Shopping Mania

Since, to win, any player needs more or equal scores than the other player, considering the other player will always play optimally, at every stage of the game we should find out the maximum difference current player can have over the other player. If the difference is non-negative, that player will surely win no matter what. Otherwise, if the other player plays optimally, the other player will win.

Suppose, at some turn some player sees that item $i$ is up for sale and there are at most $j$ skips left. She can either skip this turn or purchase the item. Let $dp(i, j)$ be the maximum difference of her score over other player’s score. We want to follow the move which maximizes $dp(i, j)$.

• Purchase: If we purchase we get $p_i - dp(i + 1, k)$.

• Skip: If $j > 0$, we get $-dp(i, j-1)$.

For convenience, we can assume $dp(n + 1,k) = 0$.

Of course, if $j = 0$, the player have to purchase the current item. Otherwise, if $p_i - dp(i + 1, k) < -dp(i, j - 1)$, she may skip this turn.

Shapla should go first if $dp(1, k) >= 0$, second otherwise.