Codeforces Round #803 (Div. 2)
06:33:55 |
Codeforces Round #804 (Div. 2)
7 өдрийн дараа |
B. Уйтгартай хэсэгчлэл
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $a_{1}, a_{2}, ..., a_{n}$ бүхэл тоон дараалал болон эерэг бүхэл тоо $h$ өгөгдөнө. Таны зорилго бол дарааллыг $2$ хэсэгт хуваах явдал юм. Хуваагдсан хэсгүүд заавал дараалласан элементүүдээс бүтэх албагүй бөгөөд элемент бүр хуваасан $2$ хэсгийн аль нэгэнд нь байх шаардлагатай. Энэ $2$ хэсгийн аль нэг нь хоосон байх боломжтой.
Дараалал дахь тоон байрлалаар $f(a_{i}, a_{j})$ ялгаатай $2$ тооны функц үүсгэе. Хэрвээ $a_{i}$ ба $a_{j}$ нь адил хэсэгт байрлавал $f(a_{i}, a_{j}) = a_{i} + a_{j}$, харин тус тусдаа байрлавал $f(a_{i}, a_{j}) = a_{i} + a_{j} + h$ байна.
Байх боломжтой бүх функц $f$-ийг тодорхойл. Функц $f$-ийн хамгийн их утга болон хамгийн бага утгуудын хоорондын ялгааг чанар гэж нэрлэе.
Таны даалгавар бол өгөгдсөн $a$ дарааллын чанарыг хамгийн бага байхаар $2$ хэсэгт хуваах юм.
Оролт
Эхний мөрөнд $n$, $h$ $(2 ≤ n ≤ 10^{5}, 0 ≤ h ≤ 10^{8})$ бүхэл тоонууд өгөгдөнө.
Хоёр дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан тоонууд $a_{1}, a_{2}, ..., a_{n}$ $(0 ≤ a_{i} ≤ 10^{8})$ өгөгдөнө.
Гаралт
Эхний мөрөнд олох ёстой хамгийн бага чанарыг хэвлэнэ.
Хоёр дахь мөрөнд $2$ хэсгийг тайлбарлан хэвлэнэ. Та $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо хэвлэх ёстой бөгөөд хэрвээ $a_{i}$ эхний хэсэгт багтаж байгаа бол $1$ харин сүүлийн хэсэгт багтаж байгаа бол $2$ гэж хэвлэнэ.
Хэрвээ хэд хэдэн боломжит хари байвал аль нэгийг нь хэвлэнэ үү.
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
3 2 1 2 3
Гаралт
1 1 2 2
Оролт
5 10 0 1 0 2 1
Гаралт
3 2 2 2 2 2
Тэмдэглэл
Эхний жишээнд функц $f$-ийн утгууд: $f(1, 2) = 1 + 2 + 2 = 5$, $f(1, 3) = 1 + 3 + 2 = 6$ ба $f(2, 3) = 2 + 3 = 5$. Тиймээс чанар нь $1$.
Хоёр дахь жишээнд $h$-ийн утга их тул эцсийн хэсгүүдийн аль нэг нь хоосон байх нь ашигтай.