← 返回题目列表

AtCoder · future_contest_2022_final_a

A. 机器人吸尘器的 Code Golf

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

问题陈述

F公司正在开发一款机器人吸尘器,高桥君吸尘器。 该机器人使用以下形式的程序进行工作,该程序仅包含基本命令和重复。

基本命令

  • L:左转 90 度。
  • R:右转 90 度。
  • l:如果机器人面向墙壁,则左转 90 度。
  • r:如果机器人面向墙壁,则右转 90 度
  • F:如果机器人没有面向墙壁,则向前移动一格。

重复

通过写入正整数 k 在基本命令之前,将重复基本命令 k 次。 例如,该程序 RFFFFFFFFFF 可以缩短为 R10F。 程序可以按以下方式分组 ()。 通过写一个正整数 k 组前,组内节目会重复 k 次。 例如,该程序 RFRFRFLRFRFRFL 可以缩短为 2(3(RF)L).

待清洁地板分为 N\times N 呈正方形并被墙壁包围。相邻的方块之间也可能有墙。 让 (0,0) 表示左上角的方块,并且 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。 机器人开始广场清扫 (s_i,s_j) 朝上。 机器人将清理所有访问过的方块,包括初始位置。

你的任务是输出一个可以清理所有方块的短程序。 机器人需要一个单位时间执行一个基本命令,并且必须在短时间内完成清洁工作 5000 时间单位。 如果输出程序没有完成 5000 单位时间,执行完后终止 5000基本命令。 执行基本命令也需要一个单位时间 l or r 不面向墙壁,或执行基本命令 F 面向墙壁。 机器人还将清洁它移动到的方格 5000基本命令。

评分

让 L 是输出程序中的字符数,并且 M 是程序执行完成或终止后已清理的方格数 5000 单位时间。 请注意 L 是字符数,而不是基本命令数。 例如,该程序 100(RF) 执行基本命令 200 次,但字符数为 L=7.

  • If L>10000 或者您的输出不是有效的程序,您的提交将被判断为 WA
  • If M=N^2,您将获得分数 N^2 + \mathrm{round}(10^8/(100+L)).
  • If M<N^2,您将获得分数 M.

有100个测试用例,提交的分数是每个测试用例的总分。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。


输入

输入由标准输入按以下格式给出:

s_i s_j
h_{0,0} \cdots h_{0,N-2}
\vdots
h_{N-1,0} \cdots h_{N-1,N-2}
v_{0,0} \cdots v_{0,N-1}
\vdots
v_{N-2,0} \cdots v_{N-2,N-1}

我们修复 N=20 适用于所有测试用例。 (s_i,s_j) 表示机器人的初始位置,满足 0\leq s_i, s_j\leq N-1.

h_{i,0} \cdots h_{i,N-2} 是一串 N-1 字符仅由 0 or 1。 如果方块之间有一堵墙 (i,j) 和 (i,j+1),那么 h_{i,j}=1,否则 h_{i,j}=0. v_{i,0} \cdots v_{i,N-1} 是一串 N 字符仅由 0 or 1。 如果方块之间有一堵墙 (i,j) 和 (i+1,j),那么 v_{i,j}=1,否则 v_{i,j}=0。 保证从初始位置可以到达所有方格。

输出

将用于在一行中操作机器人的程序输出到标准输出。

输入生成

的一代 s_i 和 s_j

s_i 和 s_j 由之间的均匀随机整数生成 0 和 N-1,包括在内。

的一代 h_{i,j} 和 v_{i,j}

让 [k]=\{0,1,\cdots,k-1\}。 开始于 N^2 孤立的顶点 V=[N]\times[N],我们生成一个图 G=(V,E) 通过以下过程。

  1. 首先,我们随机打乱一组边 \{\{(i,j),(i,j+1)\}\mid i\in[N],j\in[N-1]\}\cup\{\{(i,j),(i+1,j)\}\mid i\in[N-1],j\in[N]\} 并获取有序边列表 e_0,\cdots,e_{2N^2-2N-1}.
  2. 对于每个 e_k=\{(i,j),(i',j')\} 按顺序从 k=0 to k=2N^2-2N-1,我们插入 e_k 进入 E if (i,j) 和 (i',j') 未连接 G.
  3. 对于每个 e_k=\{(i,j),(i',j')\} 再次按顺序 k=0 to k=2N^2-2N-1,我们插入 e_k 进入 E 如果程度 (i,j) is 1 或程度 (i',j') is 1.

使用生成的图,我们生成 h 和 v 如下。

  • h_{i,j}=0 \iff \{(i,j),(i,j+1)\}\in E
  • v_{i,j}=0 \iff \{(i+1,j),(i,j)\}\in E

工具(输入生成器和可视化工具)

在比赛结束之前不允许共享可视化结果。 <font color="red">比赛期间,您可以使用网络可视化工具的“在 Twitter 上分享”功能分享seed=0 的可视化结果。</font> 您必须使用指定的主题标签和公共帐户。 请注意,在比赛结束之前,禁止分享其他种子的输出、有关如何获得该输出的信息、解决方案、讨论或源代码。 <a href="https://twitter.com/search?q=%23HTTF%20share_visualizer&src=typed_query&f=live">共享可视化结果列表</a>


样本输入 1

14 18
0000000000000010000
0001000001000110100
0010010001010101000
0011100000110100010
0011100000001001010
0001011000001101000
0010000000010100010
0011001000000000100
1101010010010100000
1001010110000010100
1001110101010010100
0000101000101100101
1010000100101010110
0000101100100001110
1001100100000000010
0011000100010100011
0010010000011001001
1101010011001000000
1011000001001001010
0001000101000010100
00101001010100000010
00100001100111000101
10000111000000010100
00000001011000101000
01000100011100010010
11011001101100001101
00101110101010111000
00000000101000100111
00101001011101010010
00000010000110100010
00110001010000001010
01100000110000110000
00011100000011000000
01010000101101110010
00100110001011010000
10000100101000110100
00100001100100001010
00000101001101111001
01000010000010000000

示例输出 1

10(RlFlF)LFF2(3(RF)L)R10FRFR5FLFFFR4FR3FL3FR2FL2FLFFFLFFFRFFR3FRFRFFRFL2FL2FRFR2FL5FFFFFFFFFFL2FL2FR4FRFFL9FL2FRFRFFL3FL3FLFFFFFLFFL4FLFLFRFLFR2FRFRFL2FL3FLFR2FRFRFR2FLFFLFRFFR3FFFLFFFRFRFRFL2FR2FL3FRFL4FLFFR6FRFRFFFRFL4FFFLFL2FRRFL2FRR4FFRFRFR2FRFR2FLFFFR4FLFRF4FR9FRFFFFFFRFFLFL3FRFFLFL4FLFRFRFLFLFRFRFL2FLFLFLFRFR3FRFLFLLFR2FR3FFFLFFRFLFFL2FRFLFL4FLFLLFRFRFLFRF2FL4FLFRFLFLFRR2FL3FRFFRFRFLFFFRFLFLFRFFLFFLFLFR4FRFFRFRFLFFLL2FR2FFRFFFFRFRFLFR2FRFRFRFL2FFR8FR2FRFFRF2FR3FRFLFR2FRFRFL2F2FFLFLFRF2FRFL5FRFLL4FRFLFFL2FRFRFL2FRFL4FL4FLFRFFLFL2FRR3FFRFFRFRFFR2FLFL2FRFRFRFL2FL7FR2FLFFLLFL3FRFLFLFFFFFL4FLFRFLFLFFR5FL2FLFRFR3FLFL7FL2FLF2FLFL4FLFR2FL3FR2FFRFFRFRFRR3FR2FLFR11FR3FLFRFRFL2FL3FRFL2FLFLFRFL2FRFLLFL3FLFLFRFFL2FLFRFLFRFLFLFRRFRFLFL4FRFLFR2FLFLFRF2FLFRFL4FR2FLFR2FRFLFRFRFL2F