Problem Statement
There is a cuboid (a rectangular box) of dimensions L x B x H. Vivek and Jeel decided to play the game CUT THE CUBE.
In this game, the players make moves alternately and the player who cannot make a move loses. Vivek starts the game. Below we define a move.
A move consists of cutting a cuboid along the xy plane, the xz plane, or the yz plane (lengthwise, breadthwise or heightwise). The two new pieces must again have integer dimensions. Hence, a cut is only possible if the dimension that is being cut is still greater than 1.
Initially, there is only one cuboid, so Vivek must cut that one into two smaller pieces. Afterwards, Jeel must choose and cut one of those two pieces. Next, Vivek must cut one of the three cuboids he currently sees, and so on.
Find out who wins if they both play optimally. Return 1 if Vivek wins otherwise return 2.
Definition
- Class:
- CutTheCube
- Method:
- findWinner
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int findWinner(int L, int B, int H)
- (be sure your method is public)
Constraints
- L will be between 1 and 100,000, inclusive.
- B will be between 1 and 100,000, inclusive.
- H will be between 1 and 100,000, inclusive.
Examples
8
7
7
Returns: 1
7
10
1
Returns: 1
2
10
7
Returns: 1
3
1
7
Returns: 2
8
7
1
Returns: 1
5
6
3
Returns: 1
4
5
4
Returns: 1
9
6
3
Returns: 1
5
2
6
Returns: 1
9
3
8
Returns: 1
5
9
5
Returns: 2
9
2
9
Returns: 1
4
8
10
Returns: 1
8
4
6
Returns: 1
3
6
5
Returns: 1
7
6
8
Returns: 1
2
6
8
Returns: 1
2
4
6
Returns: 1
9
1
4
Returns: 1
6
4
8
Returns: 1
76
52
59
Returns: 1
8
20
88
Returns: 1
88
87
82
Returns: 1
67
44
64
Returns: 1
17
95
41
Returns: 2
14
10
14
Returns: 1
38
93
14
Returns: 1
24
70
33
Returns: 1
13
96
91
Returns: 1
100
68
20
Returns: 1
64
59
32
Returns: 1
28
99
1
Returns: 1
53
19
76
Returns: 1
22
37
86
Returns: 1
92
90
98
Returns: 1
35
58
60
Returns: 1
3
68
66
Returns: 1
19
40
61
Returns: 1
69
56
45
Returns: 1
54
26
70
Returns: 1
24
70
36
Returns: 1
85
59
25
Returns: 2
46
44
70
Returns: 1
67
18
27
Returns: 1
15
10
75
Returns: 1
13
43
61
Returns: 2
99
79
56
Returns: 1
63
49
55
Returns: 2
98
12
91
Returns: 1
42
73
84
Returns: 1
625
354
2
Returns: 1
662
32
104
Returns: 1
910
507
25
Returns: 1
268
181
796
Returns: 1
764
545
804
Returns: 1
392
969
878
Returns: 1
964
351
850
Returns: 1
231
585
712
Returns: 1
631
836
323
Returns: 1
220
584
400
Returns: 1
768
568
799
Returns: 1
915
616
695
Returns: 1
388
921
560
Returns: 1
670
126
297
Returns: 1
936
479
745
Returns: 1
687
381
462
Returns: 1
914
35
335
Returns: 1
679
253
480
Returns: 1
84
182
808
Returns: 1
909
595
653
Returns: 2
421
383
794
Returns: 1
242
332
733
Returns: 1
673
246
494
Returns: 1
659
709
583
Returns: 2
619
80
670
Returns: 1
734
693
664
Returns: 1
977
202
555
Returns: 1
826
566
156
Returns: 1
255
482
395
Returns: 1
401
72
49
Returns: 1
4015
7179
5057
Returns: 2
5368
7536
8024
Returns: 1
2496
177
7086
Returns: 1
8689
6976
502
Returns: 1
1485
7661
3471
Returns: 2
3640
375
5235
Returns: 1
9777
729
5448
Returns: 1
6515
8459
9554
Returns: 1
4960
6718
3033
Returns: 1
1678
3749
5273
Returns: 1
856
9165
9534
Returns: 1
9615
748
2018
Returns: 1
73
6796
4972
Returns: 1
8598
5333
4866
Returns: 1
2657
3666
2025
Returns: 1
7032
587
5625
Returns: 1
4236
470
2940
Returns: 1
5852
7978
1370
Returns: 1
298
4003
4389
Returns: 1
5590
3889
731
Returns: 1
72274
1807
46431
Returns: 1
39011
47816
89200
Returns: 1
75111
47326
35013
Returns: 1
19605
43919
64052
Returns: 1
53000
68768
69569
Returns: 1
43872
98760
90376
Returns: 1
62973
73619
95659
Returns: 2
74933
40374
30640
Returns: 1
59856
49573
81713
Returns: 1
61934
54086
18827
Returns: 1
47433
14361
91602
Returns: 1
69610
11277
72018
Returns: 1
97709
33982
62080
Returns: 1
22602
20932
90579
Returns: 1
29849
7979
19510
Returns: 1
9836
8609
34287
Returns: 1
88666
55902
15671
Returns: 1
15366
34934
11154
Returns: 1
81583
13269
66921
Returns: 2
84806
45742
83090
Returns: 1
95622
90560
95391
Returns: 1
98372
98637
90841
Returns: 1
98184
95260
97085
Returns: 1
90030
92383
96353
Returns: 1
96667
96792
97562
Returns: 1
93137
94771
97867
Returns: 2
91473
96837
97183
Returns: 2
95762
99057
98178
Returns: 1
98555
96888
98168
Returns: 1
97536
98505
98992
Returns: 1
97685
96571
94177
Returns: 2
98849
96639
93065
Returns: 2
90748
91071
91161
Returns: 1
99032
91337
94557
Returns: 1
99615
92685
97583
Returns: 2
91023
91336
97102
Returns: 1
92243
91690
97724
Returns: 1
92366
99343
96543
Returns: 1
91508
94417
95151
Returns: 1
98294
98586
94965
Returns: 1
94546
94739
94656
Returns: 1
94630
98027
92994
Returns: 1
99125
93484
98950
Returns: 1
94569
91170
99709
Returns: 1
96696
97276
90535
Returns: 1
91275
99739
95834
Returns: 1
98414
96089
94471
Returns: 1
91200
92510
90306
Returns: 1
90874
93691
98766
Returns: 1
1
1
1
Returns: 2
Since all dimensions are 1, Vivek cannot make any move and Jeel wins immediately.
2
1
1
Returns: 1
In this case, Vivek can only cut the cuboid lengthwise. After this move Jeel will end up with two 1x1x1 cubes which cannot be cut further. Hence Vivek wins.
2
2
1
Returns: 1
97931
95210
92383
Returns: 1
100000
100000
100000
Returns: 1
3
3
3
Returns: 2
43242
43434
33333
Returns: 1
3
1
1
Returns: 2
3
3
8
Returns: 1
99998
99998
99999
Returns: 1
2
2
3
Returns: 1
99999
99999
99999
Returns: 2
4
4
1
Returns: 1
3
3
1
Returns: 2
5
1
1
Returns: 2
1
3
3
Returns: 2
3
2
2
Returns: 1
1
1
3
Returns: 2
2
2
2
Returns: 1
1
4
4
Returns: 1
3
3
2
Returns: 1
3
5
7
Returns: 2
5
5
5
Returns: 2
1
1
2
Returns: 1
5
5
3
Returns: 2
2565
8995
7803
Returns: 2
2
1
2
Returns: 1
3
2
1
Returns: 1
4
2
1
Returns: 1
3
4
4
Returns: 1
199
199
199
Returns: 2