问题陈述
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) 通过以下过程。
- 首先,我们随机打乱一组边 \{\{(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}.
- 对于每个 e_k=\{(i,j),(i',j')\} 按顺序从 k=0 to k=2N^2-2N-1,我们插入 e_k 进入 E if (i,j) 和 (i',j') 未连接 G.
- 对于每个 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