C. Ухаалаг Бүдүүн Харх

хугацааны хязгаарлалт 2.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бүдүүн Харх болон түүний найз Буудайхан хоёр ямар нэгэн ухаалаг байгууламж ашиглан жаахан овьёос ч болохноо унаж ирэх эсэхээр мөрийцжээ. Ухаалаг байгуулажийг доорх зурагт үзүүллээ.

Ухаалаг байгууламжын илүү албан ёсны тайлбарыг хэлэе. Ухаалаг байгууламж нь жинлүүрүүдтэй $n$ мөрөөс тогтно. Эхний мөр $n$ жинлүүрийг агуулна, дараагийн мөр $(n -1)$ жинлүүрийг, $i$ дахь мөр $(n - i + 1)$ жинлүүрийг, хамгийн сүүлийн мөр яг нэг жинлүүрийг агуулна. Мөр бүрд байгаа жинлүүрүүдийг зүүнээс нь баруунруу 1-ээс эхлэн дугаарлая. Тэгвэл $w_{i, k} (1 <= i <= n; i <= k <= n - i + 1)$ нь $i$ дахь мөрийн $k$ дугаар жинлүүрийн жингийн хягаарыг килограммаар заана.

Хэрэв $w_{i, k}$ жингийн хязгаартай жинлүүр дээр $w_{i, k}$-аас их жинтэй бие унахад жинлүүр эвдэрдэг. Тийм зүйл болвол жинлүүр дээр байсан бүх зүйлүүд нэг доошоо зүүн талруугаа (хэрэв боломжтой бол) унадаг эсвэл нэг доошоор баруун талруугаа (хэрэв боломжтой бол) унадаг. Өөрөөр хэлбэл $w_{i, k} (i < n)$ жинлүүр эвдэрвэл жинлүүрийн тавцан дээр байгаа зүйлүүд унах хоёрхон боломж байгаа: $w_{i, k}$ жинлүүрийн бүх зүйлүүд $w_{i + 1, k - 1}$ (хэрэв байвал) жинлүүр дээр унана эсвэл $w_{i + 1, k}$ (хэрэв байвал) жинлүүр дээр унадаг. Хэрэв $w_{n, 1}$ жинлүүр эвдэрвэл бүх зүйлүүд нь Бүдүүн Хархын гарт орно. Мөрийн хамгийн эхний болон төгсгөлийн жинлүүрийн хувьд доторх нь унах ганц л боломжтой гэдгийг анхаар.

Эхлээд нэг дүгээр мөрний бүх жинлүүр дээр овьёосууд зэрэг тавигдана. $i$ дахь жинлүүр дээр $a_i$ килограмм ачаа тавигдана. Дараагаар нь жинлүүрүүд эвдэрч, овьёосууд доош унаж эхлэнэ. Та бүх зүйлүүд маш хурдан болж өнгөрнө гэж бодож болно. Юу гэсэн үг вэ гэвэл жинлүүр эвдэрвэл овьёос ч шууд унана.

Бүдүүн Харх юу ч тохиолдсон эхний эгнээний овьёосыг авахгүй гэдэгтээ итгэлтэй байгаа. Буудайхан, Харх заримыг авах тохиодол байгаа гэдэгт итгэлтэй байгаа. Бүдүүн Харх болон Буудайханд туслаач. Хэн нь зөв болохыг тодорхойл.

Оролт

Жинлүүрүүдтэй мөрүүдийн тоо $n (1 <= n <= 50)$, ганц бүхэл тоо эхний мөрөнд байна.

Дараагийн мөрөнд килограммаар овьёосуудын жинг заах $n$ ширхэг $a_i$ тоо хоосон зайгаар тусгаарлагдан өгөгдөнө.

Дараагийн $n$ мөрөнд жинлүүрүүдийн талаарх мэдээлэл өгөгдөнө: $i$ дахь мөр $(n - i + 1)$ хоосон зайгаар тусгаарлагдсан, килограммаар $i$ дахь мөрөнд байгаа жинлүүрүүдийн жингийн хязгааруудыг заах бүхэл тоо $w_{i, k} (1 <= w_{i, k} <= 10^6)$ байна.

Гаралт

Хэрэв Бүдүүн Хархын зөв бол "Fat Rat" үгүй бол "Cerealguy" гэж хэвлэ.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
1
1
2
Гаралт
Fat Rat
Оролт
2
2 2
1 2
4
Гаралт
Cerealguy
Оролт
2
2 2
1 2
5
Гаралт
Fat Rat

Тэмдэглэл

Жишээнүүдийг тайлбарлавал:

  • Эхний жишээ: 2 хязгаартай жинлүүр нэгийг авна. Энэ нь доорх жинлүүр эвдрэхгүй гэсэн үг.

  • Хоёр дугаар жишээ: Хамгийн дээд талын бүх жинлүүрүүд мэдээжээр эвдэрнэ. Овьёосууд доорх жинлүүрүүд дээр унана. Тэдний нийт жин 4 ба энэ нь доорх жинлүүрийн бараг барьж чадах хэмжээ. Тиймээс $4 >= 4$ тул жинлүүр эвдэрнэ.

Сэтгэгдлүүдийг ачааллаж байна...