QOJ.ac

QOJ

実行時間制限: 3 s メモリ制限: 512 MB 満点: 100

#3471. 土星蜜蜂

統計

土星蜂(Apis saturnii)是一个非常有趣的物种。首先,它们以环状结构筑巢。更准确地说,蜂巢是一个六边形网格,我们将其表示为一个图,其中墙壁是边,墙壁的连接点是顶点。如果我们稍微压扁每个六边形,使其变成一个 $1 \times 2$ 的矩形,那么我们可以为每个顶点分配一个整数坐标,使得顶点 $(i, j)$ 与顶点 $(i, j - 1)$、$(i, j + 1)$ 以及当 $i + j$ 为奇数时与 $(i + 1, j)$ 相邻,或者当 $i + j$ 为偶数时与 $(i - 1, j)$ 相邻。

为了将 $n \times m$ 的网格变成一个环,边缘会首尾相连。因此,如果 $n$ 和 $m$ 都是偶数,以 $(n, j)$ 为端点的边将连接到 $(0, j)$,以 $(i, m)$ 为端点的边将连接到 $(i, 0)$。如果其中一个坐标是奇数,蜜蜂需要扭转网格以使两侧匹配:如果 $n$ 是奇数,则 $(n, j)$ 变为 $(0, j + 1)$;如果 $m$ 是奇数,则 $(i, m)$ 变为 $(i + 1, 0)$。蜂群意识到了握手引理,因此不会尝试建造 $n$ 和 $m$ 均为奇数的蜂巢。参见图 A.1 中的几个蜂巢示例。

图 A.1:蜂巢示例

土星蜂的另一个显著特点是它们如何守卫蜂巢。每只士兵蜂坐在一个顶点上,其任务是控制该顶点及其 3 个相邻顶点。蜂群意识到这需要 $nm/4$ 只蜜蜂,因此这就是蜂群中士兵的数量,但不幸的是,有些蜂巢变得难以守卫,土星蜂拒绝住在那里。

你的任务是确定一个蜂巢是否适合作为蜂群的家。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le m, n \le 10\,000$,$m$ 或 $n$ 为偶数)。

输出格式

如果 $nm/4$ 只蜜蜂可以守卫一个 $n \times m$ 的蜂巢,则输出 “possible”,否则输出 “impossible”。

样例

输入格式 1

4 6

输出格式 1

impossible

输入格式 2

6 4

输出格式 2

possible

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.