C. Баг болгон хуваах

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

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

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

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

Петя хөл бөмбөгд үнэхээр их дуртай бөгөөд ялангуяа ээж аавыгаа гэртээ байхгүй үед тоглох дуртай байв. Өглөө болгон тэрээр талбай дээр очих бөгөөд найзуудаа цуглуулан бүтэн өдрийн турш тоглодог байжээ. Ингэх зуураа тэд хэсэг завсарлаж хоол унд идэх юм уу гэрийнхээ ажлыг хийдэг байв (жишээлбэл цэцэг услах гэх мэт).

Хөл бөмбөгийн гол нууц нь тоглоом эхлэхээс өмнө багуудыг тэнцүүхэн хуваах юм. Талбай дээр нийтдээ $n$ (Петя-г оруулаад) ширхэг хөвгүүн хөл бөмбөг тоглох бөгөөд хөвгүүн болгон нь хөл бөмбөг тоглох чадвар буюу сөрөг биш $a_{i}$ гэсэн тоогоор илэрхийлэгдэх ажээ (уг тоо нь их байх тусам илүү сайн тоглодог гэсэн үг юм).

Эхний багт байх тоглогчдын тоог $x$, 2-дахь багт байх тоглогчдын тоог $y$ хэмээн тэмдэглэе. Мөн эхний багт байх хөвгүүдийг $p_{i}$ гэж дугаарлах ба 2-дахь багт байх хөвгүүдийг $q_{i}$ гэж дугаарлая. Тэгвэл дараах 3-н нөхцөлийг хангаж байхаар $n$ ширхэг хөвгүүдийг 2 баг болгон хуваасан байвал тэнцүүхэн хуваасан байна гэж үзэх юм:

  • Хөвгүүн болгон нь яг нэг л багын төлөө тоглоно ($x + y = n$).
  • Багуудын тоглогчдын тооны зөрүү нь нэгээс ихгүй байна ($|x - y| ≤ 1$).
  • 2 багт тоглож буй тоглогчдын нийт чадваруудын зөрүү нь талбай дээрх хамгийн сайн тоглогчийн чадварын хэмжээнээс ихгүй байна. Илүү дэлгэрэнгүй:

Та эдгээр хөвгүүдэд туслан 2 тэнцүүхэн багт хувааж өгнө үү. Мөн 2 багын хувьд тэнцүүхэн хуваах арга үргэлж оршин байх юм.

Оролт

Эхний мөрөнд ганц бүхэл тоо $n$ ($2 ≤ n ≤ 10^{5}$) өгөгдөх ба энэ нь талбай дээр байгаа хөвгүүдийн тоог илэрхийлнэ. Дараагийн мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан эерэг бүхэл тоонууд $a_{i}$ ($1 ≤ a_{i} ≤ 10^{4}$)-ууд өгөгдөх ба $i$-р тоо нь $i$-р хөвгүүний хөл бөмбөг тоглох чадварыг илэрхийлнэ.

Гаралт

Гаралтын эхний мөрөнд $x$ бүхэл тоог хэвлэх ба энэ нь эхний багт тоглох хөвгүүдийн тоог илэрхийлнэ. 2-дахь мөрөнд $x$ ширхэг бүхэл тоонуудыг хэвлэх бөгөөд эдгээр нь эхний багт тоглож буй хөвгүүдийн дугааруудыг илэрхийлэх юм. 3-дахь мөрөнд $y$ бүхэл тоог хэвлэх ба энэ нь 2-дахь багт тоглож буй хөвгүүдийн тоог илэрхийлнэ. 4-дэх мөрөнд $y$ ширхэг бүхэл тоонуудыг хэвлэх ба эдгээр нь 2-дахь багт тоглож буй хөвгүүдийн дугааруудыг илэрхийлэх юм. Таны хариулт $x + y = n$, $|x - y| ≤ 1$, болон нийт чадварын хязгаарлалтыг илэрхийлэх 3-н нөхцөлийг биелүүлж байх ёстойг анхаарна уу.

Хэрэв уг бодлогыг бодох олон тооны хариултууд оршин байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

Хөвгүүд нь оролтод тэдгээрийн хөл бөмбөг тоглох чадвар өгөгдсөн дарааллын дагуу 1-ээс эхлэн дугаарлагдсан байна. Та нэг ижил багт харьяалагдах хөвгүүдийн дугааруудыг ямар ч дарааллын дагуу хэвлэсэн болох юм.

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

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

Оролт
3
1 2 1
Гаралт
2
1 2 
1
3 
Оролт
5
2 3 3 1 1
Гаралт
3
4 1 3 
2
5 2 

Тэмдэглэл

Эхний жишээг авч үзье. Энд бид эхний болон 2-р хөвгүүдийг эхний багт оруулах ба 3-р хөвгүүнийг 2-дахь багт оруулах юм. Тэнцүүхэн хуваалтын 3-н нөхцөлийг шалгаж үзье. Эхний хязгаарлалтыг хангасан байна өөрөөр хэлбэл бүх хөвгүүд тоглож байна. 2-дахь хязгаарлалтын хувьд $|2 - 1| = 1 ≤ 1$ байгаа учраас мөн хангасан байна. 3-дахь хязгаарлалтын хувьд $(2 + 1) - (1) = 2 ≤ 2$ байгаа учраас мөн л хангасан байх юм.

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