Codeforces Round #745 (Div. 2) Portal Solution (Java/C++)

Solution:

It is not difficult to find that when a=5 and b=4, only 16 steps are required even in the worst case.

So we directly enumerate the position of the point in the upper left corner of the portal, and then enumerate the size of the portal from small to large. It is not difficult to find that if the red and orange parts in the figure below exceed 16, there is no need to continue enumerating the size of the portal.
Because further expansion of the portal size will still cover the red and orange parts, the required operations will only increase. It is better to directly choose a=5 and b=4.

In the code implementation, we can further optimize according to the order of a and b enumeration.

Code:

Java

Submission #130624519 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #130624780 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge