Timus 1180. Stone Game 遊戲題目

Two Nikifors play a funny game. There is a heap of N stones in front of them. Both Nikifors in turns take some stones from the heap. One may take any number of stones with the only condition

that this number is a nonnegative integer power of 2 (e.g. 1, 2, 4, 8 etc.). Nikifor who takes the last stone wins. You are to write a program that determines winner assuming each Nikifor does its best.

An input contains the only positive integer number N (condition N ≤ 10250 holds).

The first line should contain 1 in the case the first Nikifor wins and 2 in case the second one does. If the first Nikifor wins the second line should contain the minimal number of stones he should

take at the first move in order to guarantee his victory.

input

output

這也是個有趣的問題，也很經典的遊戲題目的變形了。

不過這道題擴充了成為無限大的數了。

類似的遊戲有：沒人可以拿掉桌面上的棋子，每次不能超過5個，最後沒棋子可以拿的算輸

解決這樣的題目隻能是尋找規律了，不能真的模拟區玩了，否則必定逾時。

這道題目的規律就是：

1 如果給出的stone是3的倍數，那麼先取者必輸

2 如果給出的不是3的倍數，那麼先取者就湊成3的倍數就必赢，因為湊3的倍數很容易，去掉1個或者2個必定可以湊出來了

是以最後問題就成了mod3問題了。

我是怎麼想出來的？

我是一個列子一個例子去觀察，最後得出結論的，然後驗證，AC，結論正确。

也挺花時間的。