AT_abc355_e [ABC355E] Guess the Sum

[problemUrl]: https://atcoder.jp/contests/abc355/tasks/abc355_e この問題は **インタラクティブな問題**（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。 正整数 $ N $ および $ 0 $ 以上 $ 2^N $ 未満の整数 $ L,R(L\leq\ R) $ が与えられます。 ジャッジシステムは、$ 0 $ 以上 $ 99 $ 以下の整数からなる長さ $ 2^N $ の数列 $ A\ =\ (A_0,\ A_1,\ \dots,\ A_{2^N-1}) $ を隠し持っています。 あなたの目標は $ A_L+A_{L+1}+\dots+A_{R} $ を $ 100 $ で割った余りを求めることです。ただし、あなたは数列 $ A $ の要素の値を直接知ることはできません。 その代わりに、ジャッジシステムに対して以下の質問を行うことができます。 - $ 2^i(j+1)\leq\ 2^N $ を満たすように非負整数 $ i,j $ を選ぶ。$ l=2^ij,r=2^i(j+1)-1 $ として $ A_l+A_{l+1}+\dots+A_{r} $ を $ 100 $ で割った余りを聞く。 どのような $ A $ であっても $ A_L+A_{L+1}+\dots+A_{R} $ を $ 100 $ で割った余りを特定することができる質問回数の最小値を $ m $ とします。$ m $ 回以内の質問を行って $ A_L+A_{L+1}+\dots+A_{R} $ を $ 100 $ で割った余りを求めてください。 ### Input & Output Format この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。 最初に、整数 $ N,L,R $ を標準入力から受け取ってください。 > $ N $ $ L $ $ R $ 次に、$ A_L+A_{L+1}+\dots+A_{R} $ を $ 100 $ で割った余りを特定できるまで質問を繰り返してください。 質問は、以下の形式で標準出力に出力してください。 > $ ? $ $ i $ $ j $ ここで、$ i,j $ は以下を満たす必要があります。 - $ i,j $ は非負整数 - $ 2^i(j+1)\leq\ 2^N $ これに対する応答は、次の形式で標準入力から与えられます。 > $ T $ ここで、$ T $ は質問に対する答えで、$ l=2^ij,r=2^i(j+1)-1 $ としたとき $ A_l+A_{l+1}+\dots+A_{r} $ を $ 100 $ で割った余りです。 ただし、$ i,j $ が制約を満たしていないか、質問回数が $ m $ 回を超えた場合は $ T $ は `-1` となります。 ジャッジが `-1` を返した場合、プログラムはすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。 $ A_L+A_{L+1}+\dots+A_{R} $ を $ 100 $ で割った余りが特定出来たら、$ S $ を $ A_L+A_{L+1}+\dots+A_{R} $ を $ 100 $ で割った余りとして以下の形式で出力してください。その後、ただちにプログラムを終了してください。 > $ ! $ $ S $

N/A

N/A

### 制約 - $ 1\leq\ N\leq\ 18 $ - $ 0\leq\ L\leq\ R\leq\ 2^N-1 $ - 入力は全て整数 ### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。** - **対話の途中で誤った出力形式による出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。** - 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。 ### 入出力例 以下は、$ N=3,L=1,R=5,A=(31,41,59,26,53,58,97,93) $ の場合の入出力例です。この場合 $ m=3 $ であるため、質問を $ 3 $ 回まで行うことができます。 入力 出力 説明 `3 1 5` まず整数 $ N,L,R $ が与えられます。 `? 0 1` $ (i,j)=(0,1) $ として質問を行います。 `41` $ l=1,r=1 $ であるため、質問の答えは $ A_1=41 $ を $ 100 $ で割った余りである $ 41 $ です。ジャッジはその値を返します。 `? 1 1` $ (i,j)\ =\ (1,1) $ として質問を行います。 `85` $ l=2,r=3 $ であるため、質問の答えは $ A_2+A_3=85 $ を $ 100 $ で割った余りである $ 85 $ です。ジャッジはその値を返します。 `? 1 2` $ (i,j)\ =\ (1,2) $ として質問を行います。 `11` $ l=4,r=5 $ であるため、質問の答えは $ A_4+A_5=111 $ を $ 100 $ で割った余りである $ 11 $ です。ジャッジはその値を返します。 `! 37` 答えは $ 37 $ であるとわかったので、それを出力します。