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.
Definition
- Class:
- GameOfSegments
- Method:
- winner
- Parameters:
- int
- Returns:
- int
- Method signature:
- int winner(int N)
- (be sure your method is public)
Constraints
- N will be between 3 and 1,000, inclusive.
Examples
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
15
Returns: 2
882
Returns: 1
621
Returns: 2
896
Returns: 1
792
Returns: 1
265
Returns: 1
191
Returns: 2
584
Returns: 1
34
Returns: 1
848
Returns: 1
778
Returns: 1
413
Returns: 2
521
Returns: 1
302
Returns: 1
842
Returns: 1
356
Returns: 1
520
Returns: 1
197
Returns: 1
781
Returns: 1
274
Returns: 1
663
Returns: 1
393
Returns: 1
856
Returns: 1
858
Returns: 1
59
Returns: 2
996
Returns: 1
577
Returns: 1
425
Returns: 1
400
Returns: 1
861
Returns: 1
733
Returns: 1
745
Returns: 1
409
Returns: 1
873
Returns: 1
827
Returns: 1
83
Returns: 1
967
Returns: 1
507
Returns: 1
704
Returns: 1
248
Returns: 1
145
Returns: 2
745
Returns: 1
356
Returns: 1
746
Returns: 1
459
Returns: 1
879
Returns: 2
11
Returns: 1
999
Returns: 1
7
Returns: 1
10
Returns: 1
929
Returns: 1
997
Returns: 1
246
Returns: 1
1000
Returns: 1
6
Returns: 1
925
Returns: 1
5
Returns: 2
987
Returns: 1
190
Returns: 1
891
Returns: 1
700
Returns: 1
8
Returns: 1
777
Returns: 2
25
Returns: 2
24
Returns: 1
903
Returns: 1
816
Returns: 1
37
Returns: 1
9
Returns: 2