Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
これはインタラクティブ形式の例題です。初心者向け問題ではありませんので注意してください。
初心者の方は、AtCoder Beginners Selectionに挑戦してみてください!
最初の N 個の大文字でラベルの付いた N 個のボールがあります。 どの二つのボールの重さも異なります。
あなたは Q 回クエリを質問することができます。 各クエリでは、二つのボールの重さを比べることができます。(詳しくは入出力セクションを見てください)
ボールを軽い順にソートしてください。
制約
- (N, Q) = (26, 1000), (26, 100), (5, 7) のいずれかである。
部分点
三つのテストセットがある。各セットは 100 点ずつである。
- テストセット 1: N = 26, Q = 1000
- テストセット 2: N = 26, Q = 100
- テストセット 3: N = 5, Q = 7
入出力
最初に、標準入力から N と Q が以下の形式で与えられる:
N Q
次に、あなたは Q 回以下クエリを質問する。 各クエリは、標準出力に以下の形式で出力されなければならない:
? c_1 c_2
ここで c_1 と c_2 は異なる最初の N 個の大文字のどれかでなければならない。
次に、クエリの答えが標準入力から以下の形式で与えられる:
ans
ここで ans は <
または >
である。
<
のときは c_2 のほうが重く、>
のときは c_1 のほうが重い。
最後に、答えを以下の形式で出力しなければならない:
! ans
ここで ans は N 文字の文字列であり、最初の N 個の大文字を軽い順に並べたものでなければならない。
ジャッジ
- 出力のあと、標準出力を flush しなければならない。 そうでないときは
TLE
の可能性がある。 - 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
- 出力の答えが間違っている場合の挙動は定義されていない (
WA
とは限らない)。
コード例
以下のコードは、C++ で 100 点を獲得するための例です。部分点を取得可能なコードなので、提出するとWAになります。
#include <cstdio> #include <string> using namespace std; int main(void){ int N,Q,i,j; scanf("%d%d", &N, &Q); string s; for(i=0;i<N;i++) s += (char)('A' + i); for(i=0;i<N;i++) for(j=0;j<N-1;j++){ printf("? %c %c\n", s[j], s[j+1]); fflush(stdout); char ans; scanf(" %c", &ans); if(ans == '>') swap(s[j], s[j+1]); } printf("! %s\n", s.c_str()); fflush(stdout); return 0; }
サンプル
このサンプルでは N = 3, Q = 10 で、答えは BAC
である。
Input | Output |
---|---|
3 10 | |
? A B | |
> | |
? C B | |
> | |
? A C | |
< | |
! BAC |
Score : 300 points
Problem Statement
This is an interactive task. Please note that these are not beginner questions.
If you are a beginner, try the AtCoder Beginners Selection!
There are N balls labeled with the first N uppercase letters. The balls have pairwise distinct weights.
You are allowed to ask at most Q queries. In each query, you can compare the weights of two balls (see Input/Output section for details).
Sort the balls in the ascending order of their weights.
Constraints
- (N, Q) = (26, 1000), (26, 100), or (5, 7).
Partial Score
There are three testsets. Each testset is worth 100 points.
- In testset 1, N = 26 and Q = 1000.
- In testset 2, N = 26 and Q = 100.
- In testset 3, N = 5 and Q = 7.
Input and Output
First, you are given N and Q from Standard Input in the following format:
N Q
Then, you start asking queries (at most Q times). Each query must be printed to Standard Output in the following format:
? c_1 c_2
Here each of c_1 and c_2 must be one of the first N uppercase letters, and c_1 and c_2 must be distinct.
Then, you are given the answer to the query from Standard Input in the following format:
ans
Here ans is either <
or >
.
When ans is <
, the ball c_2 is heavier than the ball c_1, and otherwise the ball c_1 is heavier than the ball c_2.
Finally, you must print the answer to Standard Output in the following format:
! ans
Here ans must be a string of length N, and it must contain each of the first N uppercase letters once. It must represent the weights of the balls in the ascending order.
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
).
Sample Code
Here is a sample solution for 100 points. The code is obtainable for partial points, so submitting it will result in a WA.
#include <cstdio> #include <string> using namespace std; int main(void){ int N,Q,i,j; scanf("%d%d", &N, &Q); string s; for(i=0;i<N;i++) s += (char)('A' + i); for(i=0;i<N;i++) for(j=0;j<N-1;j++){ printf("? %c %c\n", s[j], s[j+1]); fflush(stdout); char ans; scanf(" %c", &ans); if(ans == '>') swap(s[j], s[j+1]); } printf("! %s\n", s.c_str()); fflush(stdout); return 0; }
Sample
In this sample N = 3, Q = 10, and the answer is BAC
.
Input | Output |
---|---|
3 10 | |
? A B | |
> | |
? C B | |
> | |
? A C | |
< | |
! BAC |