/ 
Time Limit: 0 msec / Memory Limit: 256 MB
きつねの次郎は旅するきつねです。ある日次郎が歩いて旅をしていると分かれ道にさしかかりました。
片方の道の先には「うそつき村」があって、そこには嘘ばかり言う悪い人間がたくさんいます。もう片方の道の先「しょうじき村」があって、そこには嘘を決してつかない優しいきつねがたくさんいます。
次郎はとうぜん「しょうじき村」へ行きたいのですが、残念なことに分かれ道には標識がありません。きっと悪い人間がいじわるをしているのでしょう。
その道の周辺には N 人の人間がいるようです。そのうちの何人かは「うそつき村」から来た悪い人間です。他の人間はじつは「しょうじき村」から来た優しいきつねで、悪い人間にいじわるをされないように人間に化けています。
見た目からではある人間が「しょうじき村」から来たきつねなのか「うそつき村」から来た人間なのかは区別できません。次郎はその N 人に対して質問をすることで「しょうじき村」から来たきつねをすべて特定したいと思っています。
あまりたくさん質問をするのは時間がかかってしまうし、次郎も頭がこんがらがってしまいます。次郎がちゃんと「しょうじき村」へ行けるように、質問するのを手伝ってもらえないでしょうか。
課題
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) を呼び出すと不正なライブラリ呼び出しとみなし、不正解と判定する。
質問に対し、正直者は常に正しい答を返し嘘つきは常に間違った答を返す。嘘つきの返答は間違いであればどのようなものでもありうるが、同じ質問を繰り返した際には同じ答を返すことは保証されている。
質問を繰り返し、それぞれの人 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通り存在する。
例
例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) |
例2
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 を呼び出して終了する必要がある。
小課題
小課題 1 (16 点)
- 1 ≦ N ≦ 10
- identify(N) は question(Q, i, j) を何度呼び出しても構わない。
小課題 2 (29 点)
- 1 ≦ N ≦ 1 000
- identify(N) は question(Q, i, j) を何度呼び出しても構わない。
小課題 3 (17 点)
- 1 ≦ N ≦ 100 000
- identify(N) が question(Q, i, j) を呼び出す回数は 200 500 回以下でなければならない。
小課題 4 (38 点)
- 1 ≦ N ≦ 100 000
- identify(N) が question(Q, i, j) を呼び出す回数は 100 500 回以下でなければならない。
実装の詳細
制限
- CPU 時間制限: 1 秒
- メモリ制限: 256 MB
注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。
インターフェース (API)
- 実装フォルダ: honest/ (プロトタイプ: honest.zip)
- 競技者が実装するファイル: または honest.cpp
- 提出ファイルのインターフェース: honest.h
- 採点プログラムのサンプル: または grader.cpp
- 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
注意:採点プログラムのサンプルは次の書式の入力を読み込む。- 1 行目: N
- 2 行目: N 個の整数 X[0], X[1], ..., X[N-1] が空白区切りで書かれている。X[i] は人 i が正直者か嘘つきかを表す。
- 3 行目: N 個の整数 A[0], A[1], ..., A[N-1] が空白区切りで書かれている。A[i] は人 i が正直者の人数を質問された際の返答を表す。
- 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
注意:採点プログラムのサンプルは次の書式の出力を書き出す。- 正直者が完全に特定可能な場合: N 個の整数 X[0], X[1], ..., X[N-1] が空白区切りで出力される。意味は入力のそれと同じである。
- 正直者を特定することが不可能な場合: 文字列 "Impossible." のみからなる1行が出力される。
- 採点プログラムのサンプルは標準エラー出力に次の書式で情報を書き出す。
- 1 行目: "#question = Q" が出力される。ただし Q はこの実行で question が呼び出された回数である。