問題一覧 > 通常問題

No.1306 Exactly 2 Digits

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 45
作問者 : butsurizukibutsurizuki / テスター : hirakich1000000007hirakich1000000007 harady_a_humanharady_a_human
8 ProblemId : 5482 / 出題時の順位表
問題文最終更新日: 2020-12-03 01:50:56

メモ

これはAdvent Calendar Contest 2020の3日目用の問題です。
Codeforces Round #654(Div.2) の没問のうちのひとつです。

問題文

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

$A=\{A_1,A_2,...,A_{N^2-N}\}$ は $\{N,N+1,...,N^2-1\}$ を丁度 $1$ つずつ含む順列です。 (これらは $N$ 進法で丁度 $2$ 桁の数です。)
以下のクエリを用いて、この順列を特定してください。

? $i$ $j$
  1. $p = \lfloor A_i/N \rfloor - \lfloor A_j/N \rfloor $とする。直感的には、$p$ を $N$ 進法での( $A_i$ の $N$ の位) $-$ ( $A_j$ の $N$ の位)とする。
  2. $q = A_i\%N - A_j\%N$ とする。直感的には、$q$ を $N$ 進法での( $A_i$ の $1$ の位) $-$ ( $A_j$ の $1$ の位)とする。
  3. もし $p>q$ であるなら、 $p,q$ を入れ替える。
  4. $p$,$q$ の組をこの順に空白区切りで返答する。
このクエリは、高々 $1.5 \times (N^2-N)$ 回(この値は必ず整数になります)しか用いることができません。これを超えて用いると不正解となります。(判定がWAであるとは保証されません。)

! $A_1$ $A_2$ ... $A_{N^2-N}$
特定した数列を出力するクエリです。この出力の後、プログラムは直ちに終了される必要があります。

入出力

はじめに、整数 $N$ が $1$ 行で与えられます。 $N$ は $2 \le N \le 50$ である整数です。
その後、あなたはいくつかのクエリを実行することができます。各クエリ毎に $1$ 行に出力し、最後に改行してください。
? クエリごとに、返答が $1$ 行で与えられます。
! クエリに対しては、返答はありません。クエリを出力した後、直ちにプログラムを終了してください。
出力ごとに、プログラム内でflushを行う必要があります。 flushの方法について、一部の言語については、こちらの例を参照することができます。

注意

この問題のジャッジは、適応的(adaptive)である可能性があります。
ジャッジが適応的であるとは、以下のような項目を満たすようなジャッジを指します。

  • ジャッジは、最初、何らかの解を想定して、提出されたプログラムへの返答を行う。
  • ジャッジは、任意のタイミングで、今までの返答と整合性がとれる限り、想定している解を変更する可能性がある。
詳しくはサンプルの例も参照してください。

サンプル

サンプル1
入力
2

-1 0
出力

? 2 1

! 3 2

このケースでは、 $A= \{ 3,2 \}$ です。
? 2 1 に対して、はじめ、 $p=0$ , $q=-1$ となります。
しかし、 $p>q$ であるので、最終的な返答は -1 0 となります。
最終的な出力 $\{3,2\}$ は正しく、判定はACとなります。

サンプル2
入力
3

1 2
出力

? 4 1

! 3 5 4 8 7 6

このケースでは、 $A= \{ 3,5,4,8,7,6 \}$ です。
? 4 1 に対して、はじめ、 $p=1$ , $q=2$ となります。
$p \le q$ であるので、最終的な返答は 1 2 となります。
最終的な出力 $\{3,5,4,8,7,6\}$ は正しいものの、ジャッジの出力と整合性の取れる数列として、他にも、 $\{ 3,6,7,8,4,5 \}$ などが考えられます。
よって、正誤判定時に数列 $A$ が差し替えられ、 不正解の判定を受け取る可能性があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。