Day 1 Task 1: クルード (Cluedo)

ブラック博士が殺害された．探偵のジルは犯人と場所と凶器を特定しなければならない．犯人の可能性のある人物は 6 人おり， 1 から 6 までの番号が付いている．場所には 10 個の可能性があり， 1 から 10 までの番号が付いている．凶器には 6 個の可能性があり，1 から 6 までの番号が付いている．

ジルは犯人と場所と凶器のどの組合せが正しいかを繰り返し推測する． 1 回 1 回の推測を仮説 (theory) と呼ぶ．ジルは仮説を立てるたびに，助手のジャックに仮説が正しいか間違っているかを検証してもらう．ジャックの検証により仮説が正しいことが確認された場合，ジルの仕事は完了する．仮説が間違っていたことが確認された場合，ジャックはジルに「犯人が間違っている」「場所が間違っている」「凶器が間違っている」のどれかを報告する．

ジルの役割を務めるプロシージャー Solve を実装せよ．採点プログラム (grader) は Solve を何度も呼び出す． Solve が呼び出されるたびに，新しい事件に取り組むことになる． Solve は Theory(M,L,W) を繰り返し呼ばなければならない． Theory(M,L,W) は採点プログラムにより実装される． M，L，W は犯人 (murderer)・場所 (location)・凶器 (weapon) の番号の組合せを表す．仮説が正しい場合， Theory(M,L,W) は 0 を返す．仮説が間違っている場合， Theory(M,L,W) は 1，2，3 のいずれかの値を返す． 1 は犯人が間違っていることを， 2 は場所が間違っていることを， 3 は凶器が間違っていることを表す． 2 個以上が間違っている場合，ジャックは間違っているもののうちどれか 1 つを選ぶが，どれを選ぶかはわからない (この選択は非決定的かもしれない)． Theory(M,L,W) が 0 を返したときは Solve は終了 (return) しなければならない．

例

例えば，スカーレット女史 (犯人 2) が温室 (場所 3) でリボルバー (凶器 4) を用いて殺人を行ったとしよう．プロシージャー Solve が関数 Theory を次のように呼び出す場合， 2 列目のような結果が返される．

呼び出し (Call)	返り値 (Returned value)	説明 (Explanation)
Theory(1, 1, 1)	1 または 2 または 3	3 つとも間違っている
Theory(3, 3, 3)	1 または 3	場所だけが正しい
Theory(5, 3, 4)	1	犯人だけが間違っている
Theory(2, 3, 4)	0	すべて正しい

小課題 1 (50 点)

小課題 2 (50 点)

実装の詳細

• プログラムの作成とテストのためには RunC 環境を利用せよ．
• 実装フォルダー: /home/ioi2010-contestant/cluedo/ (プロトタイプ: cluedo.zip)
• 選手が実装するファイル: cluedo.c または cluedo.cpp または cluedo.pas
• 提出ファイルのインターフェース (Contestant interface): cluedo.h または cluedo.pas
• 採点プログラムのインターフェース: grader.h または graderlib.pas
• 採点プログラムのサンプル: grader.c または grader.cpp または grader.pas と graderlib.pas
• 採点プログラムの入力のサンプル: grader.in.1．
  注意: 入力の各行には, 犯人・場所・凶器を表す 3 個の数が書かれている．
• 採点プログラムの入力のサンプルに対する期待される出力: Solve がすべての事件を正しく解決した場合, 出力ファイルには OK t (ただし t は 1 事件あたりの Theory の呼び出し回数の最大値) と書き込まれる．
• コンパイルと実行 (コマンドライン): runc grader.c または runc grader.cpp または runc grader.pas
• コンパイルと実行 (gedit プラグイン): 実装ファイルを編集中に Ctrl-R
• 提出 (コマンドライン): submit grader.c または submit grader.cpp または submit grader.pas
• 提出 (gedit プラグイン): 実装ファイルまたは採点プログラムのファイルを編集中に Ctrl-J