Counter game
Categories:
Question
Louise and Richard have developed a numbers game. They pick a number and check to see if it is a power of 2. If it is, they divide it by 2. If not, they reduce it by the next lower number which is a power of 2. Whoever reduces the number to wins the game. Louise always starts.
Given an initial value, determine who wins the game.

說明
條件
- 當數字是 2 的指數倍數,則將數字除以 2
- 當數字不是 2 的指數倍數,與小於數字,且最接近的指數倍數的
差,當作是下一個數字
| 目前數字 | 下個數字 | 說明 |
|---|---|---|
| 64 | 32 | 是 2 的指數倍數,執行條件 1,(64/2)=32 |
| 92 | 28 | 不是 2 的指數倍數,執行條件 2,92 以下的 2 的指數數字是 64,(92-64)= 28 |
2 的指數表
| 2 指數倍數 | 結果 |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| 6 | 64 |
| 7 | 128 |
| 8 | 256 |
| 9 | 512 |
| 10 | 1024 |
解決問題
- 找出是 2 的指數計算次數
- 找出非 2 的指數計算次數
2 的指數計算
下表為列出 2 的指數的二元表,可以看到當數字為 2 的指數時,除了最前方為 1,後面則都為 0
當遇到 條件 1,當數字是 2 的指數倍數,則將數字除以 2
所以後面的運算都是除以 2,剛好後面 0 的出現次數,就是要除以 2 的運算次數
| 數字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | - | 除 2 除到 1 運算次數(0 的出現次數) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 256 | - | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | 8 |
| 128 | - | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | 7 |
| 64 | - | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | - | 6 |
| 32 | - | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | - | 5 |
| 16 | - | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | - | 4 |
| 8 | - | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | - | 3 |
| 4 | - | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | - | 2 |
| 2 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | - | 1 |
| 1 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | - | 0 |
非 2 的指數計算
以數字 496 為例,可以看到他的二進位數字是 11110000,以下是所有執行步驟
| 步驟 | 數字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | 下個數字 | 誰執行動作 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 496 | - | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 496 - 256 = 240 | Louise |
| 2 | 240 | - | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 240 - 128 = 112 | Richard |
| 3 | 112 | - | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 112 - 64 = 48 | Louise |
| 4 | 48 | - | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 48 - 32 = 16 | Richard |
| 5 | 16 | - | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 16 / 2 = 8 | Louise |
| 6 | 8 | - | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 8 / 2 = 4 | Richard |
| 7 | 4 | - | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 4 / 2 = 2 | Louise |
| 8 | 2 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 2 / 2 = 1 | Richard |
| 9 | 1 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 不能除了,輸了 | Louise |
在步驟 1 ~ 4 時,因為後面的二進位皆有 1 出現,所以一定非 2 可以整除的數字(非 2 的指數),所以遇到 條件2,與小於數字,且最接近的指數倍數的差,當作是下一個數字
在 1 ~ 4 步驟可以剛好看到,那個差值剛好是將二進位數字,最前面的 1 拿掉變為 0,就是這個差值,所以等於是在遇到 2 的指數數字前,1 的數量有多少個,就是使用 條件2 運算的次數
在步驟 5 ~9 時,可以看到數字變為 2 的倍數了,所以會用條件 1,當數字是 2 的指數倍數,則將數字除以 2,最後會算出來,輸的是 Louise,贏的是 Richard
計算邏輯拆分 2 種,2 的指數與非 2 的指數
剛剛在上方有提到,當遇到 2 的指數數字,運算的次數就是 後方 0 的數字多寡,所以等於是使用 條件 1 執行的次數
所以 16(10000),後面 0 的數字有 4 個,所以 條件 1 要運算 4 次
| 步驟 | 數字 | - | 16 | 8 | 4 | 2 | 1 | 下個數字 |
|---|---|---|---|---|---|---|---|---|
| 5 | 16 | - | 1 | 0 | 0 | 0 | 0 | 16 / 2 = 8 |
| 6 | 8 | - | 0 | 1 | 0 | 0 | 0 | 8 / 2 = 4 |
| 7 | 4 | - | 0 | 0 | 1 | 0 | 0 | 4 / 2 = 2 |
| 8 | 2 | - | 0 | 0 | 0 | 1 | 0 | 2 / 2 = 1 |
| 9 | 1 | - | 0 | 0 | 0 | 0 | 1 | 不能除了,輸了 |
當遇到非 2 的指數,使用 條件 2 執行的次數為遇到 2 的指數 1,前面 1 的數量,就是執行的次數
最後會遇到 2 的指數數字為 16,所以在 16(10000) 之前 1 出現的次數,496(111110000) 1 出現的次數是 4 次(排除 16 本身的 1),所以 條件 2 要運算 4 次
| 步驟 | 數字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | 下個數字 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 496 | - | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 496 - 256 = 240 | |
| 2 | 240 | - | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 240 - 128 = 112 | |
| 3 | 112 | - | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 112 - 64 = 48 | |
| 4 | 48 | - | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 48 - 32 = 16 | |
| 5 | 16 | - | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 16 / 2 = 8 |
統整運算邏輯
條件 1 是 0 出現的次數,條件 2 是 1 出現的次數,為了方便計算,直接將整個數字 -1,就會從 496(111110000) 變成 495(111101111)
| 步驟 | 數字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 496 | - | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 1 | 496 | - | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
這樣等於 條件 1 是 0 出現的次數就變成 1 出現的次數,那接下來只需要計算所有 1 出現的次數,就可以知道整個遊戲玩了幾輪,就可以知道誰輸誰贏了
| 條件 | 程式 | 結果 |
|---|---|---|
遊玩次數為 偶數(even) |
play_game_times % 2 = 0 | Richard 贏 |
遊玩次數為 奇數(odd) |
play_game_times % 2 = 1 | Louise 贏 |
Answer
Python
def counterGame(n)
setbits = bin(n-1).count('1')
if setbits%2 == 0:
return 'Richard'
else:
return 'Louise'
PHP
<?php
/*
* Complete the 'counterGame' function below.
*
* The function is expected to return a STRING.
* The function accepts LONG_INTEGER n as parameter.
*/
function counterGame($initial_number)
{
// calculate bit 1 number for play game times
$play_game_times = 0;
$initial_number -= 1;
while($initial_number) {
// if the number is exponent 2(last 1 occur), then the result will be 0, and end the while loop
$initial_number = $initial_number & ($initial_number -1);
$play_game_times++;
}
// calculate play game times to find winner
if ($play_game_times % 2 == 0) {
$winner = 'Richard';
} else {
$winner = 'Louise';
}
return $winner;
}
$fptr = fopen(getenv("OUTPUT_PATH"), "w");
$t = intval(trim(fgets(STDIN)));
for ($t_itr = 0; $t_itr < $t; $t_itr++) {
$n = intval(trim(fgets(STDIN)));
$result = counterGame($n);
fwrite($fptr, $result . "\n");
}
fclose($fptr);
C
int setBits(unsigned long long int n) {
int count = 0 ;
while(n) {
n &= (n-1) ;
count ++ ;
}
return count ;
}
int main() {
int t ;
scanf("%d\n",&t) ;
while(t--) {
unsigned long long int n ;
scanf("%llu\n",&n) ;
if (setBits(n-1) & 1) printf("Louise\n") ;
else printf("Richard\n") ;
}
return 0;
}