许多人还记得由 Alexey Pajitnov 创作的著名电脑游戏“俄罗斯方块”(TETRIS),其中由四个正方形组成的方块(四格骨牌)从空中落下,游戏的目标是旋转并让每个方块落在一个矩形容器中,创造尽可能多没有空隙的整行。当这些行被创造出来时,它们就会消失,从而为后续的方块腾出更多空间。
让我们研究一个更简单版本的游戏,称为“Tiny TETRIS”(或简称“Tiny”)。只有九种不同的 Tiny 方块(或称 t-pieces),由一到三个正方形组成:
数字表示 t-piece 的类型,后续将用于指代特定的 t-piece。
游戏的目标相同——下落的 t-pieces 必须放入一个宽 $9$ 单位、高 $9$ 单位的矩形容器中。与俄罗斯方块不同,t-pieces 不能旋转。此外,它们在开始下落后不能向左或向右移动。因此,对于每个 t-piece,玩家只需选择容器的列号($1$ 到 $9$ 之间的整数),该方块最左边的正方形(标记为 $\times$)将落入该列。
每局游戏由 $N$ 个 t-pieces 的有限序列组成,玩家需要将尽可能多的方块放入容器中,且不能超过其上边界或进行非法移动。游戏得分等于成功放入容器的 t-pieces 数量。
游戏开始时,计数器设为 0。
游戏算法如下:
- 玩家为当前 t-piece 最左边的正方形选择列;
- 如果列设置正确(例如,对于 t-piece 5,第 8 列永远不可能是正确的),t-piece 将下落直到遇到障碍物;否则游戏结束。
- 如果 t-piece 完全容纳在容器内(即所有正方形都在 $9 \times 9$ 矩形内),计数器的值加 1。否则,游戏结束。
- 然后检查是否存在任何填满的水平行(完全由 t-pieces 的方块填满且没有任何空格的水平行)。如果存在,这些行将消失,其上方的行在不改变其配置的情况下向下移动。
- 如果还有剩余的 t-pieces,转到 1)。否则游戏结束。
某局游戏的得分是游戏结束时计数器的值。
让我们分析一局特定的游戏。
给定的 $20$ 个 t-pieces 序列如下:5,4,1,6,7,6,4,4,7,9,5,5,6,8,3,4,3,7,4,2。假设前 $17$ 个 t-pieces 已分别成功放入以下列中:1,2,2,4,8,8,7,4,8,6,1,1,4,8,3,7,7。截至此时,尚未有任何行被消除,当前计数器的值为 $17$,现在轮到放入第 $18$ 个方块,即 t-piece 7(图中字母按顺序分配给各个 t-pieces):
只有两个合法的列可以放入 t-piece 7:
a) 第 1 列:
b) 第 5 列(在这种情况下,有一行将被填满并因此消失):
输入格式
你将获得五个文件,每个文件包含一局特定游戏的描述:tiny.i1、tiny.i2、tiny.i3、tiny.i4 和 tiny.i5。
每个文件包含 t-pieces 的序列,格式如下:第一行包含一个整数 $N$。接下来的 $N$ 行描述 t-piece 序列;每行包含一个 $1$ 到 $9$ 之间的整数——特定 t-piece 的编号。t-pieces 按它们必须放入容器的顺序给出;第 $i$ 个 t-piece 给出在文件的第 $i+1$ 行。
输出格式
对于每个给定的输入文件,你必须提交一个对应的输出文件(tiny.o1、tiny.o2、tiny.o3、tiny.o4 和 tiny.o5),最多包含 $N$ 行——即方块落入的列号。输出文件的第 $i$ 行必须包含输入数据中第 $i$ 个 t-piece 应当落入的列号。
保证对于每个输入文件,都存在一个列号序列,使得所有 t-pieces 都能成功放入容器中(并获得等于 $N$ 的最终游戏得分)。
子任务
五个测试点中的每一个都值 20 分。你针对某个特定输出文件(测试点)所获得的分数将使用以下公式计算:
$$20 \times \frac{\text{your\_score}}{\text{maximum\_score\_among\_all\_contestants}}$$
计算结果四舍五入保留两位小数。
在比赛期间,你将获得每个提交的输出文件的反馈:你的得分以及在假设有人获得满分的情况下你将获得的分数。比赛结束后,将使用所有参赛者中的实际最高得分对输出文件进行重新评估,你可能会因此获得更多分数。