L - Interactive Sorting Editorial /

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

入出力

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

N Q

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

? c_1 c_2

ここで c_1c_2 は異なる最初の N 個の大文字のどれかでなければならない。

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

ans

ここで ans< または > である。 < のときは c_2 のほうが重く、> のときは c_1 のほうが重い。

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

! ans

ここで ansN 文字の文字列であり、最初の 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.

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:

#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