1992 . 冰塊遊戲
TopCoder
Tags
Description
某天喜歡吃冰塊的大陸人跟盩僰麌聚在一起，他們各自在吃著自己的冰塊。吃著吃著他們覺得有點無聊，所以決定玩個遊戲。每個回合只有冰塊剩下比較多的人才能吃冰塊，而如果兩個人冰塊數量一樣多，那就是上一回合沒吃冰塊的人吃冰塊。吃冰塊的人可以吃掉任何正整數且不大於對方冰塊數量的冰塊（只能吃自己的），誰先把自己的冰塊吃完就贏了，並且遊戲結束。但是吃掉冰塊是有代價的：他們事先約定好，當一個人在一回合吃掉$x$顆冰塊，他就要請對方吃$f(x)$元的「東西」（注意，兩邊的請客不會抵消）。
然而大陸人跟盩僰麌都想把錢省下來吃麥當勞，所以他們不在意輸贏，只希望自己請客的錢愈少愈好。如果在某個回合，最小化請客的錢數量的方法有很多種，那麼他們都會希望在那回合吃愈多塊冰塊愈好。
請你計算如果大陸人跟盩僰麌都用最好的策略（也就是如上所述的策略）玩遊戲，那麼最後誰會贏、雙方分別請對方多少錢，以及遊戲會如何進行。
本題滿分為150分。
Input Format
輸入第一行有兩個整數$N,M$，分別代表大陸人跟盩僰麌的初始冰塊數量。保證一開始兩人冰塊數目不一樣。
第二行有$Q=\min(N,M)$個正整數，分別代表$f(1),f(2),\cdots ,f(Q)$的值。
對於所有測資，$N,M\leq 1200; f(x)\leq1.5\times 10^ 6$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $M=1$ | 18 |
| 2 (0~9) | $f(x)=c$，其中$c$是某正整數 | 22 |
| 3 (10~14) | $f(x)=cx$，其中$c$是某正整數 | 24 |
| 4 (15~19) | $N, M\leq 10$ | 26 |
| 5 (15~24) | $N, M\leq 600$ | 33 |
| 6 (0~30) | 無限制 | 27 |
Output Format
第一行輸出在大陸人跟盩僰麌都用最好的策略玩遊戲的情況下誰會贏。如果大陸人會贏，請輸出Dalu；如果盩僰麌會贏，請輸出bc4iaaa。
第二行輸出兩個整數，代表大陸人跟盩僰麌分別要請對方多少錢的「東西」。
第三行輸出一個整數$F$，代表遊戲總共會進行幾個回合。
接下來$F$行，每行輸出一個正整數，代表遊戲從開始到結束每一回合吃的冰塊數量。
Sample Input 1
7 4 2
Sample Output 1
7 2
2
1
3
Hints
範例測資中，大陸人會選擇先把他的一塊冰塊吃掉，接著換盩僰麌，他則會選擇一次吃完他的所有冰塊。你可以自行驗證這的確是最佳策略。
你能用注音打出盩僰麌這三個字嗎？
Problem Source
Problem Set by edisonhello / Yihda Yol
建國中學106學年度校隊選拔：初試pE
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 18 |
| 2 | 0~9 | 22 |
| 3 | 10~14 | 24 |
| 4 | 15~19 | 26 |
| 5 | 15~24 | 33 |
| 6 | 0~30 | 27 |