#E. [CZOJ 一周一测 R1 E] 绿茵战场

    交互题 1500ms 256MiB

[CZOJ 一周一测 R1 E] 绿茵战场

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

绿茵不在,战场总在。

题目背景

在 SegonOJ 的绘板大战中,拜月教成功战胜拜日教,夺去了一半以上的资源!

值得一提,画面中的 CZOI、CFS、SCZ 标志等众多内容也是与拜月教的合作。

题目描述

拜日教教皇现在手上拥有众多 token,你作为拜月教的卧底,将要舌战交互库获得 token。

拜日教现在一共掌握 n(1n109)n(1 \leq n \leq 10^9) 个 token。

拜日教教皇定义 f(x)f(x) 表示 xx 在二进制下的 11 的个数。

作为卧底来获取 token 的你,每次可使用 ? x(0x109)(0\leq x \leq 10^9) 查询 f(nx)f(n-x)f(k)f(k) 的关系;! n 输出一个答案,表示你猜测的拜日教教皇 token 数。如果错误,直接被拜日教教皇戳穿卧底身份,拜月教教皇会奖励你一个 WA。如果你说出的 token 数比拜日教教皇手中的还多,也会被戳穿并获得 WA。反之说出正确答案将会得到拜月教教皇信任,拜月教教皇会奖励你一个 AC。

我们设 k=nk=n,拜日教教皇很狡猾,每次不会告诉你你的询问正确答案。如果拜日教教皇没骗你,查询时,若 f(nx)<f(k)f(n-x)<f(k) 返回 00f(nx)=f(k)f(n-x)=f(k) 返回 11f(nx)>f(k)f(n-x)>f(k) 返回 22。若 nx<0n-x<0,那么直接忽略这个询问,表示认为你给出的 x=0x=0。如果拜日教教皇骗你了,本该输出 yy 却会输出 (y+1)mod3(y+1)\mod 3。这个骗人序列周期长度为 mm。同时,每次操作如果合法,nnxn\gets n-x,表示将 nn 修改为 nxn-x

为了不让拜日教教皇怀疑,你至多询问 6060 次。

输入格式

首先,拜月教皇会给出两个数字:cntcntmm,表示 f(k)f(k) 与序列周期长度。

? x 查询 f(nx)f(n-x)f(k)f(k) 的大小。具体返回见题目描述。

你至多可以查询 6060 次。如果超过次数则也会被戳穿卧底身份。

交互特性

在输出之后,你需要使用以下语句:

你可以使用如下语句来清空缓冲区:

  • 对于 C/C++:fflush(stdout)
  • 对于 C++:std::cout << std::flush
  • 对于 Java:System.out.flush()
  • 对于 Python:stdout.flush()
  • 对于 Pascal:flush(output)
  • 对于其他语言,请自行查阅对应语言的帮助文档。

特别的,对于 C++ 语言,在输出换行时如果你使用 std::endl 而不是 '\n',也可以自动刷新缓冲区。

输出格式

! n 输出你的答案,这将作为你的最终结果,正确则成功套取拜日教 token,错误则被戳穿身份。

2 1

2
? 0

! 3

提示

测试点编号 nn mm 特殊性质
161\sim 6 30\leq 30 10\leq 10 A\tt A
7127\sim 12 109\leq 10^9 30\leq 30
131613\sim 16 30\leq 30 10\leq 10
172017\sim 20 109\leq 10^9 30\leq 30

特殊性质 A\tt A:保证拜日教皇不会骗人。

[CZR-001] CZOJ Weekly Exercise Round 1

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-7-7 17:00
结束于
2023-7-7 22:30
持续时间
5.5 小时
主持人
参赛人数
54