StonesGame

SRM 493 · 2010-11-01 · by maksay

SRM 493 · 2010-11-01 · by maksay · Greedy, Simple Math

Show categories

Class Name: StonesGame

Return Type: String

Method Name: winner

Arg Types: (int, int, int, int)

Problem Statement

Romeo and his friend Strangelet are playing a game. There are N stones in a row, all of which are black except for the M-th one, which is white (all positions in this problem are 1-based). The players alternate turns, and Romeo plays first. On each turn, a player must choose exactly K consecutive stones, one of which must be white, and reverse their order. The winner is the first player who puts the white stone in the L-th position. Return "Romeo" if Romeo can win regardless of how Strangelet plays, and return "Strangelet" if Strangelet can win regardless of Romeo's strategy. Otherwise, return "Draw" since neither player can win if both players play optimally. All quotes are for clarity only.

Constraints

N will be between 2 and 1,000,000, inclusive.
M, K and L will each be between 1 and N, inclusive.
M and L will be different.

Examples

2
1
2
2
Returns: "Romeo"

3
1
1
2
Returns: "Draw"

There are three stones and the stone in position 1 is white. To win the game, a player must put the white stone in position 2. However, since K is 1, each player can only choose a single stone to reverse, so it is impossible to move the white stone from its original position. Therefore, neither player can win.

5
1
2
2
Returns: "Romeo"

Romeo can win on his first move by reversing the order of the first two stones.

5
5
2
3
Returns: "Strangelet"

Romeo's only possible move is to reverse the last two stones. This puts the white stone in position 4. Strangelet can then reverse the third and fourth stones, putting the white stone in position 3 and winning the game.

5
5
2
2
Returns: "Draw"

This is similar to the previous example, but here, the white stone must be moved to position 2. As in the previous example, Romeo's first move will put the white stone in position 4. This time, Strangelet will then move it back to position 5 because otherwise, Romeo would move it to position 2 and win. This sequence of moves will repeat infinitely and neither player will win.

Submissions are judged against all 193 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StonesGame with a public method string winner(int N, int M, int K, int L) · 193 test cases · 2 s / 256 MB per case