{"problem":{"name":"「Wdoi-2」死亡之后愈发愉悦","description":{"content":"**【这是一道交互题】** 定义 $f(x)$ 表示严格大于 $x$ 的最小的完全平方数，定义 $g(x)$ 为小于等于 $x$ 的最大的完全平方数。例如，$f(1)=f(2)=g(4)=g(8)=4$。 一个正整数是“可爱”的，当且仅当 $x-g(x)<f(x)-x$，例如，$1,5,11$ 是可爱的正整数，而 $3,8,15$ 不是。 为了倾听小神灵的愿望，主角组需要向神子询问。小神灵有","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8541"},"statements":[{"statement_type":"Markdown","content":"**【这是一道交互题】**\n\n定义 $f(x)$ 表示严格大于 $x$ 的最小的完全平方数，定义 $g(x)$ 为小于等于 $x$ 的最大的完全平方数。例如，$f(1)=f(2)=g(4)=g(8)=4$。\n\n一个正整数是“可爱”的，当且仅当 $x-g(x)<f(x)-x$，例如，$1,5,11$ 是可爱的正整数，而 $3,8,15$ 不是。\n\n为了倾听小神灵的愿望，主角组需要向神子询问。小神灵有一个最喜欢的正整数 $a$，神子可以根据灵梦给出的 $x\\quad(x\\in[0,10^9])$，向小神灵询问，而小神灵只能回答她，$a+x$ 是不是可爱的正整数（$\\text{cute number}$）。\n\n请通过适当的询问找出 $a$。\n\n## Input\n\n第一行有一个正整数 $T$，表示数据组数。每一组之间互相独立。\n\n接下来，对于每一组数据，你将可以进行以下两种操作：\n\n- $\\verb!? x!$：询问 $a+x$ 是否是 $\\text{cute number}$。要注意，$x$ 的值应当在 $[0,10^9]$ 以内。对于正确的询问，交互库会返回一个数字 $1$ 或者 $0$，表示 $a+x$ 是/不是 $\\text{cute number}$。\n- $\\verb|! a|$：报告你发现的 $a$。如果你给出的 $a$ 正确，该组数据结束。注意：报告操作不计入询问操作的总次数。\n\n如果你的询问次数超过了 $100$，或者 $x$ 不符合数据范围，或者你报告的 $a$ 不正确，交互库会返回一个数字 $-1$。此时你应当立即结束程序，否则可能发生不可预知的错误。\n\n## Background\n\n落樱缤纷春不待，如果错过了这次机会，可能得等到紫藤绽放的春夏之际才能赏花了。  \n但是两人依然无心在樱花树下席地而宴。\n\n因为正体不明的灵体在两人面前倏现骤消的飘浮着。  \n后来才明白这些四处飘浮的正体不明灵体，既非普通幽灵，也不是前阵子出现的怨灵。  \n这些是神灵。本应超脱为神的灵体。\n\n一般而言，神灵多半居住在神社里，其实它们是随处可见的没有固定型态的灵体。  \n这些神灵让她们困惑不已。\n\n超乎常人的强烈人欲、想法、恐惧与情感，是神灵出现的原因。一般而言，神灵很少危害人类，如果没有强烈的欲望。例如祈求丰收，或是除厄避邪等，是不会产生神灵的……\n\n小神灵指引着灵梦与魔理沙深入命莲寺的地底，与千年复苏的敌人交手。从命莲寺墓地到莲池中央的梦殿大祀庙，从彷徨的亡灵到极具传说色彩的圣德太子，从欲望加速到小小的欲望星空，一切都显得那么不可思议。\n\n「死亡之后，才能得到更加绚烂的重生。」\n\n[samples]\n\n## Note\n\n### 样例解释\n\n样例当中的过程仅供参考。\n\n样例当中，$a=114514$，是 $\\text{cute number}$（因为 $338^2\\le 114514 <339^2$，而 $114514-338^2=270<339^2-114514=407$）。\n\n同样地，$a+0,a+1,a+2,a+3,a+10$ 均为 $\\text{cute number}$。而 $a+100=114614$ 不是 $\\text{cute number}$，因为 $338^2\\le 114614 <339^2$，而 $114614-338^2=370\\ge 339^2-114614=307$。\n\n### 数据范围及约定\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\bm{a\\le } & \\bm{T\\le} & \\textbf{特殊性质} & \\textbf{分值}\\\\\\hline\n1 & 100 & 100 & - & 10\\\\\\hline\n3 & 10^9 & 2\\times 10^3 & -  & 20\\\\\\hline\n2 & 10^{12} & 2\\times 10^3 & \\textbf{A}  & 30\\\\\\hline\n4 & 10^{12} & 2\\times 10^3 & -  & 40\\\\\\hline\n\\end{array}\n$$\n\n**特殊性质** $\\textbf{A}$：保证 $a$ 是 $\\text{cute number}$。\n\n对于全部数据，保证 $1\\le a\\le 10^{12}$。你发起的询问当中，$x$ 的值应当在 $[0,10^9]$ 以内。\n\n---\n\n此外，你每个测试点的得分还与该测试点所有询问次数的最大值有关。具体而言，设某个测试点你询问操作一共进行了 $\\text{max\\_count}$ 次。\n\n- 若 $\\text{max\\_count}< 64$，你将获得该测试点 $100\\%$ 的分数；\n- 若 $64\\le \\text{max\\_count}< 81$，你将获得该测试点 $50\\%$ 的分数；\n- 若 $81\\le \\text{max\\_count}< 100$，你将获得该测试点 $20\\%$ 的分数；\n- 若 $\\text{max\\_count}\\ge 100$，你将不能获得该测试点的分数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8541","tags":["倍增","二分","洛谷原创","交互题","Special Judge","O2优化","洛谷月赛"],"sample_group":[["1\n\n1\n\n1\n\n1\n\n1\n\n1\n\n0\n\n0\n\n1","\n? 0\n\n? 1\n\n? 2\n\n? 3\n\n? 10\n\n? 100\n\n? 233\n\n? 1919810\n\n! 114514"]],"created_at":"2026-03-03 11:09:25"}}