Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

How to use Grundy numbers concept in this?

Revision en1, by TTMMM, 2019-12-09 21:55:14

MIKE AND INFINITE GRID Mike and his friend are playing a game in the first quadrant of x-y plane. They have a toy car, which is initially placed at position (a, b). A player who can place it at position (p, q), where p<a and q<b, will win the game. In a move, a player can move this car from position (x, y) to:

A position (x',y), such that p <= x' < x. A position (x,y'), such that q <= y' < y. A position (x-k,y-k), such that 0 < k <= min(x-p,y-q).

Mike starts the game and both the players play optimally. Find the winner of the game.

I understand the question reduces to two piles with A,B coins and players can remove any number of coins from individual stack and can remove k coins from both where k<=min(A,B)

Tags game theory, sprague-grundy, competitive programming, #nim-game


  Rev. Lang. By When Δ Comment
en1 English TTMMM 2019-12-09 21:55:14 806 Initial revision (published)