問題一覧 > 教育的問題

No.2753 鳩の巣原理

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 59
作問者 : 👑 p-adic / テスター : Moss_Local
2 ProblemId : 10025 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-07 09:35:32

問題文

この問題はリアクティブ形式の(ジャッジ側のプログラムと対話的に実行する必要がある)問題です。

 

入力の最初に 22 以上の 整数 NN が与えられます。

 

鳩の巣大好きbot鳩の巣が大好きなbotです。

鳩の巣大好きbot鳩の巣NN 個持っており、それらを NN 以下の各正整数 ii で番号づけ鳩の巣 ii と呼んで大切にしています。

しかし NN 個の鳩の巣にそれぞれ何羽かの鳩が住み着いてしまいました。あなたはどの鳩の巣に何羽の鳩が住み着いているかを知りませんが、鳩の巣大好きbotから以下の情報を得ました。

  • NN 未満の各正整数 ii に対し、鳩の巣 ii に住み着いている鳩の数は鳩の巣 i+1i+1 に住み着いている鳩の数以下の正整数である。
  • 鳩の巣 NN に住み着いている鳩の数は NN 未満の正整数である。

あなたはその情報をもとに、住み着いている鳩の数が等しい 22 つの相異なる鳩の巣が存在するのではないかと推測しました。

 

そこで、以下の一連のやり取りをちょうど 1010 回行います。

  • あなたは NN 以下の正整数 ii を選び、鳩の巣 ii に何羽の鳩が住み着いているかを鳩の巣大好きbotに尋ねる。(既に尋ねて知っている場合でも再度尋ねて構わない)
  • 鳩の巣大好きbot鳩の巣 ii に何羽の鳩が住み着いているかをあなたに答える。

その後、住み着いている鳩の数が等しい 22 つの相異なる鳩の巣が存在するか否かを判定し、存在する場合はそのような鳩の巣11 組求めてください。

入出力

1010 以下の各正整数 qq に対し、qq 回目のやり取りであなたが選ぶ正整数を iqi_q と置きます。

 

最初に鳩の巣の個数 NN が標準入力から 11 行で与えられます。

NN

その後でちょうど 1010 回のやり取りをしてください。1010 以下の各正整数 qq に対し、qq 回目のやり取りは標準入出力を用いて以下の形式で行います:

  • まず?iqi_q を半角空白区切りで 11 行で(出力全体の qq 行目に)出力してください。
  • ? iqi_q
    
  • 続いて鳩の巣 iqi_q に住み着いている鳩の数が 11 行で(入力全体の 1+q1+q 行目に)与えられます。
  • (鳩の巣 iqi_q に住み着いている鳩の数)
    

最後にあなたはこの問題に対する答えを標準出力に以下の形式で出力してください:

  • 住み着いている鳩の数が等しい 22 つの相異なる鳩の巣が存在しないならば、Noと(出力全体の 1111 行目に)出力してください。
  • No
    
  • 住み着いている鳩の数が等しい 22 つの相異なる鳩の巣が存在するならば、そのような 22 つの鳩の巣の番号の一例をそれぞれ i,ji, j と置き、Yesi,ji,j を半角空白区切りで(出力全体の 1111 行目に)出力してください。
  • Yes ii jj
    

最後に改行してください。

制約

入力は以下の制約を満たします:

  • NN2N1032 \leq N \leq 10^3 を満たす整数である。
  • 1010 回のやり取りにおける入力は問題文に記載されている以下の情報と整合的であり、やり取りの前後でどの鳩の巣に何羽の鳩が住み着いているかは変化しない。
    • NN 未満の各正整数 ii に対し、鳩の巣 ii に住み着いている鳩の数は鳩の巣 i+1i+1 に住み着いている鳩の数以下の正整数である。
    • 鳩の巣 NN に住み着いている鳩の数は NN 未満の正整数である。

注意

リアクティブ形式の問題に慣れてない方は、リアクティブ形式の問題についてのまとめも参考にしてください。

この問題において、以下の指示に従っていない提出のジャッジ結果は保証しません:

  • 出力は指定された形式に厳格に従ってください。例えば余計な空白を入れたりしないでください。
  • 出力を行うたびに末尾に改行を入れて標準出力をflushしてください。
  • この問題に対する答えを出力した後はプログラムをすぐに終了させてください。

サンプル

以下は N=10N=10 としてやり取りが始まった場合の対話の一例です。

入力 出力 説明
? 1 あなたは鳩の巣 11 に住み着いている鳩の数を尋ねました。
1 鳩の巣大好きbot鳩の巣 11 に住み着いている鳩の数が 11 であると答えました。
? 2 あなたは鳩の巣 22 に住み着いている鳩の数を尋ねました。
2 鳩の巣大好きbot鳩の巣 22 に住み着いている鳩の数が 22 であると答えました。
? 3 あなたは鳩の巣 33 に住み着いている鳩の数を尋ねました。
3 鳩の巣大好きbot鳩の巣 33 に住み着いている鳩の数が 33 であると答えました。
? 4 あなたは鳩の巣 44 に住み着いている鳩の数を尋ねました。
4 鳩の巣大好きbot鳩の巣 44 に住み着いている鳩の数が 44 であると答えました。
? 5 あなたは鳩の巣 55 に住み着いている鳩の数を尋ねました。
5 鳩の巣大好きbot鳩の巣 55 に住み着いている鳩の数が 55 であると答えました。
? 6 あなたは鳩の巣 66 に住み着いている鳩の数を尋ねました。
6 鳩の巣大好きbot鳩の巣 66 に住み着いている鳩の数が 66 であると答えました。
? 7 あなたは鳩の巣 77 に住み着いている鳩の数を尋ねました。
7 鳩の巣大好きbot鳩の巣 77 に住み着いている鳩の数が 77 であると答えました。
? 8 あなたは鳩の巣 88 に住み着いている鳩の数を尋ねました。
8 鳩の巣大好きbot鳩の巣 88 に住み着いている鳩の数が 88 であると答えました。
? 9 あなたは鳩の巣 99 に住み着いている鳩の数を尋ねました。
9 鳩の巣大好きbot鳩の巣 99 に住み着いている鳩の数が 99 であると答えました。
? 10 あなたは鳩の巣 1010 に住み着いている鳩の数を尋ねました。
9 鳩の巣大好きbot鳩の巣 1010 に住み着いている鳩の数が 99 であると答えました。
Yes 9 10 あなたは鳩の巣 99 に住み着いている鳩の数と鳩の巣 1010 に住み着いている鳩の数が等しいと分かったので、そう答えました。

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