[題解] UVa 12293 - Box Game
Tags
- 題解
- UVa
- E難度
題解
起手 2 必勝,只有一種分法且馬上結束遊戲。
起手 3 必敗,只有一種分法,且一定讓對方拿到必勝的 2。
由於小的那邊會直接被拿掉,而我們希望對方拿到必敗的 3。
則在 6 以前,都可以一邊分 3 另一邊分 <= 3 的數,讓對方必敗;
但 7 之後一定分不出 3,因為另一邊一定 > 3。故 7 必敗。
到 14 之前都可以分出 7 讓對方必敗,所以這些必勝。
整理觀察後發現:只有 2^n - 1 的時候必敗,其它必勝。
Time: 0.000, Rank: 232/1002
來自小希的提醒
- 可以 n & (n+1) 判斷 n 是否為 2^n - 1。證明在此略過。
cmusu