課題

N 人の人間がおり、0 から N-1 までの異なる整数の番号がつけられている。それぞれの人間は正直か嘘つきのどちらかであり、次の 2 種類の質問を繰り返すことで正直者をすべて特定したい。

• ある人 i に対して「人 j は正直者ですか？」と質問する
• ある人 i に対して「N 人のうち正直者は何人いますか？」と質問する

パラメータ identify(N) をもつプロシージャを実装する:

• N -- 人の数。人には 0 から N-1 までの異なる整数の番号がつけられている。

identify(N) 中では question(Q, i, j) を繰り返し呼び出すことができる。question(Q, i, j) の仕様は次の通り:

• Q=1 のとき question(Q, i, j) は人 i に対して「人 j は正直者ですか？」と質問したときの返答を返す。戻り値は Yes を表す 1 か No を表す 0 のいずれかである。
• Q=2 のとき question(Q, i, j) は人 i に対して「N 人のうち正直者は何人いますか？」と質問したときの返答を返す。戻り値は 0 以上 N 以下の整数である。このとき j の値は内部で捨てられるので何を指定しても構わない。
• それ以外の Q の値で question(Q, i, j) を呼び出すと不正なライブラリ呼び出しとみなし、不正解と判定する。

質問に対し、正直者は常に正しい答を返し嘘つきは常に間違った答を返す。嘘つきの返答は間違いであればどのようなものでもありうるが、同じ質問を繰り返した際には同じ答を返すことは保証されている。

質問を