CutTheCube

SRM 786 · 2020-05-14 · by vivek1998299

SRM 786 · 2020-05-14 · by vivek1998299 · Brute Force

Show categories

Class Name: CutTheCube

Return Type: int

Method Name: findWinner

Arg Types: (int, int, int)

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.

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

149)

1
1
1
Returns: 2

Since all dimensions are 1, Vivek cannot make any move and Jeel wins immediately.

150)

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.

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

Coding Area

Language: C++17 · define a public class CutTheCube with a public method int findWinner(int L, int B, int H) · 180 test cases · 2 s / 256 MB per case