主題

ZeroJudge - e574: 10404 - Bachet's Game　解題心得

Not In My Back Yard | 2019-12-22 16:32:44 | 巴幣 0 | 人氣 1085

題目連結：

題目大意：

輸入有多筆測試資料，每筆佔一列。每列開頭有兩正整數 n 、 m （n ≦ 1000000，m ≦ 10），代表石頭數，以及有 m 種拿法。接著有 m 個正整數（一定有一數為 1），代表一次可以拿的石頭之數量。

現在 Stan 先手、Ollie 後手，拿走最後一塊石頭的人贏。並假設 Stan 、 Ollie 都採取最佳策略。試問 Stan 、 Ollie 誰贏？

範例輸入：

20 3 1 3 8

21 3 1 3 8

22 3 1 3 8

23 3 1 3 8

1000000 10 1 23 38 11 7 5 4 8 3 13

999996 10 1 23 38 11 7 5 4 8 3 13

範例輸出：

Stan wins

Ollie wins

Stan wins

Ollie wins

解題思維：

拈（Nim）的變體。跟這題十分地相似。

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

ETH官方钱包