题目描述
题目译自 BalticOI 2018 Day1「Worm Worries」
本题是一道交互题。
在一个三维空间(我们限制大小为 N×M×K)内,每个点都有一个正整数参数,记这个参数为 H[x,y,z](保证 1⩽x⩽N ,1⩽y⩽M ,1⩽z⩽K 且每个参数都不超过 109)。你最多可以询问 Q 次,找到一个点,使得这个点的参数不小于它周围与它有公共边的所有点的参数,即:
H[x,y,z]⩾max(H[x+1,y,z], H[x−1,y,z], H[x,y−1,z], H[x,y−1,z], H[x,y,z+1], H[x,y,z−1]).
特别地,当一个点不在空间直角坐标系的第一卦限内时,它的参数为 0。
输入格式
请使用标准输入输出流与交互库进行交互。你可以向交互库询问最多 Q 次,每次可以询问一个点的参数。
输入的第一行包含四个整数 N,M,K,Q (请忽略这一行的其他参数)。在此之后,你可以向交互器提出至多 Q 行形如 ? x y z
的询问,表示「询问坐标为 (x,y,z) 的点的参数是多少」。对于每一组询问,交互器会输出一行一个整数表示坐标为 (x,y,z) 的点的参数。
当你找到一组解时,输出一行 ! x y z
表示你找到的答案是 (x,y,z),并终止程序。此时交互器不会有任何输出。
所有坐标必须满足 1⩽x⩽N,1⩽y⩽M,1⩽z⩽K。如果不满足坐标的限制、询问不符合格式或询问超过了 Q 行,交互器会输出 -1
并退出,此时你的程序也应该退出。否则你可能会得到 Runtime Error
或 Time Limit Exceeded
的判定结果。
请注意,你必须在每一次询问之后手动刷新缓存,否则你的程序将会超时,对于各语言,刷新缓存的方法如下:
- Java: 调用
System.out.println()
会自动刷新缓存;
- Python: 调用
print()
会自动刷新缓存;
- C++:
cout << endl
可以输出一个换行并刷新缓存。如果使用 printf
,请使用 fflush(stdout)
;
- Pascal: 调用
Flush(Output)
。
为了帮助你更好地完成交互,我们提供了可以复制到你的程序里的可选代码。可选代码使用了较快的输入输出,可能会提高 IO 较慢的 Python 和 Java 语言的程序效率(只与最后两个子任务有关)。
交互器没有使用随机函数,这意味着,每组测试数据都是固定的,与你的程序的询问无关。
样例
123
123
因为参数 14 大于等于它相邻点的参数(10 和 13),所以坐标为 (2,1,1) 的点满足条件,你一共进行了 3 次查询,小于等于最大允许查询次数 3,因此本次交互通过了这组测试数据。
数据范围与提示
子任务 |
分值 |
限制 |
1 |
10 |
M=K=1,N=1000000,Q=10000 |
2 |
22 |
M=K=1,N=1000000,Q=35 |
3 |
12 |
K=1,N=M=200,Q=4000 |
4 |
19 |
K=1,N=M=1000,Q=3500 |
5 |
14 |
N=M=K=100,Q=100000 |
6 |
23 |
N=M=K=500,Q=150000 |
请注意在 LibreOJ 上共有 7 个子任务,其中第一个子任务为样例。 |
|