Day 2 Task 1: 神経衰弱 (Memory)

神経衰弱 (Memory) と呼ばれる 50 枚のカードを使ったゲームがある．それぞれのカードには，表に A から Y (アスキーコードの 65 から 89 ) のうち 1 文字が書かれており，50 枚のカードには各文字がちょうど 2 回ずつ現れる．カードはランダムな順番にシャッフルされ，裏向きの状態でテーブルに配られる．

ジャック (Jack) は 2 枚のカードを，文字が見えるように表向き (face up) にひっくり返してゲームをする．25 文字それぞれについて， 2 枚の表向きにしたカードの文字が初めて一致した場合に，ジャックは母親からキャンディーをもらう．例えば，ジャックがひっくり返した 2 枚のカードが初めて両方とも M と書かれている場合は，ジャックはキャンディーをもらう．カードに書かれた文字が一致しているかどうかにかかわらず，ジャックは 2 枚のカードをひっくり返し，再び裏向きにする．手順はジャックがそれぞれの文字について1個ずつ，25 個のキャンディーを受け取るまで繰り返される．

ゲームをプレイするプロシージャー play を実装せよ．あなたの実装は採点プログラムが実装した faceup(C) を呼び出す必要がある． C は 1 以上 50 以下の数であり，あなたがひっくり返して表向きにしたい特定のカードを表す．指定するカードはその時点で表向きであってはならない． faceup(C) はカード C に書かれた文字を返す．

faceup を2回呼び出すごとに，採点プログラムは自動的に両方のカードをひっくり返し，再び裏向きにする．

あなたのプロシージャー play はジャックが 25 個全てのキャンディーを受け取った後にのみ終了して良い． faceup(C) の呼び出しはジャックが最後のキャンディーをもらった後でも許されている．

例

これはプロシージャー play の一連の呼び出しの例に説明を加えたものである．
呼び出し (Call)返り値(Returned value)説明(Explanation)
faceup(1)'B'カード 1 には B と書かれている．
faceup(7)'X'カード 7 には X と書かれている．2 つの文字は異なっている．
採点プログラムは自動的にカード 1 とカード 7 をひっくり返し裏向きにする．
faceup(7)'X'カード 7 には X と書かれている．
faceup(15)'O'カード 15 には O と書かれている．2 つの文字は異なっている．
採点プログラムは自動的にカード 7 とカード 15 をひっくり返し裏向きにする．
faceup(50)'X'カード 50 には X と書かれている．
faceup(7)'X'カード 7 には X と書かれている．ジャックは1個目のキャンディーをもらう．
採点プログラムは自動的にカード 50 とカード 7 をひっくり返し裏向きにする．
faceup(7)'X'カード 7 には X と書かれている．
faceup(50)'X'カード 50 には X と書かれている．2 つの文字は一致しているがジャックはキャンディーをもらえない．
採点プログラムは自動的にカード 7 とカード 50 をひっくり返し裏向きにする．
faceup(2)'B'カード 2 には B と書かれている．
...
(いくつかの呼び出しについて省略する)
...
faceup(1)'B'カード 1 には B と書かれている．
faceup(2)'B'カード 2 には B と書かれている． ジャックは25個目のキャンディーをもらう．

小課題 1 [50 点]

ゲームのルールに従い制限時間内に終了する戦略を実装せよ．

例えば，faceup(C) を常に 2*(49+48+...+2+1) = 2450 回ちょうど呼び出す単純な戦略が存在する．

小課題 2 [50 点]

いかなるゲームに対しても faceup(C) を高々 100 回呼び出して終了する戦略を実装せよ．

実装の詳細