← 返回题目列表

AtCoder · xmascon21_i

I. 互动鼹鼠

中文机器翻译题面 查看原题

配点 : 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 以下。

入出力

  1. 整数 A, B, C, D 将以空格分隔的形式从标准输入提供。
  2. 重复以下操作。
    1. 整数 e, f 将以空格分隔的形式从标准输入提供。
    2. e = f = 0 表示在这种情况下结束打地鼠游戏。结束程序。
    3. 否则,表示地鼠出现在格子 (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 ,所以这是正确答案。

在实际的裁判数据中,并不一定会出现与这个输入输出例完全一致的对话。