きつねの次郎は旅するきつねです。ある日次郎が歩いて旅をしていると分かれ道にさしかかりました。
片方の道の先には「うそつき村」があって、そこには嘘ばかり言う悪い人間がたくさんいます。もう片方の道の先「しょうじき村」があって、そこには嘘を決してつかない優しいきつねがたくさんいます。
次郎はとうぜん「しょうじき村」へ行きたいのですが、残念なことに分かれ道には標識がありません。きっと悪い人間がいじわるをしているのでしょう。
その道の周辺には N 人の人間がいるようです。そのうちの何人かは「うそつき村」から来た悪い人間です。他の人間はじつは「しょうじき村」から来た優しいきつねで、悪い人間にいじわるをされないように人間に化けています。
見た目からではある人間が「しょうじき村」から来たきつねなのか「うそつき村」から来た人間なのかは区別できません。次郎はその N 人に対して質問をすることで「しょうじき村」から来たきつねをすべて特定したいと思っています。
あまりたくさん質問をするのは時間がかかってしまうし、次郎も頭がこんがらがってしまいます。次郎がちゃんと「しょうじき村」へ行けるように、質問するのを手伝ってもらえないでしょうか。
N 人の人間がおり、0 から N-1 までの異なる整数の番号がつけられている。それぞれの人間は正直か嘘つきのどちらかであり、次の 2 種類の質問を繰り返すことで正直者をすべて特定したい。
次のパラメータをもつプロシージャ identify(N) を実装せよ:
identify(N) 中では question(Q, i, j) を繰り返し呼び出すことができる。question(Q, i, j) の仕様は次の通り:
質問に対し、正直者は常に正しい答を返し嘘つきは常に間違った答を返す。嘘つきの返答は間違いであればどのようなものでもありうるが、同じ質問を繰り返した際には同じ答を返すことは保証されている。
質問を繰り返し、それぞれの人 i についてその人が正直者であるか嘘つきであるかを判定し answer(i, X) を呼び出せ。X は人 i が正直者であることを表す 1 か嘘つきであることを表す 0 のいずれかである。answer(i, X) はどのような i の順番で呼び出しても構わないが、すべての人についてちょうど1回ずつ呼び出される必要がある。
ただしどのように質問をしても正直者をすべて特定できない場合がある。そのような場合には identify(N) は answer(i, X) を一度も呼び出さず、かわりに impossible() を呼び出して終了する必要がある。identify(N) は戻り値を持たない。
なお question(Q, i, j) は矛盾した答を返さないことが保証されている。すなわち question(Q, i, j) の結果をすべて満たすような正直者の組み合わせが少なくとも1通り存在する。
N = 2 の場合を考える。question を次のようなパラメータで呼び出し、以下に示すような返答を得たとする。
| パラメータ | 戻り値 |
|---|---|
| question(1, 0, 1) | 0 |
| question(2, 1, -1) | 0 |
これは人 0 は「人 1 は正直者ですか？」という質問に No と返答し、人 1 は「2 人のうち正直者は何人いますか？」という質問に 0 人と返答したことを表す。
人 1 が正直者だと仮定すると正直者は少なくとも 1 人はおり、これは質問の答と矛盾するので人 1 は嘘つきである。いっぽう人 0 は人 1 について正しい返答をしているので正直者である。したがって identify は次のような answer 呼び出しを行う必要がある。
| パラメータ |
|---|
| answer(0, 1) |
| answer(1, 0) |
N = 2 の場合を考える。question を次のようなパラメータで呼び出し、以下に示すような返答を得たとする。
| パラメータ | 戻り値 |
|---|---|
| question(2, 0, -1) | 2 |
| question(2, 1, -1) | 2 |
| question(1, 0, 1) | 1 |
| question(1, 1, 0) | 1 |
これは人 0, 1 の双方ともに正直者が 2 人いると主張し、また互いに互いを正直者であると主張していることを表す。
この質問の結果を満たすような組み合わせは人 0, 1 がともに正直者である場合とともに嘘つきである場合の 2 通りがあり、これ以上の質問は不可能である。したがって identify は impossible を呼び出して終了する必要がある。