[HackerRank - Java] Day 3 - 2. Tower Breakers

Tower Breakers

Two players are playing a game of Tower Breakers! Player 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 evenly $y$ 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 . Otherwise, return .

There 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 1 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.

Function Description

Complete the towerBreakers function in the editor below.

towerBreakers has the following paramter(s):

• int n: the number of towers
• int m: the height of each tower

Returns

• int: the winner of the game

Input Format

The first line contains a single integer , the number of test cases.
Each of the next lines describes a test case in the form of space-separated integers, and .

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

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.

---

두 플레이어가 타워 브레이커 게임을 하고 있다.(각 플레이어를 P1, P2라고 부르도록 하겠습니다.)
P1은 항상 먼저 움직이며, 두 플레이어는 항상 최적의 방식으로 움직인다.

최초에 n개의 타워가 있고
각 타워의 높이는 m
플레이어들은 번갈아가면서 움직이고
각 턴에서 플레이어는 높이가 x인 타워를 선택할 수 있고, 높이를 y로 줄일 수 있습니다.
(1 <= y < x 이면서, x % y = 0)
플레이어가 움직일 수 없다면 게임에서 진것입니다.

P1이 이기면 1, P2가 이기면 2를 리턴하세요.

....

설명은 매우 거창한데, 사실 문제는 매우 간단하다.
언제나 P1과 P2는 최적의 방식으로 움직인다는 것이고

y로 줄일 수 있으면서 x를 y로 나눴을 때 나머지가 0이면 된다는 말인데.
이는 즉, 높이가 12든 6이든 1로 나눠 떨어지기 때문에 1로 줄일 수 있다는 의미가 된다.

최초에 타워 높이가 2보다 작을 경우 첫 타자인 P1이 움직일 수 없기 때문에 P2가 이기고
그 외의 경우, 타워 수가 홀수면 P1이 이기고 짝수면 P2가 이긴다.

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