Tower Breakers

HackerRank 問題: Tower Breakers
Categories:
Tags:

Question

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 .
  • 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.

HackerRank 問題: Tower Breakers

Answer

<?php

/*
 * Complete the 'towerBreakers' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. INTEGER m
 */

function towerBreakers($tower_number, $unit_number) {
    if ($unit_number == 1) {
        // no movable unit, and player 1 move first, so player 2 win
        $winner_player = 2;
    } else {
        if ($tower_number % 2 == 0) {
            // tower number is even, player 1 move first, player 2 can always move exact same as player 1. so player 2 will never lose
            $winner_player = 2;
        } else {
            // tower number is odd, player 1 can move to 1 unit at first move. Then player 1 can move exact same as player 2 move at 3rd move. So player 1 will never lose
            $winner_player = 1;
        }
    }

    return $winner_player;
}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$t = intval(trim(fgets(STDIN)));

for ($t_itr = 0; $t_itr < $t; $t_itr++) {
    $first_multiple_input = explode(' ', rtrim(fgets(STDIN)));

    $n = intval($first_multiple_input[0]);

    $m = intval($first_multiple_input[1]);

    $result = towerBreakers($n, $m);

    fwrite($fptr, $result . "\n");
}

fclose($fptr);

Reference