luogu#P11145. 「SFMOI Round I」Strange Homura Game

    ID: 15070 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>洛谷原创交互题Special JudgeO2优化洛谷月赛Ad-hoc

「SFMOI Round I」Strange Homura Game

题目背景

English statement. You must submit your code at the Chinese version of the statement.

伝えたいコトバは たったひとつ / 想要传达的言语 唯有一个
キミがいたから 強くなれた / 因有你在 我变坚强了
2 人ならどんな空も飛べるね / 只要两人一起就能任意飞翔
キミをいつでも 信じてるから / 因为一直都 坚信着你
ずっとずっと夢を見ていよう / 能同做此梦不复醒吧

题目描述

本题和 B1 是不同的问题,请分别仔细阅读两题题面。

这是一道交互题。

提示:我们在题目描述的最后提供了一份简要的、形式化描述的题面。

焰和圆在玩游戏。

焰在心中想了一个正整数 mm,让圆猜出 mm 的值。当然,焰不会为难圆,所以 2m1017\textcolor{red}{2}\le m\le 10^{17}。焰不会作弊,也就是说,焰不会悄悄更换想好的数字。

圆可以问焰:对于非负整数 xxxmodmx\bmod m 的值是多少。圆需要用最少的询问次数来猜出 mm 的值。(为了得到全部分数,最多只能使用 22 次询问。)

焰一共和圆玩了 TT 次游戏。圆的数学很好,在 ε\varepsilon 秒内就秒了这题,但是她在军训,于是她找来了你,来帮她猜出这 TT 次游戏的答案。

形式化地:有一个隐藏的正整数 m[2,1017]m\in [\textcolor{red}{2},10^{17}]。每次询问给定非负整数 xx,回答 xmodmx\bmod m。用最少的询问次数找出 mm。共有 TT 组测试数据。mm 的数值在事先确定,不会根据询问变化,也就是说,交互库是非适应性的

【实现细节】

对于每个测试点,输入一行一个正整数 TT,表示游戏次数。

对于每组测试数据,你可以用以下的格式发起一次询问:

  • ? x\texttt{? }x:询问 xmodmx\bmod m 的值。你需要保证 xx非负整数,且 x[0,1018]x \in \textcolor{red}{ [0,10^{18}]}

    从标准输入流读入一个整数表示答案。特别地,若整数是 -1\texttt{-1},你的程序已经被判定为 Wrong Answer\texttt{Wrong Answer},此时你需要立刻终止程序。

你可以用以下的格式回答答案:

  • ! m\texttt{! }m:回答 mm 的值。

在发起询问后,需要刷新缓冲区,否则可能导致 TLE。

  • 在 C++ 中,使用 fflush(stdout)cout.flush()。 特别地,利用 std::endl 来换行也会刷新缓冲区。
  • 在 Pascal 中,使用 flush(output)
  • 在 Python 中,使用 stdout.flush()
  • 对于其它语言,可自行查阅文档。

输入格式

见【实现细节】。

输出格式

见【实现细节】。

1

0

1

? 5

? 1

! 5

提示

数据范围

对于 100%100\% 的数据,保证 1T1001\le T\le 100mm 为正整数,2m1017\textcolor{red}{2}\le m\le 10^{17}

评分方式

记单个测试点中,你的询问次数的最大值为 QQ。则得分 score\mathrm{score} 如下所示:

$$\begin{aligned} \mathrm{score}=\begin{cases} 0, & Q\in [101,+\infty) \\ 30, & Q\in [3,101) \\ 50, & Q\in [0,3) \\ \end{cases} \end{aligned} $$

本题得分为所有测试点得分的最小值。