Editorial for COCI '17 Contest 2 #1 Košnja


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.

Let N and M denote the number of rows and columns of the matrix that represent the lawn, respectively.

Let's assume that N \le M. One of the optimal ways for Mirko to visit each field while making the minimal number of turns is that he starts from the upper left field facing right, visits the entire first row, goes to the second row, turns right, visits the entire second row, goes to the third row, and so on. The described way takes exactly 2(N-1) turns.

In the case when M \le N, he needs to visit the fields in the same way, but now he needs to visit the columns in order. This takes exactly 2(M-1) turns. Therefore, the solution to the problem is 2\min(N-1, M-1).

The proof that the described way is indeed the optimal way is left as an exercise to the reader


Comments

There are no comments at the moment.