[HackerRank] Tower Breakers c++

• Problem

Two players are playing a game of Tower Breakers! Player 1 always moves first, and both players always play optimally.The rules of the game are as follows:

• Initially there are n towers.
• Each tower is of height m.
• The players move in alternating turns.
• In each turn, a player can choose a tower of height x and reduce its height to y, where 1<= y <x and y evenly divides x.
• If the current player is unable to make a move, they lose the game.
• Given the values of n and m, determine which player will win. If the first player wins, return 1. Otherwise, return 2.

• Example

n = 2, m = 6

here are 2 towers, each 6 units tall. Player 1 has a choice of two moves:

- remove 3 pieces from a tower to leave 3 as 6 modulo 3 = 0
- remove 5 pieces to leave 1

Let Player 1 remove 3. Now the towers are 3 and 6 units tall.

Player 2 matches the move. Now the towers are both 3 units tall.

Now Player  has only one move.

Player 1 removes 2 pieces leaving 1. Towers are 1 and 2 units tall.
Player 2 matches again. Towers are both 1 unit tall.

Player 1 has no move and loses. Return 2.

• Constraints

1 <= t <= 100

1 <= n,m <= 10^6

• Sample Input

STDIN   Function
-----   --------
2       t = 2
2 2     n = 2, m = 2
1 4     n = 1, m = 4

• Sample Output

2
1

• Explanation

We'll refer to player 1 as  P1 and player 2 as P2

In the first test case,P1  chooses one of the two towers and reduces it to 1. Then P2 reduces the remaining tower to a height of 1. As both towers now have height 1,P1  cannot make a move so P2 is the winner.

In the second test case, there is only one tower of height 4.P1  can reduce it to a height of either 1 or 2.

P1 chooses 1 as both players always choose optimally. Because P2 has no possible move, P1 wins.

• Solutions

문제가 해석이 잘안되서 검색해봤더니

다른 분도 듣도 보다 못한 이상한 게임이라고 해서 공감너무 됬네요 ㅋㅋㅋㅋㅋ

문제는 타워의 수가 짝수이거나, 타워 높이가 1이면 player 2가 이기고, 이외의 경우에는 player 1이 이긴다고 합니다.

int towerBreakers(int n, int m) {
    return n%2 == 0 || m==1 ? 2 : 1;
}

hackerrank tower breakers c++