XOR Circuit

Time Limit : 5 sec, Memory Limit : 65536 KB

問題 G XOR 回路

問題文

計算機科学実験及演習 3 は CAD を用いて CPU を設計する授業である.CPU は多くの回路を組み合わせなければ動かず,その中の 1 つに n ビット入力の XOR 回路がある.ここで XOR 回路とは,入力ビット列 x1x2...xn に対して,x1 + x2 + ... + xn\ (mod 2) を出力する回路のことを言う.しかし完璧に動作する XOR 回路を設計するのは時間がかかるので,とりあえず n ビットのうち k ビットだけ使う XOR 回路 A を作ることにした.つまり,ある i1, ... , ik が存在し,回路 A は xi1 + xi2 + ... + xik\ (mod 2)を出力する.

暫く後に今度は k ビット入力の XOR 回路が欲しくなった.何だ簡単ではないか.先ほどの回路 A を使えばよい.ただ残念なことに,回路 A がどの k ビットを使っていたのか忘れてしまった上に,回路 A の設計図も間違って削除してしまった.しかしコンパイル済みの回路 A は残っている.なので,入力 x1x2...xn を入れて回路 A を実行することで,その出力 xi1 + xi2 + ... + xik\ (mod 2) を見ることは出来る. 出来るだけ作業の時間を短くしたいので,回路 A の実行回数には上限を設定することにしよう.どうすれば回路Aが依存しているビット i1, ... , ik を見つけられるだろうか?

入出力

最初に nk がスペース区切りで与えられる.以降,プログラムは回路 A に入力を与え,その出力を読むことが出来る.例えば C/C++ で回路 A にビット列 x1x2...xn を与えるには

printf("?x1x2...xn\n"); fflush(stdout);
とする.ここで各 xi の間にスペースをいれてはならない. 次に,
scanf("%d", &v);
とすると v に対応する出力 xi1 + xi2 + ... + xik\ (mod 2) が入る. 最終的に回路 A が依存するビット i1,...,ik を出力するには
printf("!i1 i2 ...ik\n"); fflush(stdout);
とする.ここで各 ij の間はスペースを丁度 1 つずついれる.

制約

  • 1 ≤ n ≤ 10,000
  • 1 ≤ k ≤ min(10, n)
  • 各データセットごとに,回路 A の実行回数の上限は 200 回であり,それを超えると誤答 (Query Limit Exceeded) と判定される.

入出力例

入力例 1

以下の例はプログラムの入出力の例である.左の列はプログラムの出力,右の列はプログラムへの入力を時系列順に示している.最初に n k が入力として与えられる.ここでは n = 2, k = 1 である.次に回路 A に 00 という入力をいれると,回路 A は 0 を返した.次に回路 A に 01 という入力をいれると,回路 A は再び 0 を返した.このことから回路 A は 1 ビット目のみ利用していることが分かり,プログラムは 1 を解答として出力した.

プログラムの出力プログラムへの入力
2 1
?00
0
?01
0
!1

入力例 2

以下の例では,n = 2, k = 2 であり,直ちに回路 A が 1 ビット目と 2 ビット目の両方を利用していることが分かる.よってプログラムは 12 を解答として出力した.

プログラムの出力プログラムへの入力
2 2
!1 2


Source: Kyoto University Programming Contest 2011 , Kyoto, Japan, 2011-08-06
Problem Setter:  Yuichi Yoshida ,  Tester: Yasuharu Hirasawa
http://www.kupc.jp/2011.html