← 返回题目列表

Codeforces · 690/E2

E2. 照片(二)

中文机器翻译题面 查看原题

僵尸最近似乎变得更加聪明——一些僵尸不知何故通过自动门溜进了基地。海蒂必须加强安全措施,并安装了新的大门。不幸的是,现在提出的问题更加复杂,甚至人类也很难回答。您还能对机器人军队进行编程以可靠地完成此任务吗?

新问题的形式如下:一张灰度照片被分成几个水平的部分,并被任意重新排列。任务是将这些碎片组合成原始图像(有点像拼图游戏)。为了进一步延迟僵尸的出现,图像中添加了显着的高斯分布噪声。

输入

输入格式与之前的版本相同,只是每个问题的第一行现在包含三个空格分隔的数字 h、w 和 k (1 ≤ h, w ≤ 600, 2 ≤ k ≤ 16) – 分别是照片的高度(行数)和宽度(列数)和张数。片数均分高度,每片高度h/k相同。

再次强调,只有一个输入文件需要处理,并且提供给您的资源与之前的版本相同(除了现在为您提供 .bmp 格式的所有输入图像,而不是前 50 个)。

输出

你的程序应该打印 q 行。第 i 行应包含第 i 个问题的答案:一个由空格分隔的 k 个数字 π1, π2, ..., πk 的序列,使得:

- π 是 {1, 2, ..., k} 的排列,即从 1 到 k 的每个数字在 π 中只出现一次,
- 对于每个 j = 1, ..., k,πj 是原始图像中位于输入图像中位置 j 的片段的位置(索引)。 (为了清楚起见,请参见下图。)

测试集中的第二张图像。如果原图像中的三块从上到下编号为1、2、3,则右侧图像中的编号应为2、3、1。因此,该图像的正确答案为2 3 1。

再次强调,如果您的答案符合此格式并且至少 75% 是正确的,我们将接受您的答案。

同样,您可以在本地处理输入并仅提交预先计算的答案(即仅打印输入文件 all.in 的输出的程序)。

注意

下载所有必要材料的链接是http://assets.codeforces.com/files/690/medium_contestant_package.zip