故事
AtCoder Inc. 正在开发机器人来保卫其办公室。 每个机器人都由一个 有限状态自动机 根据前面是否有一堵墙来改变它的状态和动作。 所需的成本取决于自动机中的状态数量、要引入的机器人数量以及要安装的新墙的数量。 请找到一种成本尽可能低的方法,使整个办公室定期巡逻。
问题陈述
有一个 N\times N 网格。 设左上角单元格的坐标为 (0,0),并定义移动到达的单元格的坐标 i 细胞向下并且 从那里右侧的 j 右侧的单元格为 (i,j)。 的外边界 N\times N 网格被墙包围,相邻单元之间也可能有墙。
最多 N^2 可以引入机器人。 对于每个机器人,最多 4N^2 可以定义内部状态。 每个机器人都由一个自动机控制,根据其前面是否有墙(即当前单元格与当前方向上一步的单元格之间是否有墙)和当前的内部状态,决定前进、右转、左转的动作以及下一个内部状态。
前进 (F) 沿当前方向向前移动一个单元格,且方向不变。
右转(R)并向左转(L) 指的是在不移动到另一个单元格的情况下改变原地方向。
按照以下顺序执行一个步骤的操作。 首先,机器人从当前(位置、方向、内部状态)判断前方是否有墙。 接下来,它确定操作和下一个状态。 然后它执行该操作,最后将内部状态更新为下一个状态。
让 m_k 是控制自动机的内部状态数 k第一个机器人。您可以选择 m_k 任意。 然后,对于每个状态 s=0,1,\cdots,m_k-1,指定以下内容。
- a_{k,s,0}: 哪一个右转 (
R),左转(L),或继续(F) 在前面没有墙壁时执行。 - b_{k,s,0}:前面没有墙时的下一个状态号。
- a_{k,s,1}: 哪一个右转 (
R)或左转(L)在前面有墙时执行。展望未来(F) 无法选择。 - b_{k,s,1}:前面有墙时的下一个状态号。
示例
考虑以下具有 2 个内部状态的自动机。
s a_{k,s,0} b_{k,s,0} a_{k,s,1} b_{k,s,1} 0 F 0 R 1 1 R 0 R 0
该自动机的操作如下。
- 当内部状态为0时,只要前面没有墙,它就向前走,如果前面有墙,它就向右转,过渡到内部状态1。
- 当内部状态为1时,无论前面是否有墙,都会向右转,并过渡到内部状态0。
换句话说,只要前面没有墙壁,它就会重复向前走,并在墙壁前面掉头的行为。
接下来,对于每个机器人 k,确定其位置 (i_k,j_k) 和方向 d_k 在初始放置中(向上: U,向下: D,左: L,右: R)。
内部状态的初始值为 0。
机器人之间互不干扰,多个机器人可以占据同一个单元。
最后,安装新墙。 任意两个相邻单元之间可以安装墙壁。 您可以指定一个已经存在墙的位置,但除了增加成本之外什么也不会发生。 由于新安装的墙壁,允许板断开连接。
对于每个机器人来说,(位置、方向、内部状态)的集合是有限的,且同一集合对应的下一次(位置、方向、内部状态)是唯一确定的。 因此,经过一段时间后,它必然会进入周期性行为。 将机器人在此周期性行为期间访问的单元定义为该机器人巡逻的单元。 仅在进入周期性行为之前访问的小区不包括在巡视的小区中。
让 K 为要引入的机器人数量,令 M=\sum_k m_k 是所有机器人的内部状态总数,
并让 W 是输出中指定的新安装墙壁的数量(
输出中的 1)。
给定系数 A_K, A_M,和 A_W 在输入中提供,定义引入成本 V 如下。
\[ V = A_K × (K-1) + A_M × M + A_W × W \]
寻找一种引入成本尽可能低的方法,使得每个小区都成为至少一个机器人巡逻的小区。 如果存在没有成为巡逻小区的小区,则判断为 WA.
评分
当引进成本为 V,您将获得以下分数。
\[ 1+\mathrm{round}\left(10^6\times \max\left(0,\log_2 \frac{A_K (N^2-1) + A_M N^2}{V}\right)\right) \]
取决于系数 A_K, A_M,和 A_W,问题分为三个子问题:A、B、C。 每个子问题包含 150 个测试用例,提交该子问题的总分是该子问题中所有测试用例得分的总和。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。
最终排名由各子题获得的最高分之和决定,赛后不进行系统测试。 如果有多支队伍获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出。
N A_K A_M A_W
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
- 电路板尺寸 N 固定为 N=20 适用于所有测试用例。
- 系数 A_K, A_M,和 A_W 的引入成本是之间的整数 0 和 1000,包括在内。
- v_{i,0} \cdots v_{i,N-2} 是一个长度为的字符串 N-1 组成
0和1,以及 j- 第一个字符 v_{i,j} 表示是否有(1) 或不是 (0) 细胞之间的墙 (i, j) 和细胞 (i, j+1). - h_{i,0} \cdots h_{i,N-1} 是一个长度为的字符串 N 组成
0和1,以及 j- 第一个字符 h_{i,j} 表示是否有(1) 或不是 (0) 细胞之间的墙 (i, j) 和细胞 (i+1, j). - 在初始状态下,保证所有单元格相互可达。
输出
按以下格式打印到标准输出。
K
m_0 i_0 j_0 d_0
a_{0,0,0} b_{0,0,0} a_{0,0,1} b_{0,0,1}
\vdots
a_{0,m_0-1,0} b_{0,m_0-1,0} a_{0,m_0-1,1} b_{0,m_0-1,1}
\vdots
m_{K-1} i_{K-1} j_{K-1} d_{K-1}
a_{K-1,0,0} b_{K-1,0,0} a_{K-1,0,1} b_{K-1,0,1}
\vdots
a_{K-1,m_{K-1}-1,0} b_{K-1,m_{K-1}-1,0} a_{K-1,m_{K-1}-1,1} b_{K-1,m_{K-1}-1,1}
v_{0,0}' \cdots v_{0,N-2}'
\vdots
v_{N-1,0}' \cdots v_{N-1,N-2}'
h_{0,0}' \cdots h_{0,N-1}'
\vdots
h_{N-2,0}' \cdots h_{N-2,N-1}'
- K 是要开发的机器人数量,必须满足 1\leq K\leq N^2.
- m_k 是内部状态的数量 k第一个机器人,它必须满足 1\leq m_k\leq 4N^2.
- (i_k,j_k) 是初始位置 k第一个机器人,它必须满足 0\leq i_k,j_k\leq N-1.
- d_k 是初始方向 k- 第一个机器人,并且是角色之一:
U,向下:D,左:L,右:R. - 对于每个机器人 k,必须准确输出 m_k 按内部状态顺序排列的行 s=0,1,\dots,m_k-1.
- a_{k,s,0} 和 a_{k,s,1} 代表机器人的动作 k 当其内部状态为 s。对于前面没有墙和前面有墙的情况分别指定右转之一:
R,左转:L,或继续:F。然而, a_{k,s,1} 不得F. - b_{k,s,0} 和 b_{k,s,1} 代表机器人下一个内部状态号 k 处于内部状态 s。对于前面没有墙和前面有墙的情况,分别必须满足 0\leq b_{k,s,0}, b_{k,s,1}\leq m_k-1.
- a_{k,s,0} 和 a_{k,s,1} 代表机器人的动作 k 当其内部状态为 s。对于前面没有墙和前面有墙的情况分别指定右转之一:
- v_{i,0}' \cdots v_{i,N-2}' 是一个长度为的字符串 N-1 组成
0和1,以及 j- 第一个字符 v_{i,j}' 表示是否安装(1)或不安装(0) 细胞之间的新墙 (i, j) 和细胞 (i, j+1). - h_{i,0}' \cdots h_{i,N-1}' 是一个长度为的字符串 N 组成
0和1,以及 j- 第一个字符 h_{i,j}' 表示是否安装(1)或不安装(0) 细胞之间的新墙 (i, j) 和细胞 (i+1, j). - 由于墙壁安装,该板可能会断开连接。
示例解决方案
import sys
input = sys.stdin.readline
N, AK, AM, AW = map(int, input().split())
wall_v = [input().strip() for _ in range(N)]
wall_h = [input().strip() for _ in range(N - 1)]
K = N * N
print(K)
for i in range(N):
for j in range(N):
m = 1
d = 'U'
print(m, i, j, d)
print('R 0 R 0')
for _ in range(N):
print('0' * (N - 1))
for _ in range(N - 1):
print('0' * N)
输入生成
对于任务 A、B 和 C 中的每一个,系数是从下表列出的范围(闭区间)中均匀随机生成的。
| 任务 | A_K | A_M | A_W |
|---|---|---|---|
| A | [0,0] | [1,1] | [1000,1000] |
| B | [1000,1000] | [1,10] | [1,10] |
| C | [1000,1000] | [1,1] | [1000,1000] |
墙的生成
让 \mathrm{rand}(L, U) 是一个函数,它均匀地随机生成一个整数 L 和 U,包括在内。
一、生成竖墙生成数 X=\mathrm{rand}(1,6) 和水平墙代数 Y=\mathrm{rand}(1,6).
从根本没有墙壁的状态开始,按如下方式生成墙壁。
重复以下操作 X 次。
- 随机决定是向上还是向下生成墙。
- 生成墙长 L = \mathrm{rand}(5, 15).
- 选择起点 (i, j) by i = \mathrm{rand}(0, N-1),\ j = \mathrm{rand}(0, N-2).
- 如果方向向上,则设置 v_{i-L+1, j}, \cdots, v_{i, j} to
1;如果方向向下,则设置 v_{i, j}, \cdots, v_{i+L-1, j} to1。指数超出董事会范围的术语将被忽略。
重复以下操作 Y 次。
- 随机决定是从左侧还是从右侧生成墙。
- 生成墙长 L = \mathrm{rand}(5, 15).
- 选择起点 (i, j) by i = \mathrm{rand}(0, N-2),\ j = \mathrm{rand}(0, N-1).
- 如果方向是向左,则设置 h_{i, j-L+1}, \cdots, h_{i, j} to
1;如果方向是向右,则设置 h_{i, j}, \cdots, h_{i, j+L-1} to1。指数超出董事会范围的术语将被忽略。
对于生成的墙,检查所有单元是否均可到达。如果某些单元格无法到达,则重置墙壁并重做墙壁生成(不重新生成 X 和 Y).
工具(输入生成器和分数计算)
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止在团队之外分享可视化结果或讨论解决方案/想法。
示例输入 1
20 0 1 1000 0010000000000000000 0010000000000000000 0010000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000010000 0001000000000010000 0001010000000010000 0001010000000010000 0001010000000010000 0001010000000010000 0000010000000010000 0000000000000010000 0000000000000000000 00000000000000000000 00000000111111111110 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000
示例输出 1
400 1 0 0 U R 0 R 0 1 0 1 U R 0 R 0 1 0 2 U R 0 R 0 1 0 3 U R 0 R 0 1 0 4 U R 0 R 0 1 0 5 U R 0 R 0 1 0 6 U R 0 R 0 1 0 7 U R 0 R 0 1 0 8 U R 0 R 0 1 0 9 U R 0 R 0 1 0 10 U R 0 R 0 1 0 11 U R 0 R 0 1 0 12 U R 0 R 0 1 0 13 U R 0 R 0 1 0 14 U R 0 R 0 1 0 15 U R 0 R 0 1 0 16 U R 0 R 0 1 0 17 U R 0 R 0 1 0 18 U R 0 R 0 1 0 19 U R 0 R 0 1 1 0 U R 0 R 0 1 1 1 U R 0 R 0 1 1 2 U R 0 R 0 1 1 3 U R 0 R 0 1 1 4 U R 0 R 0 1 1 5 U R 0 R 0 1 1 6 U R 0 R 0 1 1 7 U R 0 R 0 1 1 8 U R 0 R 0 1 1 9 U R 0 R 0 1 1 10 U R 0 R 0 1 1 11 U R 0 R 0 1 1 12 U R 0 R 0 1 1 13 U R 0 R 0 1 1 14 U R 0 R 0 1 1 15 U R 0 R 0 1 1 16 U R 0 R 0 1 1 17 U R 0 R 0 1 1 18 U R 0 R 0 1 1 19 U R 0 R 0 1 2 0 U R 0 R 0 1 2 1 U R 0 R 0 1 2 2 U R 0 R 0 1 2 3 U R 0 R 0 1 2 4 U R 0 R 0 1 2 5 U R 0 R 0 1 2 6 U R 0 R 0 1 2 7 U R 0 R 0 1 2 8 U R 0 R 0 1 2 9 U R 0 R 0 1 2 10 U R 0 R 0 1 2 11 U R 0 R 0 1 2 12 U R 0 R 0 1 2 13 U R 0 R 0 1 2 14 U R 0 R 0 1 2 15 U R 0 R 0 1 2 16 U R 0 R 0 1 2 17 U R 0 R 0 1 2 18 U R 0 R 0 1 2 19 U R 0 R 0 1 3 0 U R 0 R 0 1 3 1 U R 0 R 0 1 3 2 U R 0 R 0 1 3 3 U R 0 R 0 1 3 4 U R 0 R 0 1 3 5 U R 0 R 0 1 3 6 U R 0 R 0 1 3 7 U R 0 R 0 1 3 8 U R 0 R 0 1 3 9 U R 0 R 0 1 3 10 U R 0 R 0 1 3 11 U R 0 R 0 1 3 12 U R 0 R 0 1 3 13 U R 0 R 0 1 3 14 U R 0 R 0 1 3 15 U R 0 R 0 1 3 16 U R 0 R 0 1 3 17 U R 0 R 0 1 3 18 U R 0 R 0 1 3 19 U R 0 R 0 1 4 0 U R 0 R 0 1 4 1 U R 0 R 0 1 4 2 U R 0 R 0 1 4 3 U R 0 R 0 1 4 4 U R 0 R 0 1 4 5 U R 0 R 0 1 4 6 U R 0 R 0 1 4 7 U R 0 R 0 1 4 8 U R 0 R 0 1 4 9 U R 0 R 0 1 4 10 U R 0 R 0 1 4 11 U R 0 R 0 1 4 12 U R 0 R 0 1 4 13 U R 0 R 0 1 4 14 U R 0 R 0 1 4 15 U R 0 R 0 1 4 16 U R 0 R 0 1 4 17 U R 0 R 0 1 4 18 U R 0 R 0 1 4 19 U R 0 R 0 1 5 0 U R 0 R 0 1 5 1 U R 0 R 0 1 5 2 U R 0 R 0 1 5 3 U R 0 R 0 1 5 4 U R 0 R 0 1 5 5 U R 0 R 0 1 5 6 U R 0 R 0 1 5 7 U R 0 R 0 1 5 8 U R 0 R 0 1 5 9 U R 0 R 0 1 5 10 U R 0 R 0 1 5 11 U R 0 R 0 1 5 12 U R 0 R 0 1 5 13 U R 0 R 0 1 5 14 U R 0 R 0 1 5 15 U R 0 R 0 1 5 16 U R 0 R 0 1 5 17 U R 0 R 0 1 5 18 U R 0 R 0 1 5 19 U R 0 R 0 1 6 0 U R 0 R 0 1 6 1 U R 0 R 0 1 6 2 U R 0 R 0 1 6 3 U R 0 R 0 1 6 4 U R 0 R 0 1 6 5 U R 0 R 0 1 6 6 U R 0 R 0 1 6 7 U R 0 R 0 1 6 8 U R 0 R 0 1 6 9 U R 0 R 0 1 6 10 U R 0 R 0 1 6 11 U R 0 R 0 1 6 12 U R 0 R 0 1 6 13 U R 0 R 0 1 6 14 U R 0 R 0 1 6 15 U R 0 R 0 1 6 16 U R 0 R 0 1 6 17 U R 0 R 0 1 6 18 U R 0 R 0 1 6 19 U R 0 R 0 1 7 0 U R 0 R 0 1 7 1 U R 0 R 0 1 7 2 U R 0 R 0 1 7 3 U R 0 R 0 1 7 4 U R 0 R 0 1 7 5 U R 0 R 0 1 7 6 U R 0 R 0 1 7 7 U R 0 R 0 1 7 8 U R 0 R 0 1 7 9 U R 0 R 0 1 7 10 U R 0 R 0 1 7 11 U R 0 R 0 1 7 12 U R 0 R 0 1 7 13 U R 0 R 0 1 7 14 U R 0 R 0 1 7 15 U R 0 R 0 1 7 16 U R 0 R 0 1 7 17 U R 0 R 0 1 7 18 U R 0 R 0 1 7 19 U R 0 R 0 1 8 0 U R 0 R 0 1 8 1 U R 0 R 0 1 8 2 U R 0 R 0 1 8 3 U R 0 R 0 1 8 4 U R 0 R 0 1 8 5 U R 0 R 0 1 8 6 U R 0 R 0 1 8 7 U R 0 R 0 1 8 8 U R 0 R 0 1 8 9 U R 0 R 0 1 8 10 U R 0 R 0 1 8 11 U R 0 R 0 1 8 12 U R 0 R 0 1 8 13 U R 0 R 0 1 8 14 U R 0 R 0 1 8 15 U R 0 R 0 1 8 16 U R 0 R 0 1 8 17 U R 0 R 0 1 8 18 U R 0 R 0 1 8 19 U R 0 R 0 1 9 0 U R 0 R 0 1 9 1 U R 0 R 0 1 9 2 U R 0 R 0 1 9 3 U R 0 R 0 1 9 4 U R 0 R 0 1 9 5 U R 0 R 0 1 9 6 U R 0 R 0 1 9 7 U R 0 R 0 1 9 8 U R 0 R 0 1 9 9 U R 0 R 0 1 9 10 U R 0 R 0 1 9 11 U R 0 R 0 1 9 12 U R 0 R 0 1 9 13 U R 0 R 0 1 9 14 U R 0 R 0 1 9 15 U R 0 R 0 1 9 16 U R 0 R 0 1 9 17 U R 0 R 0 1 9 18 U R 0 R 0 1 9 19 U R 0 R 0 1 10 0 U R 0 R 0 1 10 1 U R 0 R 0 1 10 2 U R 0 R 0 1 10 3 U R 0 R 0 1 10 4 U R 0 R 0 1 10 5 U R 0 R 0 1 10 6 U R 0 R 0 1 10 7 U R 0 R 0 1 10 8 U R 0 R 0 1 10 9 U R 0 R 0 1 10 10 U R 0 R 0 1 10 11 U R 0 R 0 1 10 12 U R 0 R 0 1 10 13 U R 0 R 0 1 10 14 U R 0 R 0 1 10 15 U R 0 R 0 1 10 16 U R 0 R 0 1 10 17 U R 0 R 0 1 10 18 U R 0 R 0 1 10 19 U R 0 R 0 1 11 0 U R 0 R 0 1 11 1 U R 0 R 0 1 11 2 U R 0 R 0 1 11 3 U R 0 R 0 1 11 4 U R 0 R 0 1 11 5 U R 0 R 0 1 11 6 U R 0 R 0 1 11 7 U R 0 R 0 1 11 8 U R 0 R 0 1 11 9 U R 0 R 0 1 11 10 U R 0 R 0 1 11 11 U R 0 R 0 1 11 12 U R 0 R 0 1 11 13 U R 0 R 0 1 11 14 U R 0 R 0 1 11 15 U R 0 R 0 1 11 16 U R 0 R 0 1 11 17 U R 0 R 0 1 11 18 U R 0 R 0 1 11 19 U R 0 R 0 1 12 0 U R 0 R 0 1 12 1 U R 0 R 0 1 12 2 U R 0 R 0 1 12 3 U R 0 R 0 1 12 4 U R 0 R 0 1 12 5 U R 0 R 0 1 12 6 U R 0 R 0 1 12 7 U R 0 R 0 1 12 8 U R 0 R 0 1 12 9 U R 0 R 0 1 12 10 U R 0 R 0 1 12 11 U R 0 R 0 1 12 12 U R 0 R 0 1 12 13 U R 0 R 0 1 12 14 U R 0 R 0 1 12 15 U R 0 R 0 1 12 16 U R 0 R 0 1 12 17 U R 0 R 0 1 12 18 U R 0 R 0 1 12 19 U R 0 R 0 1 13 0 U R 0 R 0 1 13 1 U R 0 R 0 1 13 2 U R 0 R 0 1 13 3 U R 0 R 0 1 13 4 U R 0 R 0 1 13 5 U R 0 R 0 1 13 6 U R 0 R 0 1 13 7 U R 0 R 0 1 13 8 U R 0 R 0 1 13 9 U R 0 R 0 1 13 10 U R 0 R 0 1 13 11 U R 0 R 0 1 13 12 U R 0 R 0 1 13 13 U R 0 R 0 1 13 14 U R 0 R 0 1 13 15 U R 0 R 0 1 13 16 U R 0 R 0 1 13 17 U R 0 R 0 1 13 18 U R 0 R 0 1 13 19 U R 0 R 0 1 14 0 U R 0 R 0 1 14 1 U R 0 R 0 1 14 2 U R 0 R 0 1 14 3 U R 0 R 0 1 14 4 U R 0 R 0 1 14 5 U R 0 R 0 1 14 6 U R 0 R 0 1 14 7 U R 0 R 0 1 14 8 U R 0 R 0 1 14 9 U R 0 R 0 1 14 10 U R 0 R 0 1 14 11 U R 0 R 0 1 14 12 U R 0 R 0 1 14 13 U R 0 R 0 1 14 14 U R 0 R 0 1 14 15 U R 0 R 0 1 14 16 U R 0 R 0 1 14 17 U R 0 R 0 1 14 18 U R 0 R 0 1 14 19 U R 0 R 0 1 15 0 U R 0 R 0 1 15 1 U R 0 R 0 1 15 2 U R 0 R 0 1 15 3 U R 0 R 0 1 15 4 U R 0 R 0 1 15 5 U R 0 R 0 1 15 6 U R 0 R 0 1 15 7 U R 0 R 0 1 15 8 U R 0 R 0 1 15 9 U R 0 R 0 1 15 10 U R 0 R 0 1 15 11 U R 0 R 0 1 15 12 U R 0 R 0 1 15 13 U R 0 R 0 1 15 14 U R 0 R 0 1 15 15 U R 0 R 0 1 15 16 U R 0 R 0 1 15 17 U R 0 R 0 1 15 18 U R 0 R 0 1 15 19 U R 0 R 0 1 16 0 U R 0 R 0 1 16 1 U R 0 R 0 1 16 2 U R 0 R 0 1 16 3 U R 0 R 0 1 16 4 U R 0 R 0 1 16 5 U R 0 R 0 1 16 6 U R 0 R 0 1 16 7 U R 0 R 0 1 16 8 U R 0 R 0 1 16 9 U R 0 R 0 1 16 10 U R 0 R 0 1 16 11 U R 0 R 0 1 16 12 U R 0 R 0 1 16 13 U R 0 R 0 1 16 14 U R 0 R 0 1 16 15 U R 0 R 0 1 16 16 U R 0 R 0 1 16 17 U R 0 R 0 1 16 18 U R 0 R 0 1 16 19 U R 0 R 0 1 17 0 U R 0 R 0 1 17 1 U R 0 R 0 1 17 2 U R 0 R 0 1 17 3 U R 0 R 0 1 17 4 U R 0 R 0 1 17 5 U R 0 R 0 1 17 6 U R 0 R 0 1 17 7 U R 0 R 0 1 17 8 U R 0 R 0 1 17 9 U R 0 R 0 1 17 10 U R 0 R 0 1 17 11 U R 0 R 0 1 17 12 U R 0 R 0 1 17 13 U R 0 R 0 1 17 14 U R 0 R 0 1 17 15 U R 0 R 0 1 17 16 U R 0 R 0 1 17 17 U R 0 R 0 1 17 18 U R 0 R 0 1 17 19 U R 0 R 0 1 18 0 U R 0 R 0 1 18 1 U R 0 R 0 1 18 2 U R 0 R 0 1 18 3 U R 0 R 0 1 18 4 U R 0 R 0 1 18 5 U R 0 R 0 1 18 6 U R 0 R 0 1 18 7 U R 0 R 0 1 18 8 U R 0 R 0 1 18 9 U R 0 R 0 1 18 10 U R 0 R 0 1 18 11 U R 0 R 0 1 18 12 U R 0 R 0 1 18 13 U R 0 R 0 1 18 14 U R 0 R 0 1 18 15 U R 0 R 0 1 18 16 U R 0 R 0 1 18 17 U R 0 R 0 1 18 18 U R 0 R 0 1 18 19 U R 0 R 0 1 19 0 U R 0 R 0 1 19 1 U R 0 R 0 1 19 2 U R 0 R 0 1 19 3 U R 0 R 0 1 19 4 U R 0 R 0 1 19 5 U R 0 R 0 1 19 6 U R 0 R 0 1 19 7 U R 0 R 0 1 19 8 U R 0 R 0 1 19 9 U R 0 R 0 1 19 10 U R 0 R 0 1 19 11 U R 0 R 0 1 19 12 U R 0 R 0 1 19 13 U R 0 R 0 1 19 14 U R 0 R 0 1 19 15 U R 0 R 0 1 19 16 U R 0 R 0 1 19 17 U R 0 R 0 1 19 18 U R 0 R 0 1 19 19 U R 0 R 0 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000