QOJ.ac

QOJ

حد الوقت: 10 s حد الذاكرة: 512 MB مجموع النقاط: 100

#8851. 幂等过滤器

الإحصائيات

我们考虑对由六边形像素组成的单色图像进行操作,每个像素的颜色要么是黑色,要么是白色。由于像素的形状,每个像素恰好有六个邻居(例如,与它共享一条边的像素)。

“过滤”(Filtering)是一种根据像素自身及其六个邻居的颜色来确定该像素颜色的操作。下面展示了过滤的示例。

示例 1:当一个像素的所有邻居均为白色时,将该像素涂成白色。否则,颜色保持不变。

同时对所有像素执行此操作会产生“降噪”(noise canceling)效果,它会去除孤立的黑色像素。

示例 2:当一个像素的所有邻居均为黑色时,将该像素涂成白色。否则,颜色保持不变。

同时对所有像素执行此操作会产生“边缘检测”(edge detection)效果,它只保留填充区域的边缘。

示例 3:将像素涂成其正下方像素的颜色,忽略其他任何邻居。

同时对所有像素执行此操作会产生将整个图像“向上移动”(shifting up)一个像素的效果。

对任何图像应用某些过滤器(例如“降噪”和“边缘检测”)两次,产生的结果与仅应用一次的结果完全相同。我们称这类过滤器为幂等的(idempotent)。“向上移动”过滤器不是幂等的,因为每次重复应用都会使图像向上移动一个像素。

你的任务是确定给定的过滤器是否为幂等。

输入格式

输入包含多个数据集。数据集的数量少于 100 个。每个数据集是一个表示过滤器的字符串,格式如下(数字之间没有空格)。

$c_i$ 为 ‘0’(代表黑色)或 ‘1’(代表白色),表示当像素及其六个邻居的二进制表示为 $i$ 时,过滤器的输出。像素到位的映射如下:

二进制表示 $i$ 定义为 $i = \sum_{j=0}^{6} bit_j \times 2^j$,其中当对应像素为黑色时 $bit_j$ 为 0,为白色时 $bit_j$ 为 1。注意,过滤器应用于中心像素,即 $bit_3$。

输入以仅包含一个 “#” 的行结束。

输出格式

对于每个数据集,如果给定的过滤器是幂等的,则在一行中打印 “yes”,否则打印 “no”(引号仅用于清晰说明)。

样例

输入 1

00000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000111111111
10000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111
01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
#

输出 1

yes
yes
no

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.