F - HonestOrUnkind Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1300 点

問題文

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

シカのAtCoDeerくんは 0~N-1 の番号がついた N 人の人が集まっているのを見つけました。 この内 A 人は正直者で、残りの B(=N-A) 人は不親切な人です。 N 人の人は全員、誰が正直者で、誰が不親切な人かを把握しています。 一方、AtCoDeerくんは、正直者が A 人いて不親切な人が B 人いることしか知りません。 そこで、AtCoDeerくんはこれらの N 人に質問をして、正直者を全員特定しようとしています。 一回の質問では、AtCoDeerくんは、0≦a,b≦N-1 なる a, b を選んで、a さんに「b さんは正直者ですか?」という質問をします。

正直者は、質問に対し常に Yes か No の正しい答えを返します。 一方、不親切な人は、質問に対し Yes か No のどちらかを恣意的に選んで返します。 つまり、常に嘘をついたり、半分の確率でランダムに答えるといった単純なアルゴリズムではない可能性があります。

AtCoDeerくんは高々 2N 回質問をすることができます。質問は順番に行われ、以前の質問の結果から次の質問を決めることが出来ます。

正直者を全員特定してください。 不可能な場合(正確には、どのような 2N 回の質問をしようと、不親切な人たちがうまく返答することで、正直者の集合としてありうるものが2つ以上存在するようにできる場合)は、その旨を出力してください。

制約

  • 1≦A,B≦2000

入出力

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

A B

もし特定が不可能な場合は、即座に次のように出力し、プログラムを終了しなければならない。:

Impossible

それ以外の場合は、次に、クエリを質問する。 各クエリは、標準出力に以下の形式で出力されなければならない:

? a b

ここで a と b は 0 以上 N-1 以下の整数でなければならない。

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

ans

ここで ans は Y または N である。 Y のときは質問の答えが Yes であることを、N のときは No であることを表す。

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

! s_0s_1...s_{N-1}

ここで s_i は i 番の人が正直者なら 1、不親切な人なら 0 でなければならない。

ジャッジ

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

サンプル

このサンプルでは A = 2, B = 1 で、答えは 101 である。

Input Output
2 1
? 0 1
N
? 0 2
Y
? 1 0
Y
? 2 0
Y
? 2 2
Y
! 101

次のサンプルでは A = 1, B = 2 で、答えは Impossible である。

Input Output
1 2
Impossible

Score : 1300 points

Problem Statement

This is an interactive task.

AtCoDeer the deer came across N people. For convenience, the people are numbered 0 through N-1. Among them, A are honest and the remaining B(=N-A) are unkind. All of these N people know who are honest and who are unkind, but AtCoDeer only knows that there are A honest and B unkind people. He is trying to identify all of the honest people by asking questions to these N people. For one question, AtCoDeer selects a and b (0≤a,b≤N-1), and asks person a the following question: "Is person b honest?"

An honest person will always answer correctly by "Yes" or "No". An unkind person, however, will answer by selecting "Yes" or "No" arbitrarily. That is, the algorithm used by an unkind person may not be simple one such as always lying or giving random fifty-fifty answers.

AtCoDeer can ask at most 2N questions. He will ask questions one by one, and the responses to the previous questions can be used when deciding the next question to ask.

Identify all of the honest people. If it is impossible (more formally, if, for any strategy of asking 2N questions, there exists a strategy for unkind people to answer the questions so that there are two or more possible sets of the honest people), report that fact.

Constraints

  • 1≤A,B≤2000

Input and Output

First, A and B are given from Standard Input in the following format:

A B

If identifying the honest people is impossible, the program must immediately print the following output and terminate itself:

Impossible

Otherwise, the program shall ask questions. Each question must be written to Standard Output in the following format:

? a b

Here, a and b must be integers between 0 and N-1 (inclusive). The response to the question will be given from Standard Input in the following format:

ans

Here, ans is either Y or N. Y represents "Yes"; N represents "No".

Finally, the answer must be written to Standard Output in the following format:

! s_0s_1...s_{N-1}

Here, s_i must be 1 if person i is honest, and 0 if person i is unkind.

Judgement

  • After each output, you must flush Standard Output. Otherwise you may get TLE.
  • After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Samples

In the following sample, A = 2, B = 1, and the answer is 101.

Input Output
2 1
? 0 1
N
? 0 2
Y
? 1 0
Y
? 2 0
Y
? 2 2
Y
! 101

In the following sample, A = 1, B = 2, and the answer is Impossible.

Input Output
1 2
Impossible