← 返回题目列表

Codeforces · 185/C

C. 聪明的肥鼠

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

肥鼠和他的朋友 Сerealguy 打赌,是否至少有一些燕麦会通过某种巧妙的构造降临到他们身上。下图展示了巧妙的构造。

巧妙构造的更正式描述如下。这个巧妙的结构由 n 行带有刻度的行组成。第一行有 n 个刻度,第二行有 (n - 1) 个刻度,第 i 行有 (n - i + 1) 个刻度,最后一行只有一个刻度。让我们从左到右对每行秤进行编号,从 1 开始。那么 wi, k 的值(以千克为单位)(1 ≤ i ≤ n; 1 ≤ k ≤ n - i + 1) 就是第 i 行中第 k 个秤的承重能力参数。

如果一个质量不小于 wi, k 的物体落在重量为 wi, k 的秤上,则秤破裂。秤上的任何东西要么向左下降一级(如果可能),要么向右下降一级(如果可能)。换句话说,如果尺度 wi, k (i < n) 破裂,则最多有两种可能的变体,其中尺度平移的内容可能会掉出:尺度 wi, k 的所有内容要么落在尺度 wi + 1, k - 1 (如果存在)上,要么落在尺度 wi + 1, k (如果存在)上。如果scale wn,1破裂,那么它的所有内容都会落入肥鼠的爪子中。请注意,连续的第一个和最后一个秤只有一种删除内容的变体。

最初,燕麦同时放在第一层的所有秤上。第 i 个秤上放了 ai 公斤燕麦。之后,鳞片开始破裂,燕麦开始以某种方式掉落。你可以认为一切都会立即发生。也就是鳞片瞬间破裂,燕麦也瞬间掉落。

肥鼠确信无论发生什么,他都不会从第一层得到燕麦。 Cerealguy 确信,当老鼠至少得到一定数量的燕麦时,就会出现这种情况。帮助肥老鼠和麦片佬。确定一下,哪一个是正确的。

输入

第一行包含一个整数 n (1 ≤ n ≤ 50) — 带刻度的行数。

下一行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 106) — 燕麦的质量(以千克为单位)。

接下来的 n 行包含秤的描述:第 i 行包含 (n - i + 1) 个空格分隔的整数 wi, k (1 ≤ wi, k ≤ 106) — 第 i 行秤的重量容量参数,单位为千克。

输出

如果 Fat Rat 正确,则打印“Fat Rat”,否则打印“Cerealguy”。

示例

输入 #1

1
1
2

输出 #1

Fat Rat

输入 #2

2
2 2
1 2
4

输出 #2

Cerealguy

输入 #3

2
2 2
1 2
5

输出 #3

Fat Rat

注意

示例注释:

- 第一个示例:承重能力为 2 的秤得到 1。这意味着较低的秤不会破裂。
- 第二个样本:顶行的所有鳞片明显断裂。然后燕麦落在下面一排。它们的总质量是4,这正是下秤“几乎可以承受”的重量。因此,当 4  ≥  4 时,尺度就破裂了。