故事
给出了如下图所示的地图。 高桥的家位于红圈广场,AtCoder 的办公室位于蓝圈广场。 他将自己到办公室的通勤路线记为一串字符,例如 DRDR,意思是下、右、下、右。 因为他很健忘,有时他会忘记他所记住的弦的某些部分。 例如,如果他忘记了第三个字符,他就会向下、向右、向右移动,而没有到达办公室就会迷路。 因此,他决定记住一根牢靠的绳子,这样即使他忘记了绳子的某些部分,也能让他有很大的概率到达办公室。 例如,如果他记住了字符串 DRDRDR,那么即使他忘记了其中任何一个字符,他也可以到达办公室。 你的任务是找到一根绳子,让高桥以高概率快速到达办公室。
|
|
|
|
问题陈述
您将获得一张地图,其中包括 20\times 20 方块。
地图的外部被墙壁包围。
相邻的方块之间也可能有墙。
让 (0,0) 表示左上角的方块,并且 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
高桥的家位于 (s_i, s_j) AtCoder 的办公室位于 (t_i, t_j)。
通过将上、下、左、右运动表示为 U, D, L,和 R分别输出从家到办公室的通勤路线作为长度小于或等于的字符串 200.
让 L 是输出字符串的长度。 从家里开始,高桥会在每个房间做以下动作: t=1,\cdots,L 转。
- 具有恒定概率 p,他不记得了 t- 第一个字符并停留在当前方格中。
- 剩余概率 1-p,他按照 所代表的方向移动一格 t- 第一个字符。如果那个方向有墙,他就留在当前的广场上。
当他到达办公室时,他立即终止了搬迁。
评分
让 S 是一个随机变量,定义为 S=401-t 如果他在以下时间到达办公室 t 动作轮流和 S=0 如果他未能到达办公室并计算其期望值, E[S]。
然后,你将获得分数 \mathrm{round}(250000\times E[S])。
如果您的输出无效(长度超过 200 或包含除 U, D, L,和 R),会被判断为 WA.
有100个测试用例,提交的分数是每个测试用例的总分。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。
输入
输入由标准输入按以下格式给出:
s_i s_j t_i t_j p
h_{0,0} \cdots h_{0,18}
\vdots
h_{19,0} \cdots h_{19,18}
v_{0,0} \cdots v_{0,19}
\vdots
v_{18,0} \cdots v_{18,19}
家和办公室的坐标满足 0\leq s_i\leq 4, 0\leq s_j\leq 4, 15\leq t_i\leq 19,和 15\leq t_j\leq 19. p 是一个实数,代表忘记每个字符的概率,并且满足 0.1\leq p\leq 0.5. h_{i,0} \cdots h_{i,18} 是一串 19 字符仅由 0 or 1。 如果方块之间有一堵墙 (i,j) 和 (i,j+1),那么 h_{i,j}=1,否则 h_{i,j}=0. v_{i,0} \cdots v_{i,19} 是一串 20 字符仅由 0 or 1。 如果方块之间有一堵墙 (i,j) 和 (i+1,j),那么 v_{i,j}=1,否则 v_{i,j}=0。 保证从家里就可以到达所有广场。
输出
将高桥记住的字符串一行输出到标准输出。
输入生成
的一代 (s_i, s_j), (t_i, t_j),和 p
我们生成 s_i=\mathrm{rand}(0, 4), s_j=\mathrm{rand}(0, 4), t_i=\mathrm{rand}(15, 19), t_j=\mathrm{rand}(15, 19),和 p=\mathrm{rand}(10, 50) / 100.
的一代 h_{i,j} 和 v_{i,j}
让 [k]=\{0,1,\cdots,k-1\}。 让 G=(V,E) 是一个网格图,使得 V=[20]\times[20] 和 E=\{\{(i,j),(i,j+1)\}\mid i\in[20],j\in[19]\}\cup\{\{(i,j),(i+1,j)\}\mid i\in[19],j\in[20]\}。 我们生成两棵生成树 G_r=(V,E_r) (r=1,2) of G 通过独立执行以下过程两次。
- 首先,我们随机打乱边缘 E 并获得有序边列表 e_0,\cdots,e_{759}.
- 从 E_r=\emptyset,对于每个 e_k=\{(i,j),(i',j')\} 按顺序从 k=0 to k=759,我们插入 e_k 进入 E_r if (i,j) 和 (i',j') 未连接 G_r.
使用获得的两个生成树,我们生成 h 和 v 如下。
- h_{i,j}=0 \iff \{(i,j),(i,j+1)\}\in E_1\cup E_2
- v_{i,j}=0 \iff \{(i,j),(i+1,j)\}\in E_1\cup E_2
工具(输入生成器和可视化工具)
- 网页版:这个比本地版本更强大,可以显示动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
在比赛结束之前不允许共享可视化结果。
示例输入 1
1 2 19 16 0.10 0010000100110011100 1000001000001000001 0000000000000000010 0100000000000110100 0000000000000000100 1000101100000101010 0010001011000110000 0000001001000000000 0000000100010001001 0010010000100000001 0001000010000100000 0011010000000001000 0000000101010100000 0000001000000100010 0110100010000000000 0010011101000101000 0000100110010000000 0010000101101000010 1001000000000000000 1000110000000000000 00000001000000000100 00001000010001000000 00010001010000010000 01110010101000010100 00000000000001100000 00001000010000000100 00101000000010110011 01010100000000000000 00001101010010010010 10000000000000010100 01011010000001100100 00000000000000010011 00001100111000110100 00000010000000000000 00010000100111000000 11010000001001010100 01100010011001011001 00000101000010101010 00100000000000000001
示例输出 1
RDLRLRRDUUDRLURDRRDDLRLRUURUUUUDRDRUUDLRUDLLDDDDURLRUDDLDRDLRLLLLUDRUDRRULRULRDLRLDLLUUULDLUURRLRDRRRRDULDRLRRRRDDDDDRULDDURDDDRDLRRLDLDLDLRLLLUDDRDDDUURUDDLLLUULLLLDLUDRLLDLLULRLDLDDRLDRDLURURULRDDDR