← 返回题目列表

AtCoder · kupc2019_i

I. 编码/解码 2019

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

配点 : 400 点

問題文

这是交互元素的问题。

0 以上 10^{18} 的整数 给出了 X 。 对于

以下的说明, 请实现对X 进行编码的编码程序以及进行解码的解码程序。 替换为

由编码程序编码 仅根据 X 的信息,解码程序 如果您可以解码 X ,则您的答案是正确的。

编码程序

编码程序使用给定的整数 X 该值应乘以 150 行 150 列网格 编码为 H 。

首先是一个整数 最多可查询 X 和 150 行 150 列的初始网格 输入 G 信息。

G 中的每个方格都是空方格。 . 或墙方 # ,稍后将进行描述。“初始网格生成” 由生成。

你 G 空方块 . 通过对每个网格执行以下操作之一 必须创建并输出 H 。

  • 墙体 替换为 # 。 请输出
  • S 质量 S 。 请输出
  • 空方块 保留为 . 。

然而,网格 在 H 中,S方始终位于网格上。 1 只能存在正方形。

解码程序

在解码程序中,网格 来自 H 中信息的整数 解密 X 。

但是, 运算前设定中包含的 H 信息不是直接输入的。相反,网格 H 你可以控制你上方的机器人。

网格 i 行 j 选择列中的单元格。 (i, j) 。

首先,机器人 我在 H 的S方。你在下面「操作」可以进行多次。

  • 上、下、左、右 4 方向不对 1 告诉机器人。
  • 机器人尝试从当前所在的方格移动到该方向的相邻方格。
    • 换句话说,机器人 假设您位于 (i, j) 。
      • 当告诉机器人的方向是向上时,机器人将 (i-1, j) 属于
      • 当给机器人的方向为向下时,机器人将 (i+1, j) 属于
      • 如果给机器人的方向为左,机器人将 (i, j-1) 属于
      • 当告诉机器人的方向正确时,机器人 正在尝试移至 (i, j+1) 。
  • 那个方块是一个墙方块 如果不是 # 并且不在网格之外,则移动并移动墙体。 # 或者在网格之外,它不会移动。
  • 然后您将被告知机器人是否在 S 广场中。
  • 您无法得知机器人的移动是否成功。

几次 在「操作」之后你得到解密的整数 必须输出 X 。

初始网格生成

初始网格 G 有 直到 3800 墙方块 # 是随机放置的。

围墙广场 8 保证一个方格没有其他墙方格。 大约

质量 从 (i, j) 大约 8 什么是质量? (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1) 。

具体地,初始网格的生成如下。

  • 最初,所有网格方块都是空方块。 重复以下步骤,直到放置 . 。
  • 3800 墙方块。
    • 周囲 8 枚举没有墙方格的空方格作为候选,并从其中随机选择。 1 选择一个方块并将其替换为墙壁方块。
    • 如果网格边缘的空方块周围没有墙方块,它们也将被包含为候选方块。
    • 如果没有这样的方块, 如果您发现无法放置3800 墙方块,请丢弃该网格并生成一个新网格。 当放置
  • 3800 墙方格时,使用该网格作为初始网格。

此方法生成的初始网格示例 50 件是共享文件夹 分发于 。

请注意,这些分布式网格不一定包含在实际测试用例中。

制約

  • 0 \leq X \leq 10^{18}
    • X 是从此范围中随机选择的整数。
  • 网格的高度和宽度是 150 这是一个质量。
  • 初始网格 G 墙面空间 在 # 的数量是 必须小于或等于 3800 。
  • 初始网格 G 中,墙体周围的区域 8 方格内没有放置其他墙方格。
  • 整数 X 和初始网格 每次提交答案代码时都会重新生成 G 。

部分点

针对此问题设置了部分分数。

为每个提交的答案代码新生成。 对于任何 25 测试用例,

  • 65000 次或更少 如果您通过「操作」回答正确, 如果您通过 10 点
  • 6500 次或更少 如果您通过「操作」回答正确,除了上述之外 390 点

。 表示

提出

编码和解码程序 1 并提交。

从下面的“判断”部分可以看到,提交的程序是用于编码和解码的。 它被激活 1 次。

当程序启动时,输入一个字符串来确定是否应该进行编码或解码。

输入(编码程序)

输入是按以下格式从标准输入给出的。

1 行是一个字符串 请注意, encode 。 表示

2 在线 X , 行 3 之后 输入 G 。

G 广场 (i, j) 是一个字符 G_{i,j} 代表。 当

  • 质量 从 (i, j) 为空时 G_{i,j} 是一个字符 . 和
  • 质量 从 (i, j) 是墙方块时 G_{i,j} 是一个字符 # 。

字符之间没有空格。

encode
X
G_{1,1}G_{1,2}...G_{1,150}
:
G_{150,1}G_{150,2}...G_{150,150}

输出(编码程序)

以以下格式标准输出 H 。

H 广场 (i, j) 字符 将其表示为 H_{i,j} 。 当

  • 质量 从 (i, j) 为空时 H_{i,j} 是一个字符 .、
  • 质量 从 (i, j) 是墙方块时 H_{i,j} 是一个字符 #、
  • 质量 从 (i, j) 为S方时 让它成为 H_{i,j} 是一个字符 S 。

字符之间不包含空格。

H_{1,1}H_{1,2}...H_{1,150}
:
H_{150,1}H_{150,2}...H_{150,150}

输入/输出(解码程序)

一、字符串 decode 由标准输入以以下格式给出。

decode

之后好几次 执行「操作」。 执行「操作」现在按以下格式输出到标准输出。

输入您希望机器人移动的方向。 C 。 当C 是一个字符 U,D,L,R ,具有顶部、底部、左侧和右侧 4 代表方向。 对

? C

这个「操作」的响应由标准输入给出,格式如下:

文字表示机器人是否在S方格内。 由 J 代表。

  • 当机器人处于S空间时 J 是 您也可以写 S 和
  • 当机器人不在S广场时 J 是 您也可以写 . 。
J

最后 X 。

! X

法官

判断将按以下步骤进行。 生成

  • 整数 X 和初始网格 每次提交答案代码时都会重新生成 G 。
  • 启动对提交的程序进行编码的进程。
  • 为编码过程提供输入。但是,没有给出 EOF。
  • 等待编码过程产生适当的输出并且编码过程完成。
  • 如果输出不合适的网格,将被视为错误答案。
  • 启动对提交的程序进行解码的进程。
  • 与解码过程交互。该对话将持续到解码过程终止。
  • 只有解码过程在执行时限内产生正确的输出,才认为答案是正确的;否则答案将不正确。

注意

  • 每次输出后刷新标准输出。否则可能会导致 TLE。
  • 网格 H 和整数 X 后立即退出程序。法官在不遵守规定的情况下的行为是不确定的。
  • 输出格式不正确时的判断行为未定义。
  • 进程不得参与上述指定之外的任何通信。

输入示例(编码程序)

在此示例中 我已经注释掉了对 G 是 您也可以写 20 行 20 作为列网格输入,但实际上 150 行 150 栏。

另外,在这个例子中 G 墙方格的数量是 70 但实际上 3800 。

encode
239
#..............#..#.
......#....#.#......
..#............#....
.....#..#..#.#...#..
.#.#...............#
.......#..#..#......
..#..#.........#.#.#
..........#..#......
..#..#..........#.#.
.......#.#..#.......
...#..........#...#.
.#...#...#.#........
.......#.....#.#..#.
#.#......#.#........
....#.#.......#..#..
.........#.........#
#..#.#.#...#.#.#.#..
...................#
..#.....#.#.#.......
.....#.........#.#..

输出示例(编码程序)

在此示例中 我已经注释掉了对 H 是 您也可以写 20 行 20 虽然它是作为列网格输出的,但它实际上是 150 行 150 栏。

####################
#S...###############
..##...#############
######.#############
#####..#############
#.....##############
..######....########
.#####...##..#######
.##########..#######
......####..########
########...#########
##########.#.....###
####..##...#.###..##
#####....###.####..#
############..####.#
#############......#
##################.#
############..###..#
#############.....##
####################

输入/输出示例(解码程序)

如上面的输入/输出示例所示,示出了在执行编码之后的解码示例。

入力 出力 備考
decode
解码开始。机器人是S-mas 我在 (2, 2) 。
? R
机器人是一个空的方块 转至 (2, 3) 。
.
机器人处于空旷的空间中。
? U
机器人质量很高 我尝试移动到 (1, 3) ,但由于这个方块是一个墙方块,所以我移动到原来的方块。 留在 (2, 3) 。
.
机器人处于空旷的空间中。
? L
机器人是 S 质量 (2, 2) 。
S
机器人位于 S 方格中。 输出
! 239
X 并终止程序。「操作」的数量是 3 次。 超过