$\lceil$ 御坂美琴 $\rfloor$ 正在学习 C 语言,她实在想不到这些题应该怎么写,于是她通过意念获取到了 $\lceil$ 初春饰利 $\rfloor$ 一份已经 $\textsf{AC}$ 了的代码,但一想到有被查重的风险,她决定修改一下再提交上去。
这份代码一共有 $n$ 个语句,查重红线是 $m$ 个语句,也就是如果她提交的代码与 $\lceil$ 初春饰利 $\rfloor$ 的代码有 $x$ 个语句不同,当 $x\leq m$ 的时候会触发 $1$ 次预警。
$x=0$ 的时候一定会触发预警,$x \gt n$ 的时候一定不会触发预警。
预警次数达到 $3$ 次就算作抄袭,成绩清零!
如果提交次数超过 $[\sqrt{2n}~]$,就会被助教注意到并人工查重,同样会被发现抄袭,成绩清零!(其中 $[~~]$ 表示四舍五入取整)
现在她想要通过多次试探性提交的方式,在成绩不被清零的前提下,猜出 $m$ 的值究竟是多少,你能帮帮她嘛?
我们已经帮你实现好了两个函数 submit(x) 和 guess(x),请你利用这两个函数帮她猜出 $m$ 的值。如果在 成绩不被清零 的前提下猜对了,你就能够 AC 本题,否则不能。
submit(x) 表示你提交了一份有 x 个语句不同的代码,可以调用不超过 $[\sqrt{2n}~]$ 次。其返回值为本次提交的查重结果。
guess(x) 表示你最终猜测 $m$ 的值为 x,只能调用 $1$ 次,调用后我们会立即结束你的程序并判断是否猜测正确。这个函数没有返回值。
这两个函数的参数 $x$ 必须是一个 int 型变量,变量名不必为 $x$。
submit(x) 的返回值是 int 类型,其返回值含义如下:
| 返回值 | 含义 |
|---|---|
1 | 本次提交触发了预警 |
0 | 本次提交未触发预警 |
-1 | 成绩被清零(预警次数达到了 $3$ 次,或提交次数超过了 $[\sqrt{2n}~]$) |
(这是两个函数的实现,但你不必关心具体是如何实现的,更不要试图改动,以免发生意外错误~)
#define submit(x) (printf("%d\n",x),fflush(stdout),scanf(" "),(int)(getchar()-'0'))
#define guess(x) return (printf("m=%d\n",x),fflush(stdout))
$1$ 个正整数 $n$,保证 $3 \leq n \leq 10000$。
无
100
submit(x) 返回值样例0
0
0
0
1
#define submit(x) (printf("%d\n",x),fflush(stdout),scanf(" "),(int)(getchar()-'0'))
#define guess(x) return (printf("m=%d\n",x),fflush(stdout))
#include<stdio.h>
int main()
{
int n;
scanf("%d", &n); //第一步先读入 n
for(int i = n; i >= 0; i--)
{
int jud = submit(i); // jud 中获得了这次提交是否预警的反馈
if(jud == 1)
{
guess(i); //猜测最终结果为当前的 i
}
}
return 0; //这行可以省略,因为 guess(i) 自带 return
}
返回值样例或许可以来源于这个程序,这里每次 submit(i) 对应的不同语句数(i 的值)分别为 $100,99,98,97,96$,反馈依次为 $0,0,0,0,1$,说明查重红线 $m=96$。
但这是一个只能通过样例的示例,用来演示这个程序的结构。
如果 $n=100,m=1$ 那么这个示例程序显然因为提交次数过多就不能 AC 了!