Codeforces Round #803 (Div. 2)
05:07:00 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
D. Ширээний теннис
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Петя болон Жена ширээний теннис тоглох дуртай. Нэг тоглолт нь дараах дүрмийн дагуу явагдана: нэг тоглолт хэд хэдэн сэтээс бүрдэх ба сэт бүр хэд хэдэн давуулалтаас бүрдэнэ. Нэг давуулалтад тоглогчдын аль нэг нь хожих ба тэр тоглогч нэг оноо авна. Тоглогчдын аль нэг нь $t$ оноотой болмогц тэр тоглогч сэт-д хожих ба дараагийн сэт эхэлж хоёр тоглогчийн оноо 0 болно. Аль нэг тоглогч нийт $s$ сэтд хожвол тэр тоглогч тоглолтонд хожиж тоглолт дуусна. Энд $s$ ба $t$ нь эерэг бүхэл тоонууд.
Илүү сонирхолтой болгохын тулд тоглолт бүрийн өмнө Петя Жена хоёр шинэ $s$ ба $t$ тоонууд сонгоно. Үүнээс гадна түүхийн төлөө тэд тоглолт бүрийн бичлэгийг хадгалах буюу давуулалт бүрд ялагчийг бичиж авна. Давуулалтын ялагчид цаг хугацааны дараалалтайгаар тэмдэглэгдэнэ. Тэмдэглэлд аль нэг тоглогч нь $t$ оноотой болмогц сэт дуусах ба аль нэг тоглогч $s$ сэтд хожмогц тоглолт дуусна.
Петя Жена хоёр хуучин тоглолтын тэмдэглэл олсон. Харамсалтай нь тэмдэглэлд байгаа давуулалтын дараалал нь сэтүүдэд хуваагдаагүй ба уг тоглолтонд зориулсан $s$ ба $t$ тоонууд байхгүй байсан. Тоглогчид одоо $s$ ба $t$ тоонуудын утга хэд байх ёстой юм бол гэж гайхаж байна. Та боломжит бүх боломжуудыг тодорхойлж чадах уу?
Оролт
Эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ байх ба давуулалтуудын дарааллын урт ($1 ≤ n ≤ 10^{5}$).
Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утга $a_{i}$ байна. Хэрвээ $a_{i} = 1$ байвал $i$-р давуулалтанд Петя хожсон гэсэн үг ба хэрвээ $a_{i} = 2$ байвал $i$-р давуулалтанд Жена хожсон гэсэн үг.
Өгөгдсөн тэмдэглэлд харгалзах $s$ ба $t$ тоонуудын боломж хамгийн багадаа нэг байх албагүй.
Гаралт
$s$ ба $t$ тоонуудын хувьд боломжуудын тоог илэрхийлэх нэг тоо $k$-г эхний мөрөнд хэвлэ.
Дараагийн $k$ мөр бүрт хоёр бүхэл тоон утга $s_{i}$ ба $t_{i}$ байх ба $s$ ба $t$ тоонуудын боломж. Боломжуудыг $s_{i}$-н өсөх дарааллаар хэвлэх ба тэнцүү $s_{i}$-тэй байвал $t_{i}$-н өсөх дарааллаар хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
5 1 2 1 2 1
Гаралт
2 1 3 3 1
Оролт
4 1 1 1 1
Гаралт
3 1 4 2 2 4 1
Оролт
4 1 2 1 2
Гаралт
0
Оролт
8 2 1 2 1 1 1 1 1
Гаралт
3 1 6 2 3 6 1