Блог пользователя mohamedeltair

Автор mohamedeltair, история, 7 лет назад, По-английски

When the subgames are independent, dealing with them is easy, you try to calculate grundy for each sub game, either you derive a dynamic programming solution or see if the grundies follow specific pattern then just code the pattern directly (this is useful if the limits are very high), finally you xor the grundies.

But suppose a game like this: you have n piles and each pile has number of stones greater than 0, in a move you pick a number of stones to remove, this number will be subtracted from any pile which has a number of stones greater than or equal the number you have picked, as you see here one move affects more than one existing pile, how to think in these situations ?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I guess this type of games will follow a pattern, that you need to discover.

check this problem here you can also read more about the situation when n=2 in here.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Note that the game you are describing is part of the solution to 850C - Арпа и игра с Можтабой. It can be solved using simple DP, as you can see in the editorial.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks all for your responses