Notice that the state of the game is completely determined by only three numbers: ~l~ - the leftmost pebble still in the game, ~r~ - the rightmost pebble still in the game and ~m~ - the number of red pebbles collected so far by the player whose turn it is. Using prefix sums on the number of red pebbles in the array, from these numbers, we can easily determine which player will win. Since ~n, k \le 350~ and from each game state, we can make only two possible moves, a natural idea is to use dynamic programming. The state will be ~dp[l][r][m]~ which will be ~1~ if the current player can win, and ~0~ otherwise. The number of red pebbles collected so far by the other player can be determined from the information of the state: ~h = (\text{num. of red pebbles}) - m - (\text{num. of red pebbles in interval }l, r)~, where we used ~h~ to denote this number. The transition is defined as follows:

• ~dp[l][r][m] = 0~, if ~m \ge k~
• ~dp[l][r][m] = 1~, if ~h \ge k~
• ~dp[l][r][m] = {!dp[l+1][r][h]} \mid {!dp[l][r-1][h]}~, otherwise