GameOfSegments
SRM 624 · 2013-12-22 · by MDantas
Problem Statement
Rijél is a very wise teacher. He loves mathematics, especially games and geometry problems. Recently one of his students challenged him to the following game:
Initially, there is a polygon with N vertices drawn in the plane. The polygon is strictly convex, i.e., each internal angle is strictly smaller than 180 degrees. The vertices of the polygon are numbered 1 through N, in clockwise order.
Two players play the game on this polygon. The players take alternating turns. In each turn, the current player chooses a diagonal or a side of the polygon and draws it as a straight line segment. (A diagonal of the polygon is a line segment that connects any two non-adjacent vertices of the polygon.) The player is only allowed to choose a diagonal or a side that does not intersect any of the previously drawn segments (it must not share endpoints with any of them either). The player who cannot draw a diagonal or a side according to the above rules loses the game.
You are given the
We assume that both players play the game optimally. Return 1 if the first player wins and 2 otherwise.
Constraints
- N will be between 3 and 1,000, inclusive.
3 Returns: 1
This polygon has zero diagonals and three sides. The first player will always win no matter which side he picks.
4 Returns: 1
This polygon has four sides and two diagonals. The first player wins the game if he takes one of the diagonals, because he will leave no choice for the second player.
498 Returns: 1
887 Returns: 1
854 Returns: 1
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GameOfSegments with a public method int winner(int N) · 74 test cases · 2 s / 256 MB per case