E - Guess the Sum Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

正整数 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 で割った余りを求めてください。

制約

  • 1\leq N\leq 18
  • 0\leq L\leq R\leq 2^N-1
  • 入力は全て整数

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

最初に、整数 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

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を 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 であるとわかったので、それを出力します。

Score : 500 points

Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).

You are given a positive integer N and integers L and R such that 0 \leq L \leq R < 2^N. The judge has a hidden sequence A = (A_0, A_1, \dots, A_{2^N-1}) consisting of integers between 0 and 99, inclusive.

Your goal is to find the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. However, you cannot directly know the values of the elements in the sequence A. Instead, you can ask the judge the following question:

  • Choose non-negative integers i and j such that 2^i(j+1) \leq 2^N. Let l = 2^i j and r = 2^i (j+1) - 1. Ask for the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100.

Let m be the minimum number of questions required to determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100 for any sequence A. You need to find this remainder within m questions.

Constraints

  • 1 \leq N \leq 18
  • 0 \leq L \leq R \leq 2^N - 1
  • All input values are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).

First, read the integers N, L, and R from Standard Input:

N L R

Then, repeat asking questions until you can determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. Each question should be printed in the following format:

? i j

Here, i and j must satisfy the following constraints:

  • i and j are non-negative integers.
  • 2^i(j+1) \leq 2^N

The response to the question will be given in the following format from Standard Input:

T

Here, T is the answer to the question, which is the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100, where l = 2^i j and r = 2^i (j+1) - 1.

If i and j do not satisfy the constraints, or if the number of questions exceeds m, then T will be -1.

If the judge returns -1, your program is already considered incorrect. In this case, terminate the program immediately.

Once you have determined the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100, print the remainder S in the following format and terminate the program immediately:

! S

Notes

  • At the end of each output, print a newline and flush Standard Output. Otherwise, the verdict may be TLE.
  • If your output is malformed or your program exits prematurely, the verdict will be indeterminate.
  • After printing the answer, terminate the program immediately. Otherwise, the verdict will be indeterminate.

Example

Here is an example for N=3, L=1, R=5, and A=(31, 41, 59, 26, 53, 58, 97, 93). In this case, m=3, so you can ask up to three questions.

Input Output Description
3 1 5 First, the integers N, L, and R are given.
? 0 1 Ask the question with (i, j) = (0, 1).
41 l=1 and r=1, so the response is the remainder when A_1=41 is divided by 100, which is 41. The judge returns this value.
? 1 1 Ask the question with (i, j) = (1, 1).
85 l=2 and r=3, so the response is the remainder when A_2 + A_3 = 85 is divided by 100, which is 85. The judge returns this value.
? 1 2 Ask the question with (i, j) = (1, 2).
11 l=4 and r=5, so the response is the remainder when A_4 + A_5 = 111 is divided by 100, which is 11. The judge returns this value.
! 37 The answer is 37, so print this value.