B. 书本检测

内存限制:512 MiB 时间限制:1000 ms 题目类型:交互

题目描述

这是一道交互题,交互题是指题目的输入会根据你的输出所产生变化。

早晨一女生背着一堆书出了图书馆,结果警报响了。大妈让女生看看是哪本书把警报弄响了,那女生把书倒出来,准备一本一本地测。
大妈见状急了,立刻把书分成两份,第一份过一下,响了。又把这一份分成两份接着测,三回就找到了。
大妈用鄙夷的眼神看着女生,仿佛她不懂算法。

结果图书馆丢了 n-1 本书。

你背着一堆书出了图书馆,结果警报响了。不过你确实只错拿了一本书,但是你也不知道是哪一本。

每次测试你可以给出两个数 ,表示你把区间 之间的书拿来测试警报。之后系统会给出一个整数 ,表示猜测结果,其中 表示警报响了, 表示警报没响。你可以测试不超过 次来求出哪一本书被错拿了。

由于时间宝贵,所以你最多只有 次测试机会;

输入格式

初始输入一个数 ,表示你的一堆书的总数。

交互输入的方式:

每当你进行一次测试,就可以从标准输入流中读取一个整数,表示猜测结果,其中 表示警报响了, 表示警报没响。

当你找出错拿的书后,应当立即终止程序,此后不要再继续读入,因为你已经找到了。

输出格式

交互输出:

最多可以测试 次,对于每次测试,输出形如 ? l r 的一行,包含两个 以内的正整数 并换行

当你找出错拿的书后,输出形如 ! x 的一行并换行。其中 x 为错拿的书的编号。

注意

每次输出之后,必须刷新输出缓冲区,否则将会得到 TLE 的结果。

你只能输出一次表示已经找出错拿书的指令,并且在此之后不应继续输出,因为你已经找到了。

记得输出时要输出换行符。

刷新输出缓冲区的方式如下:

编程语言 操作方式
C/C++ fflush(stdout);
Java System.out.flush();
Python stdout.flush();
Pascal flush(output);

其它语言请参见各自文档。

下面给出 C/C++ 的一种交互方式:

int query(long long l, long long r)
{
	printf("? %lld %lld\n", l, r);
	fflush(stdout);
	int x;
	scanf("%d", &x);
	return x;
}

样例

样例输入

100
0
0
1

样例输出

? 1 1
? 2 2
? 3 3
! 3

数据范围与提示

对于样例,初始输入表示有 本书,你拿第 本书去测试,警报没有响,然后再拿第 本书去测试,警报还是没有响,拿第 本书去测试的时候警报响了,所以确定第三本书是错拿的书。

注意数据范围决定要开的数据类型