Editorial for JDCC '15 Contest 2 P2 - Icy Spiral
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Let's look at an example.
The two rinks require the same number of turns. What they have in common is the same number of rows, and the fact that the number of columns exceeds the number of rows. The number of turns is dependent on the magnitude of the greater dimension.
The second rink has one more row, and as a result, it has 2 more turns. Now, some edge cases.
Let be the magnitude of the smallest row or column. We can formulate
as the number of turns. This expression also passes the two edge cases. Sub the actual value of
to get the final formula
.
Time Complexity:
Comments