← 返回题目列表

Codeforces · 1446/E

E. 恢复时间长

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

一名患者感染了未知疾病。他的身体可以看作是由三角形细胞组成的无限网格,如下所示:

如果两个单元共享一侧,则它们是相邻的。因此,每个单元格 ($$$x$$$, $$$y$$$) 恰好有三个邻居:

- ($$$x+1$$$, $$$y$$$)
- ($$$x-1$$$, $$$y$$$)
- 如果 $$$x$$$ 是偶数,则为 ($$$x+1$$$, $$$y-1$$$),否则为 ($$$x-1$$$, $$$y+1$$$)。

最初,一些细胞被感染,所有其他细胞都是健康的。恢复过程开始。每一秒,对于一个单元格(即使可能有多个单元格可以改变其状态),会发生以下情况之一:

- 至少有 $$$2$$$ 受感染邻居的健康细胞也会被感染。
- 具有至少 $$$2$$$ 健康邻居的受感染细胞也会变得健康。

如果不存在这样的单元,则恢复过程将停止。如果恢复过程停止并且所有细胞都健康,则认为患者已康复。

我们对最坏的情况感兴趣:患者是否有可能永远无法康复,或者如果不可能,康复过程的最长可能持续时间是多少?

输入

第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 250000)$$$ — 受感染细胞的数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个空格分隔的整数 $$$x_i$$$ 和 $$$y_i$$$ $$$(0 \leq x_i, y_i < 500)$$$,表示单元格 $$$(x_i, y_i)$$$ 被感染。所有细胞 $$$(x_i, y_i)$$$ 都是不同的,所有其他细胞都被认为是健康的。

输出

如果有机体有可能永远无法从疾病中完全恢复,请打印 SICK。否则,您应该打印 RECOVERED 并在下一行中输出一个整数 $$$k$$$ — 最长的可能恢复期,以 $$$998244353$$$ 为模。

示例

输入 #1

4
0 0
1 0
2 0
0 1

输出 #1

RECOVERED
4

输入 #2

3
1 0
3 0
1 1

输出 #2

SICK

注意

对于第一个测试用例,下图描述了最长的可能恢复过程。可以证明,不存在长度为 $$$5$$$ 或更长的恢复期,并且有机体在此测试用例中始终恢复。

$$$\hspace{40pt} \downarrow$$$ $$$\hspace{40pt} \downarrow$$$ $$$\hspace{40pt} \downarrow$$$ $$$\hspace{40pt} \downarrow$$$

$$$\hspace{15pt}$$$ 已恢复

对于第二个测试用例,单元格 $$$(2, 0)$$$、$$$(2, 1)$$$、$$$(0, 1)$$$ 可能被感染。之后,没有细胞可以改变其状态,因此答案是“病态”,因为并非所有细胞都是健康的。