← 返回题目列表

Codeforces · 690/E1

E1. 照片(一)

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

由海蒂领导的人牛联盟(HC2)建立了一个基地,人和牛可以躲藏起来,免受僵尸攻击。基地的入口受到自动门的保护,该门执行一种图灵测试:它向进入的生物展示一张照片,并询问它们这张照片的上半部分和下半部分是否已交换。一个人(甚至一头牛)回答这样的问题是没有问题的;另一方面,僵尸只会随机粉碎两个按钮中的一个。

该生物被问了一系列这样的问题。如果其中至少 75% 回答正确,则大门解锁;否则,一扇侧门会打开,门下有一个巨大的风扇在旋转……

海蒂现在正在组建一支机器人军队来对抗僵尸,她希望机器人也能够进入基地。您的任务是对它们进行编程以区分图像。

测试集中的前两张图像。第一张图片已重新排列,但第二张图片没有重新排列。

输入

输入的第一行包含问题数 q (1 ≤ q ≤ 220)。之后是 q 个问题,每个问题的格式如下。

每个问题的第一行包含两个空格分隔的整数 h 和 w (1 ≤ h, w ≤ 600) – 照片的高度(行数)和宽度(列数)。 (大多数照片大约为 200 × 300。)之后是 h 行,每行描述图片的一行。图片是单色的(灰色阴影)。它的第 i 行由 w 个空格分隔的整数 aij (j = 1, ..., w) 描述,其中 aij 是相应像素的亮度(0 ≤ aij < 256,其中 0 为黑色,255 为白色)。

每张图片要么是现实生活中的照片,要么是被分成两部分并重新排列的现实生活照片。更准确地说,在后一种情况下,最上面的 $$\frac{h}{2}$$ 行已移动到图片的底部。保证h是偶数。

只有一个要处理的输入文件,称为 all.in,可以从在线法官下载。您还有一个给定的另一个输入文件,名为sample.in,其中包含all.in 中的前20 张图片;在sample.out 中为您提供了sample.in 的正确答案。您还会获得一个目录 easy_bmp,其中包含 .bmp 图像文件形式的前 50 张输入照片,以及一个目录 easy_sample_original_bmp,其中包含重新排列之前的前 20 张图像。检查下载链接的注释。

输出

你的程序应该打印 q 行。第 i 行应包含您对第 i 个问题的答案:如果照片已重新排列,则为“是”,否则为“否”。如果您的答案全部符合此格式并且其中至少 75% 是正确的,则您的答案将被接受。

因为输入相当大,所以请随意在本地处理它并仅提交您预先计算的答案(即仅打印输入文件 all.in 的输出的程序)。

注意

下载所有必需文件的链接是http://assets.codeforces.com/files/690/easy_contestant_package.zip