#2776. 「BalticOI 2018」蠕虫之忧

内存限制:1024 MiB 时间限制:3000 ms 题目类型:交互
上传者: Mingqi_H

题目描述

题目译自 BalticOI 2018 Day1「Worm Worries

本题是一道交互题。

在一个三维空间(我们限制大小为 N\times M\times K )内,每个点都有一个正整数参数,记这个参数为 H[x,\, y,\, z] (保证 1\leqslant x \leqslant N\ ,1 \leqslant y \leqslant M\ ,1 \leqslant z \leqslant K 且每个参数都不超过 10^9 )。你最多可以询问 Q 次,找到一个点,使得这个点的参数不小于它周围与它有公共边的所有点的参数,即:

H[x,\,y,\,z]\geqslant\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\leqslant x\leqslant N,\, 1\leqslant y\leqslant M,\, 1\leqslant z\leqslant K 。如果不满足坐标的限制、询问不符合格式或询问超过了 Q 行,交互器会输出 -1 并退出,此时你的程序也应该退出。否则你可能会得到 Runtime ErrorTime Limit Exceeded 的判定结果。

请注意,你必须在每一次询问之后手动刷新缓存,否则你的程序将会超时,对于各语言,刷新缓存的方法如下:

  • Java: 调用 System.out.println() 会自动刷新缓存;
  • Python: 调用 print() 会自动刷新缓存;
  • C++: cout << endl 可以输出一个换行并刷新缓存。如果使用 printf,请使用 fflush(stdout)
  • Pascal: 调用 Flush(Output)

为了帮助你更好地完成交互,我们提供了可以复制到你的程序里的可选代码。可选代码使用了较快的输入输出,可能会提高 IO 较慢的 Python 和 Java 语言的程序效率(只与最后两个子任务有关)。

交互器没有使用随机函数,这意味着,每组测试数据都是固定的,与你的程序的询问无关。

样例

为了使你更好地完成交互,下面给出一组交互的示例。在这个示例中, N=3,\,M=3,\,K=1,\,Q=3 ,这三个格子的参数为 \{10,\,14,\,13\} 。以 JUDGE 开头的行表示交互库输出的内容(你的程序的标准输入的内容),以 YOU 开头的行表示你的程序的输出。

JUDGE:      3 1 1 3 123123 fixed 10 14 13
YOU  :      ? 3 1 1
JUDGE:      13
YOU  :      ? 2 1 1
JUDGE:      14
YOU  :      ? 1 1 1
JUDGE:      10
YOU  :      ! 2 1 1

样例解释

因为参数 14 大于等于它相邻点的参数( 10 13 ),所以坐标为 (2,\,1,\,1) 的点满足条件,你一共进行了 3 次查询,小于等于最大允许查询次数 3 ,因此本次交互通过了这组测试数据。

数据范围与提示

子任务 分值 限制
1 10 M=K=1,\,N=1\,000\,000,\,Q=10\,000
2 22 M=K=1,\,N=1\,000\,000,\,Q=35
3 12 K=1,\,N=M=200,\,Q=4\,000
4 19 K=1,\,N=M=1\,000,\,Q=3\,500
5 14 N=M=K=100,\,Q=100\,000
6 23 N=M=K=500,\,Q=150\,000

请注意在 LibreOJ 上共有 7 个子任务,其中第一个子任务为样例。