網頁

2014年1月25日 星期六

UVa 11489 Integer Game

http://uva.onlinejudge.org/external/114/11489.html
題意:
  由S先開始,每次拿掉一個數字都要使得剩下的"位數和"是3的倍數,如果找不到數字拿掉就輸了。

想法:
  我們知道如果數字和為3的倍數,那麼接下來要拿掉的數字必須為3的倍數,才能繼續使得數字和為3的倍數。本題可將一連串的數字分成兩組:3的倍數和非3的倍數,然後有3種情況:
  1. 如果非3倍數的數字和是3的倍數:那麼只要看3的倍數的數字個數是奇數個還偶數個就能決定贏家,因為當拿完3的倍數的數字後就無法再拿任何數字了。
  2. 如果非3倍數的數字和不是3的倍數:
    那麼需要確認是否能從非3倍數的數字中找出使得數字和為3的倍數,
    *如果找的到,那麼就可以回到狀況1
    *如果找不到,代表是T獲勝,因為從一開始就無法拿掉任何數字。