← 返回题目列表

AtCoder · abc355_e

H. 猜总和

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

这是一个 交互问题 (您的程序通过输入和输出与法官交互)。

给你一个正整数 N 和整数 L 和 R 这样 0 \leq L \leq R < 2^N。法官有一个隐藏的序列 A = (A_0, A_1, \dots, A_{2^N-1}) 由之间的整数组成 0 和 99,包括在内。

你的目标是找到余数 A_L + A_{L+1} + \dots + A_R 除以 100。但是,您无法直接知道序列中元素的值 A。相反,您可以向法官提出以下问题:

  • 选择非负整数 i 和 j 这样 2^i(j+1) \leq 2^N。让 l = 2^i j 和 r = 2^i (j+1) - 1。询问剩余时间 A_l + A_{l+1} + \dots + A_r 除以 100.

让 m 是确定剩余部分所需的最少问题数 A_L + A_{L+1} + \dots + A_R 除以 100 对于任何序列 A。您需要在其中找到余数 m 问题。

约束

  • 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 是问题的答案,即当 A_l + A_{l+1} + \dots + A_r 除以 100,其中 l = 2^i j 和 r = 2^i (j+1) - 1.

If i 和 j 不满足约束条件,或者问题数量超过 m,那么 T 将是 -1.

如果法官返回 -1,您的程序已被认为不正确。在这种情况下,请立即终止程序。

一旦你确定了余数 A_L + A_{L+1} + \dots + A_R 除以 100,打印余数 S 格式如下并立即终止程序:

! S

注释

  • 在每个输出的末尾,打印换行符并刷新标准输出。否则,判决可能是 TLE.
  • 如果您的输出格式错误或您的程序过早退出,则结论将是不确定的。
  • 打印答案后,立即终止程序。否则,判决将是不确定的。

示例

这是一个示例 N=3, L=1, R=5,和 A=(31, 41, 59, 26, 53, 58, 97, 93)。在这种情况下, m=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,所以打印这个值。