CF185C.Clever Fat Rat

省选/NOI-

通过率:0%

时间限制:2.50s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The Fat Rat and his friend Сerealguy have had a bet whether at least a few oats are going to descend to them by some clever construction. The figure below shows the clever construction.

A more formal description of the clever construction is as follows. The clever construction consists of n rows with scales. The first row has n scales, the second row has (n - 1) scales, the i-th row has (n - i + 1) scales, the last row has exactly one scale. Let's number the scales in each row from the left to the right, starting from 1. Then the value of w__i, k in kilograms (1 ≤ i ≤ n; 1 ≤ k ≤ n - i + 1) is the weight capacity parameter of the k-th scale in the i-th row.

If a body whose mass is not less than w__i, k falls on the scale with weight capacity w__i, k, then the scale breaks. At that anything that the scale has on it, either falls one level down to the left (if possible) or one level down to the right (if possible). In other words, if the scale w__i, k (i < n) breaks, then there are at most two possible variants in which the contents of the scale's pan can fall out: all contents of scale w__i, k falls either on scale w__i + 1, k - 1 (if it exists), or on scale w__i + 1, k (if it exists). If scale w__n, 1 breaks, then all its contents falls right in the Fat Rat's claws. Please note that the scales that are the first and the last in a row, have only one variant of dropping the contents.

Initially, oats are simultaneously put on all scales of the first level. The i-th scale has a__i kilograms of oats put on it. After that the scales start breaking and the oats start falling down in some way. You can consider everything to happen instantly. That is, the scale breaks instantly and the oats also fall instantly.

The Fat Rat is sure that whatever happens, he will not get the oats from the first level. Cerealguy is sure that there is such a scenario, when the rat gets at least some number of the oats. Help the Fat Rat and the Cerealguy. Determine, which one is right.

胖老鼠和他的朋友麦片哥打了个赌:通过某种精巧的构造,是否至少会有少量燕麦最终落到他们手中。下图展示了这种精巧的构造。

该精巧构造的形式化描述如下:它由 nn 行天平组成。第一行有 nn 个天平,第二行有 (n−1)(n-1) 个天平,第 ii 行有 (n−i+1)(n-i+1) 个天平,最后一行恰好只有一个天平。我们从左到右对每行中的天平编号,起始编号为 11。记 wi,kw_{i,k}(单位:千克,其中 1≤i≤n1 \le i \le n,1≤k≤n−i+11 \le k \le n-i+1)为第 ii 行第 kk 个天平的承重参数。

若一个质量不小于 wi,kw_{i,k} 的物体落在承重参数为 wi,kw_{i,k} 的天平上,则该天平会断裂;此时,天平托盘上的所有内容物将向下一级掉落——要么向左下方(若存在),要么向右下方(若存在)。换言之,若天平 wi,kw_{i,k}(其中 i<ni < n)发生断裂,则其托盘上的全部内容物至多有两种下落路径:全部落入天平 wi+1,k−1w_{i+1,k-1}(若该天平存在),或全部落入天平 wi+1,kw_{i+1,k}(若该天平存在)。若最底层唯一的天平 wn,1w_{n,1} 断裂,则其全部内容物将直接落入胖老鼠的爪中。请注意:每行中最左侧与最右侧的天平,其内容物仅有一种下落路径。

初始时,燕麦被同时放置于第一层(即第 11 行)的所有天平上;其中第 ii 个天平上放置了 aia_i 千克燕麦。随后,天平开始逐级断裂,燕麦随之向下坠落(可能存在多种坠落方式)。可认为整个过程瞬时完成:天平断裂瞬时发生,燕麦下落亦瞬时完成。

胖老鼠确信:无论发生何种情况,他都无法从第一层获得任何燕麦。而麦片哥则确信:存在某种坠落路径,使得胖老鼠至少能获得一定数量的燕麦。请帮助胖老鼠与麦片哥判断:谁的观点是正确的?

输入格式

The first line contains a single integer n (1 ≤ n ≤ 50) — the number of rows with scales.

The next line contains n space-separated integers a__i (1 ≤ a__i ≤ 106) — the masses of the oats in kilograms.

The next n lines contain descriptions of the scales: the i-th line contains (n - i + 1) space-separated integers w__i, k (1 ≤ w__i, k ≤ 106) — the weight capacity parameters for the scales that stand on the i-th row, in kilograms.

第一行包含一个整数 nn(1≤n≤501 \leq n \leq 50)—— 表示天平的行数。

第二行包含 nn 个以空格分隔的整数 aia_i(1≤ai≤1061 \leq a_i \leq 10^6)—— 表示每份燕麦的质量(单位:千克)。

接下来的 nn 行描述了天平:第 ii 行包含 (n−i+1)(n - i + 1) 个以空格分隔的整数 wi,kw_{i,k}(1≤wi,k≤1061 \leq w_{i,k} \leq 10^6)—— 表示位于第 ii 行的天平的承重参数(单位:千克)。

输出格式

Print "Fat Rat" if the Fat Rat is right, otherwise print "Cerealguy".

如果“胖老鼠”正确,则输出 “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

说明/提示

Notes to the examples:

  • The first example: the scale with weight capacity 2 gets 1. That means that the lower scale don't break.
  • The second sample: all scales in the top row obviously break. Then the oats fall on the lower row. Their total mass is 4,and that's exactly the weight that the lower scale can "nearly endure". So, as 4  ≥  4, the scale breaks.

示例说明:

  • 第一个示例:承重能力为 2 的天平承载了重量 1,这意味着下方的天平不会损坏。
  • 第二个示例:最上方一行的所有天平显然都会损坏。随后燕麦下落到下方一行,其总质量为 4,而这恰好是下方天平所能“勉强承受”的重量。因此,由于 4≥44 \geq 4,该天平损坏。

输入解题思路,AI测评打分。不知道怎么写?

首页