A problem on games

Revision en2, by GLAYS, 2017-07-04 19:23:15

Hello.

I'm stuck in this problem for a while now.(It reminded me with the "Berzerk" problem here)

To be honest; I never really understood this kind of problems nor did I ever understand why a solution is always possible(When the author says so).

When I think of it(or any similar problem) I always believe that it will go on forever..

Specially when the statement says; "If both the players play clever and cautious(or optimally)..

When I read the examples, an idea crossed my mind; the player will win if and only if he can get to the north-east,north-west,south-east,south-west cell of his opponent's.

However, I don't know whether that is the only possibility.

Please note that I don't need help with the first two subtasks which are: R=2 & C=2 and R <= 100 & C=1.

The real problem is with the other two subtasks: R,C <= 100 and R,C <= 1e9 ...

Any hints?

Thanks!

Tags games, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English GLAYS 2017-07-04 19:23:15 22
en1 English GLAYS 2017-07-04 16:46:26 1023 Initial revision (published)