配点 : 100 点
黑兔:「今年一起玩吧!」
白兔:「如果左右手各拿一个锤子,不就一个人也能玩吗?」
黑兔:「用手的话会扭到,不太好哦」
白兔:「真聪明」
打地鼠神:「连我的速度一半都发挥不出来,真可怜」
黑兔·白兔:“……”
問題文
这个问题是交互式的。评分程序最多使用运行时间 100 ms / 内存 16 MB 左右。
2 行 100 有一列格子。i 行 j 这一列的格子 (i, j) (1 \le i \le 2,1 \le j \le 100).
黑兔和白兔在格子上,最初所在的格子分别是 (A, B), (C, D) 。
接着,打地鼠开始。请在线响应查询。每个查询如下列之一:
- 田鼠会出现在格子上。 (e, f) 你选择黑兔或白兔。被选中的兔子会移动到田鼠出现的格子上。如果兔子移动到格子 (i, j) 到 (e, f) ,\lvert i - e \rvert + \lvert j - f \rvert 可以得到第成本 需要会产生费用。
- 打田鼠结束。此时,到目前为止产生的费用总额必须不超过“假设事先知道田鼠会出现的格子时所产生费用总额的最小值” z 作为 2 z + \lvert A - C \rvert + \lvert B - D \rvert 。
任意时刻,允许黑兔、白兔和田鼠中的多个存在于同一格子上。
并且,裁判是自适应的。也就是说,根据你的选择,田鼠是否结束或者田鼠会出现的格子可能会变化。
制約
- 1 \le A \le 2.
- 1 \le B \le 100.
- 1 \le C \le 2.
- 1 \le D \le 100.
- 田鼠会出现的格子 (e, f) 是 您也可以写 1 \le e \le 2,1 \le f \le 100 很满意。
- 田鼠出现查询的次数为 1 以上 10\,000 以下。
入出力
- 整数 A, B, C, D 将以空格分隔的形式从标准输入提供。
- 重复以下操作。
- 整数 e, f 将以空格分隔的形式从标准输入提供。
- e = f = 0 表示在这种情况下结束打地鼠游戏。结束程序。
- 否则,表示地鼠出现在格子 (e, f) 上。以标准输出
1或 至少2该值应乘以 1 行输出,并刷新标准输出。1表示选择黑兔,2表示选择白兔。
如果进行不遵循此原则的输入输出,裁判结果不确定(不一定 WA 会如此)。
入出力例
| 入力 | 出力 | 説明 |
|---|---|---|
1 12 2 24 |
最初,黑兔出现在格子 (1, 12) 上,白兔出现在格子 (2, 24) 。 | |
1 1 |
田鼠会出现在格子上。 (1, 1) 上。 | |
2 |
已选择白兔。移动到格子 (2, 24) 到 (1, 1) 。24 需要成本。 | |
2 100 |
田鼠会出现在格子上。 (2, 100) 上。 | |
1 |
选择了黑兔。 (1, 12) 到 (2, 100) 。89 需要成本。 | |
0 0 |
停止打地鼠。总成本是 113 和z = 87 捻 2 z + \lvert A - C \rvert + \lvert B - D \rvert = 187 ,所以这是正确答案。 |
在实际的裁判数据中,并不一定会出现与这个输入输出例完全一致的对话。