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.
兩個玩家正在玩塔樓破壞者的遊戲! 玩家 1 總是第一個行動,並且雙方玩家總是最好的發揮。 遊戲規則如下: – 最初有 n 座塔。 – 每個塔的高度為 m。 – 玩家輪流移動。 – 在每一回合中,玩家可以選擇高度為 x 的塔並將其高度降低為 y,其中 1 <= y < x 且 y 整除 x。 - 如果當前玩家無法採取行動,他們就會輸掉遊戲。 給定 n 和 m 的值,確定哪個玩家將獲勝。 如果第一個玩家獲勝,則返回 1。否則,返回 2。
Example 1:
n = 2, m = 6 return 2;
solution:
首先,這個塔的高度最少要移動一層,如果只剩一層,則第一個玩家無法移動,所以第二個玩家獲勝。
接著,如果 n 個塔為二的倍數,則第二個玩家會剛好把塔破壞結束,則第一個玩家無法動作。
剩餘狀況皆為第一個玩家勝利。
Code 1: BigO(1)
'use strict'; const fs = require('fs'); process.stdin.resume(); process.stdin.setEncoding('utf-8'); let inputString = ''; let currentLine = 0; process.stdin.on('data', function(inputStdin) { inputString += inputStdin; }); process.stdin.on('end', function() { inputString = inputString.split('\n'); main(); }); function readLine() { return inputString[currentLine++]; } /* * 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(n, m) { // Write your code here if (m <= 1) return 2; if (n % 2 === 0) return 2; return 1; } function main() { const ws = fs.createWriteStream(process.env.OUTPUT_PATH); const t = parseInt(readLine().trim(), 10); for (let tItr = 0; tItr < t; tItr++) { const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' '); const n = parseInt(firstMultipleInput[0], 10); const m = parseInt(firstMultipleInput[1], 10); const result = towerBreakers(n, m); ws.write(result + '\n'); } ws.end(); }
FlowChart:
Example 1
n = 2, m = 6 m <= 1 //m = 6 n % 2 === 0 //2 % 2 === 0 return 2;