No.850 企業コンテスト2位

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 58
作問者 : chocoruskchocorusk / テスター : omochana2omochana2
9 ProblemId : 2870 / 出題時の順位表

問題文

ユキコダ社主催のプログラミングコンテストが開かれました。コンテストには $1, 2, \ldots , N$ の番号がついた $N$ 人が参加し、全員に $1$ 位から $N$ 位までの相異なる順位がつきました。

ユキコダ社採用担当のあなたは、$2$ 位の人をスカウトすることにしましたが、まだコンテストの結果を知らないので、参加者たちに質問することにしました。

参加者たちは皆ひねくれ者なので、次の形式の質問にしか答えてくれません。

  • 人 $x$ と人 $y$ ($x\neq y$) ではどちらのほうが順位が上だったか?

この形式の質問を $334$ 回以下行って、$2$ 位の人の番号を特定してください。

入出力

最初に標準入力から参加者の人数 $N$ ($2\leq N\leq 300$) が以下のように与えられる。

$N$

続いて、あなたのプログラムは標準出力に以下の形式の質問クエリを $334$ 回まで行うことができる。

? $x\ y$

この出力は、人 $x$ と人 $y$ ではどちらのほうが順位が上だったか質問することを表す。$x$, $y$ は整数で、$1\leq x, y\leq N$, $x\neq y$ を満たさなければならない。

質問クエリを行うと、その回答が以下の形式で標準入力から与えられる。

$ans$

人 $x$ のほうが順位が上 (順位の数が小さい) ならば $ans=x$ であり、そうでないなら $ans=y$ である。

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

! $ans$

今までの質問クエリの内容から $2$ 位の人の番号をただ一つに決定できて、その番号が $ans$ に一致するとき、正解となる。

注意

  • 出力のあと、標準出力をflushしなければならない。
  • 質問クエリの後、その結果を必ず受け取ること。
  • 答えを出力したあとはプログラムをすぐに終了しなければならない。
  • テストケースの中には、質問クエリの回答がこれまでの質問クエリの内容により変化するものがあるが、回答がこれまでの質問クエリの内容に矛盾することはない。

サンプル

サンプル1
入力
4
4
2
1
出力
? 1 4
? 2 4
? 1 3
! 4

参加者が $4$ 人で、$1$ 位, $2$ 位, $3$ 位, $4$ 位がそれぞれ人 $2$, 人 $4$, 人 $1$, 人 $3$ で固定の場合の入出力例です。

  • 人 $1$ と人 $4$ について、順位が上なのは人 $4$ です。
  • 人 $2$ と人 $4$ について、順位が上なのは人 $2$ です。
  • 人 $1$ と人 $3$ について、順位が上なのは人 $1$ です。
  • $3$ 回の質問クエリの内容から $2$ 位の人の番号は $4$ であると確定するので、正解となります。

同じケースの不正解の入出力例を挙げます。

入力
4
1
2
2
出力
? 1 3
? 2 4
? 1 2
! 4

この出力では、$2$ 位の人の番号を $4$ と正しく答えていますが、質問クエリの内容からは $2$ 位の人の番号が $1$ か $4$ かわからないので、この出力は不正解となります

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。