QOJ.ac

QOJ

مجموع النقاط: 100 إخراج فقط

#15965. Tiny

الإحصائيات

许多人还记得由 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。

游戏算法如下:

  1. 玩家为当前 t-piece 最左边的正方形选择列;
  2. 如果列设置正确(例如,对于 t-piece 5,第 8 列永远不可能是正确的),t-piece 将下落直到遇到障碍物;否则游戏结束。
  3. 如果 t-piece 完全容纳在容器内(即所有正方形都在 $9 \times 9$ 矩形内),计数器的值加 1。否则,游戏结束。
  4. 然后检查是否存在任何填满的水平行(完全由 t-pieces 的方块填满且没有任何空格的水平行)。如果存在,这些行将消失,其上方的行在不改变其配置的情况下向下移动。
  5. 如果还有剩余的 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.i1tiny.i2tiny.i3tiny.i4tiny.i5

每个文件包含 t-pieces 的序列,格式如下:第一行包含一个整数 $N$。接下来的 $N$ 行描述 t-piece 序列;每行包含一个 $1$ 到 $9$ 之间的整数——特定 t-piece 的编号。t-pieces 按它们必须放入容器的顺序给出;第 $i$ 个 t-piece 给出在文件的第 $i+1$ 行。

输出格式

对于每个给定的输入文件,你必须提交一个对应的输出文件(tiny.o1tiny.o2tiny.o3tiny.o4tiny.o5),最多包含 $N$ 行——即方块落入的列号。输出文件的第 $i$ 行必须包含输入数据中第 $i$ 个 t-piece 应当落入的列号。

保证对于每个输入文件,都存在一个列号序列,使得所有 t-pieces 都能成功放入容器中(并获得等于 $N$ 的最终游戏得分)。

子任务

五个测试点中的每一个都值 20 分。你针对某个特定输出文件(测试点)所获得的分数将使用以下公式计算:

$$20 \times \frac{\text{your\_score}}{\text{maximum\_score\_among\_all\_contestants}}$$

计算结果四舍五入保留两位小数。

在比赛期间,你将获得每个提交的输出文件的反馈:你的得分以及在假设有人获得满分的情况下你将获得的分数。比赛结束后,将使用所有参赛者中的实际最高得分对输出文件进行重新评估,你可能会因此获得更多分数。


أو قم برفع الملفات واحداً تلو الآخر:

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.