E - Coin Authentication

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

これはインタラクティブな問題です。

イルカは街中でコインが入った N 個の袋を見つけました。
i(1≦i≦N) 番目の袋の中に重さ w_i グラムのコインが 10000 枚入っています。

ここで、イルカは街で偽物コインが多く流通していることを思い出しました。
N 個の袋のうち、いくつかの袋は偽物コインだけが入った袋かもしれません。
イルカは本物コインの袋を探そうとしています。

これらのコインの見た目は全く同じですが、本物コインと偽物コインでその重さが異なります。
本物コインの重さは 9 グラム、または 11 グラムであり、偽物コインの重さは 8 グラム、10 グラム、または 12 グラムであることが知られています。
イルカは袋に入っているコインの重さ w_i を全く知りません。

イルカは友達のシャチから、はかりを借りることにしました。
はかりを利用して、コインの計測は以下の手順で行います。

  • それぞれの袋について、整数 0≦s_i≦10000 (1≦i≦N) を決めます。
  • i 番目の袋から s_i 枚のコインを取り出して、はかりに乗せます。
  • その後に計測を行い、はかりの上に乗せたコインの重さの合計を知ることができます。
  • 最後に、はかりに乗せたコインを元の袋に戻します。

しかし、シャチはとても忙しいのでイルカは 高々 10 回のコイン計測しかできません。
どの袋に本物コインが含まれているかを判定してください。

制約

  • 1≦N≦50
  • 8≦w_i≦12
  • Nw_i は全て整数

入出力

最初に、標準入力から N が以下の形式で与えられる:

N 

次に、あなたはクエリを質問して、コインの計測を行う。
このクエリは高々 10 回まで出力することができる。
各クエリでは、はかりの上に乗せるコインの枚数を以下の形式で標準出力へ出力しなければならない:

? s_1 s_2  s_N

ここで s_i は、 はかりの上に乗せる i 番目の袋のコインの枚数であり、0 以上 10000 以下の整数でなければならない。

その後、クエリの答えが標準入力から以下の形式で与えられる:

ans

ここで ans は非負の整数であり、はかりの計測結果が ans グラムであることを表す。


最後に、答えを以下の形式で出力しなければならない:

! a_1 a_2  a_N

ここで a_ii 番目の袋に入っているコインが本物コインなら 1、偽物コインなら 0 でなければならない。
なお、答えの出力はコインの計測を行う質問クエリの回数制限に含まれない。

ジャッジ

  • 出力の最後に改行を含めて出力しなければならない。そのあと、標準出力を flush しなければならない。 そうでないときは TLE の可能性がある。
  • 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
  • 出力の答えが間違っている場合の挙動は定義されていない (WAとは限らない)。

サンプル

このサンプルでは N = 5, w_1 = 8, w_2 = 9, w_3 = 10, w_4 = 11, w_5 = 12 で、答えは 0 1 0 1 0 である。

Input Output
5
? 1 0 0 0 0
8
? 0 1 0 0 0
9
? 0 0 1 0 0
10
? 0 0 0 1 0
11
? 0 0 0 0 1
12
! 0 1 0 1 0