D. Шатрын хүү

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

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

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

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

Шатрын хөлгийн хамгийн доод мөрийн нэгэн нүдэнд шатрын хүү байрлаж байв. Уг хүү нь 2 янзаар нүүнэ: зүүн дээш болон баруун дээш гэсэн 2 янзаар нүүнэ. Уг шатрын хүү нь хамгийн доод мөрийн аль нүднээс нүүж эхлэхээ өөрөө сонгож болох юм. Түүнчлэн шатрын хөлгийн нүд болгонд 0-ээс 9 хүртэлх тооны вандуй байрлаж байгаа юм. Шатрын хүү аль болох олон тооны вандуй цуглуулан хамгийн дээд мөрөнд очихыг хүсэж байв. Хамгийн дээд мөрөнд очмогцоо тэрээр цуглуулсан вандуйнуудаа өөртөө болон өөрийн $k$ ширхэг ах дүү нартаа хуваах бөгөөд өөрөөр хэлбэл цуглуулсан вандуйны тоо нь заавал $k + 1$-д хуваагддаг байх ёстой. Шатрын хүүгийн цуглуулж болох хамгийн их тооны вандуй болон үүнийг хийх нүүдлүүдийг олно уу.

Шатрын хүү нь хөлгөөс вандуйнуудыг авч хаяж болохгүй. Мөн шатрын хүү нь хөлгийн ямар нэгэн нүдэнд очмогцоо (эхний болон сүүлийн нүднүүдийн хувьд мөн адил) тухайн нүдэнд байх бүх вандуйнуудыг авах шаардлагатай юм.

Оролт

Эхний мөрөнд шатрын хөлгийн мөр болон баганын тоо, шатрын хүүгийн ах дүүсийн тоо болох 3-н бүхэл тоо $n$, $m$, $k$ ($2 ≤ n, m ≤ 100, 0 ≤ k ≤ 10$) өгөгдөнө. Дараа нь өгөгдөх $n$ мөрийн мөр болгонд 0-ээс 9 хүртэлх $m$ ширхэг тоо хоорондоо зайгаар тусгаарлагдаагүй байдлаар өгөгдөх ба эдгээр нь шатрын хөлгийг дүрсэлнэ. Нүд болгон нь уг нүдэнд агуулагдах вандуйны тоо болох ганц тоог агуулсан байна. Шатрын хөлгийн эхний мөр гэдэгт хамгийн доор байх мөрийг ойлгоно.

Гаралт

Хэрэв хамгийн дээд мөрөнд $k + 1$-д хуваагддаг байх тооны вандуйнууд цуглуулан очиж чадахгүй бол $-1$ гэж хэвлэнэ үү.

Бусад тохиолдолд, эхний мөрөнд шатрын хүүгийн цуглуулсан вандуйн тоо нь $k + 1$-д хуваагддаг байхаар түүний цуглуулж чадах боломжит хамгийн их вандуйны тоог хэвлэх юм. 2-дахь мөрөнд шатрын хүү хамгийн доод мөрийн аль нүднээс эхэлж нүүхийг хэвлэх бөгөөд хамгийн доод мөрөнд байрлах тухайн нүдний баганын дугаарыг хэвлэх юм. Баганууд нь зүүнээс баруун уруу $1$-ээс эхлэн бүхэл тоонуудаар дугаарлагдсан байна. 3-дахь мөрөнд шатрын хүүгийн нүүдлүүдийг дүрслэх бөгөөд $n - 1$ ширхэг тэмдэгт хэвлэнэ. Хэрэв шатрын хүү зүүн дээш нүүх бол $L$, хэрэв баруун дээш нүүх бол $R$ гэж хэвлэнэ. Хэрэв уг бодлогыг бодох хэд хэдэн бодолт байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

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

Оролт
3 3 1
123
456
789
Гаралт
16
2
RL
Оролт
3 3 0
123
456
789
Гаралт
17
3
LR
Оролт
2 2 10
98
75
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...