本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-30 21:12:56

注：此题为 IO 交互题。

题目考察：交互，最短路。
题目简述：
给你三个整数 $n,l,r$，指评测机随机生成了一个长度为 $2^n$ 的序列 $\{a_{2^n}\}$（题目从 $0$ 开始计数），让你求区间 $[l,r]$ 的和对 $100$ 取模的结果 $\displaystyle(\sum_{i=l}^ra_i)\bmod 100$。
你可以问评测机若干个问题，每次以 ? l r 的形式给出，意为询问区间 $[2^ij,2^i(j+1)-1]$ 的和对 $100$ 取模的结果，若得到了答案，以 ! ans 的形式给出答案，并立即终止程序。
要求在能确定答案的情况下，问题数最少，你要按照以上描述给出答案。
数据范围：

• $n\in[1,18]\cap\mathbb N$
• $l,r\in[0,2^n-1]\cap\mathbb N$
• $l\le r$

为了方便，我们将 $[l,r+1)$ 当作题目的 $[l,r]$。
我们将这道题建模为由 $r+1$ 走到 $l$ 的最短路，我们可以由 $x$ 转移到 $x-2^i$ 和 $x+2^i$（$i\in\mathbb Z,2^i|x$），由于边权都为 $1$，所以使用 BFS 即可。
记录路径时我们记录其前驱结点即可。

这样我们就得到了路径，然后我们对其进行询问，最后输出答案即可。

代码：

#include<bits\/stdc++.h>
#define int long long
#define reg register
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(reg int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define gc getchar
#define pc putchar
#define endl '\n'
#define fi first
#define se second
using namespace std;
inl int read(){
	reg int f=1,x=0;
	reg char ch;
	while(!isdigit(ch=gc()))
		if(!(ch^'-')) f=-1;
	x=ch^48;
	while(isdigit(ch=gc())) x=(x<<1)+(x<<3)+(ch^48);
	return f*x;
}
inl void write(int x,char ch){
	if(x<0){
		pc('-');
		x=-x;
	}
	if(x>=10) write(x\/10,0);
	pc(x%10^48);
	if(ch) pc(ch);
}
inl string get(){
	char ch;
	string s="";
	while((ch=gc())=='\r'||ch=='\n'||ch==' ');
	s+=ch;
	while((ch=gc())!='\r'&&ch!='\n'&&ch!=' ') s+=ch;
	return s;
}
inl char gett(){
	char ch;
	while((ch=gc())=='\r'||ch=='\n'||ch==' ');
	return ch;
}
inl int maxx(int a,int b,int c){
	return max(a,max(b,c));
}
inl int minn(int a,int b,int c){
	return min(a,min(b,c));
}
const int N=(1<<18)+10,MOD=100;
int n,l,r,lst[N],ans,now,res;
queue<int>q;
inl void bfs(){
	q.push(l);
	while(!q.empty()){
		reg int x=q.front();
		q.pop();
		rep(i,0,__lg(n)){
			rep(j,-1,1)
				if(j){
					reg int tx=x+(1<<i)*j;
					if(tx>=0&&tx<=n&&!(~lst[tx])){
						lst[tx]=x;
						q.push(tx);
					}
				}
			if(x&(1<<i)) break;
		}
	}
}
signed main(){
	memset(lst,-1,sizeof(lst));
	n=(1<<read());
	l=read();
	r=read()+1;
	bfs();
	now=r;
	while(now!=l){
		reg int f=1,a=lst[now],b=now;
		if(a>b){
			swap(a,b);
			f=-1;
		}
		putchar('?');
		putchar(' ');
		write(__lg(b-a),' ');
		write(a\/(b-a),endl);
		fflush(stdout);
		res=read();
		(ans+=f*res+MOD)%=MOD;
		now=lst[now];
	}
	putchar('!');
	putchar(' ');
	write(ans,endl);
	return 0;
}