ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1224. Spiral

how about use recursion
Posted by staticor 27 Jun 2013 10:32
think about :

F(N,M)  =  F(N-? , M- ? )

and give the initial values.
Re: how about use recursion
Posted by Egor 30 Oct 2016 17:24
The number of steps is too big. By doing a single recursive step you reduce the size of the original problem to (N - 2, M - 2). If we were to reduce the size to (N / 2, M / 2) (notice that we changed minus sign to division), then we could solve it recursively.

Instead you should think of this problem as a whole. There are N rows and M columns. So some part of the robots path is by row and some part is by column:
path = row|column|row|column|row|column...

And we are counting the number of signs | in the path. As we see, each column is surrounded by sign | from both of its sides: "|column|". The first rough estimate that comes to mind after this observation is that probably the robot does 2 * (number of columns) turns. And by thinking of different specific cases of (N, M) we can turn this estimate into a true measure of the number of turns of the robot in the general case.

Edited by author 30.10.2016 17:25