主題

ZeroJudge - f710: 11489 - Integer Game 解題心得

Not In My Back Yard | 2021-03-28 00:00:04 | 巴幣 0 | 人氣 20

題目連結:


題目大意:
玩家 S 和 T 正在玩一個數字遊戲:
數字一開始為 N ,而 S 為先手、T 為後手,兩人輪流。
輪到某個玩家的回合時,該玩家必須從數字 N 取出一位數使得新的數字 N' 為 3 的倍數、
當某玩家沒有位數可以取時,該玩家即敗北。

輸入第一列給定一正整數 T (T < 60),代表有 T 筆測試資料,每筆佔一列。每列給定一正整數 N ,代表兩位玩家 S 和 T 本局遊戲一開始的數字。試問,誰必贏?輸出格式參見範例輸出。



範例輸入:
3
4
33
771


範例輸出:
Case 1: S
Case 2: T
Case 3: T


解題思維:
首先我們回憶一下一正整數 N 為 3 的倍數之充分必要條件,即 N 的每個位數之和為 3 的倍數。

而我們定義 D = N 的位數和、C0 = N 的位數中那些除以 3 餘 1 之數字和、C1 = N 的位數中那些除以 3 餘 1 之數字和、C2 = N 的位數中那些除以 3 餘 2 之數字和。

則可以看到 S 要必贏的話有以下情況:
一.D 為 3 的倍數且 C0 為奇數:
這個情況最單純,因為所有玩家每回合都只能拿那些是 3 的倍數之位數(不然無法使數字維持是 3 的倍數),即 3 、 6 以及 9。再加上兩人輪流取位數,因此當 C0 為奇數時,最後會輪到 T 的回合而 T 沒有數字可以取,因此 S 必贏。

二.D 為 3 的倍數 + 1 且 C1 > 0 且 C0 為偶數:
首先,S 一開始必須拿走一個除以 3 餘 1 之位數(1 、 4 或是 7),然後之後就變得像是情況一,但是此時是輪到 T 的回合。因此當 C0 為偶數時,又會再輪回到 T 之回合,此時 S 必贏。

三.D 為 3 的倍數 + 2 且 C2 > 0 且 C0 為偶數:
首先,S 一開始必須拿走一個除以 3 餘 2 之位數(2 、 5 或是 8),然後之後就變得像是情況一,但是此時是輪到 T 的回合。因此當 C0 為偶數時,又會再輪回到 T 之回合,此時 S 必贏。

除了以上三種情況,其他情況都是 T 必贏。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作