人は皆,トマトを切るのが苦手です.
AliceとBobは,トマトを薄切りにするようにお母さんに頼まれました.しかし,人ともトマトを切るのがとても下手です.そこで,以下のようなルールのゲームを思い付きました.
トマトの厚さは最初です.つまり,初期状態はです.
このトマトを交互に切っていき,先にこれ以上切れなくなった方が負けです.
トマトを回 "切る" とは,トマトのスライスの厚さの配列からつを選び,それを配列から削除し,新しくつの整数を配列に加えることを言います.ただし,削除した整数を,加えたつの整数を,とするとき,次の条件を満たす必要があります.
上の という条件に注意してください.人は,より薄いトマトを(枚も)生成することができません.
Aliceからゲームを始め,人とも最善の行動をした場合,勝つのはどちらですか.
Aliceからゲームを始めたとき,勝つプレイヤーの名前を出力してください.
13 4
Alice
初期状態はです.
最初,Aliceは,,という通りの切り方を選択できます.このうち,,の切り方を選択した場合,Bobは次の番で,(もしくは)のトマトのスライスを選んで切ることができます.
しかし,Aliceがという切り方を選んだ場合,Bobはこれ以上トマトを切ることができません.従って,Aliceは最善の行動を取り,トマトをに切るため,Bobは勝つことができません.
1000 777
Bob
度もトマトを切ることができないため,先行のAliceの負けです.