故事
AtCoder 的首席执行官高桥为明天的万圣节做准备。 在 AtCoder 的万圣节派对上,高桥会乔装打扮,依次从 100 名员工手中领取一块糖果,并说:“不给糖就捣蛋!” 他准备了一个方盒子,里面可以装 10\times 10 糖果呈网格状,每个员工将一块糖果放在空白处,这样糖果就不会重叠。 有 3 糖果种类:草莓味、西瓜味、南瓜味。 通过初步调查,他知道每个员工会放入哪种口味的糖果,但不知道每个员工会放在哪里。 由于他是个干净狂,他会通过向前、向后、向左或向右倾斜盒子来移动糖果,每收到一块糖果就移动一次,并最终希望确保相同类型的糖果尽可能聚集在一起。 请帮助他编写一个程序来确定倾斜的方向。
问题陈述
有一个盒子可以容纳 10\times 10 呈网格图案的糖果。 盒子最初是空的,并且 100 糖果将按顺序放置。 有 3 糖果的口味,并且我们提前知道了口味 f_t (1\leq f_t\leq 3) 的 t第一个糖果。 另一方面,我们事先并不知道每个糖果将被放置到哪个单元格中,并且它会在空单元格中均匀随机选择。 您无法更改收到糖果的顺序。
每次您收到一颗糖果,您必须将盒子向前、向后、向左或向右倾斜一次。 当您倾斜盒子时,每块糖果都会同时朝该方向移动,直到到达边缘或撞到另一块糖果。 例如,如果在左图所示的状态下将盒子向前倾斜,则盒子将处于右图所示的状态。

评分
我们将糖果块的连通性定义如下并考虑连通分量。
两块糖果是相连的当且仅当它们具有相同的口味,并且只能通过四个方向(前、后、左、右)相同口味的糖果才能到达对方。
例如下图中的状态由 7 连接组件的尺寸 \{1, 1, 2, 2, 4, 6, 9\}.

让 n_1,\cdots,n_k 是收到 100 块糖果后最终状态下连通分量的大小列表,令 d_i 为口味糖果的总数 i。 那么测试用例的分数是
\[\mathrm{round}\left(10^6\times\frac{\sum_{i=1}^k n_i^2}{\sum_{i=1}^3 d_i^2}\right)\]
你的任务是编写一个程序来确定倾斜方向,以便获得尽可能高的分数。
有200个测试用例,一次提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置(注意,这与之前的短期AHC有所不同)。
输入和输出
首先,每块糖果的味道由标准输入以以下格式给出。
f_1 f_2 \cdots f_{100}
每个 f_t 是介于 1 和 3,代表味道 t第一块糖果。
阅读以上信息后,重复以下过程 100 次。
在 t第一个进程(1\leq t\leq 100),单个整数 p_t 之间 1 和 101-t 由标准输入给出。 让我们对空单元格进行编号 1 to 101-t 从前到后、从左到右优先,如下图所示。 然后 t- 第一块糖果被放置在 p_t- 第一个空单元格。

阅读后 p_t,通过表示向前、向后、向左、向右 F, B, L,和 R分别将单个字符输出到标准输出,以指示盒子倾斜的方向。
输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交内容可能会被判定为 在输出以下内容之前,不会给出 TLE. 请注意 p_{t+1} 在你输出之前不会给出 t第方向。 由于第 100 次倾斜时没有任何反应,因此您可以跳过输出。
示例
| t | 输入 | 输出 |
|---|---|---|
| 先前信息 | 2 2 1 3 1 2 1 2 1 \cdots 3 |
|
| 1 | 3 |
R |
| 2 | 98 |
B |
| \vdots | ||
| 100 | 1 |
L |
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 每个 f_t 是由生成的 \mathrm{rand}(1,3)。 每个 p_t 是由生成的 \mathrm{rand}(1,101-t).
工具(输入生成器和可视化工具)
- 网页版:这比提供动画和手动播放的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。