Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
E. Чихэрнүүүдээр тоглосон нь
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Иахуб нэгэн сонирхолтой тоглоом тоглож байв. Одоогоор түүнд $1, 2, 3, ... , n$ дугаарлагдсан $n$ ширхэг хайрцагнууд байв. Хайрцаг бүрт $a_1, a_2, ... , a_n$ дарааллаар тодорхойлогдсон хэдэн ширхэг чихэр байсан. $a_k$ тоо $k$ хайрцган дахь чихэрний тоо ширхэгийг илэрхийлнэ.
Тоглоомны зорилго нь бүх чихрийг яг хоёр хайрцганд шилжүүлэх юм. Үлдсэн $n-2$ ширхэг хайрцгууд $0$ чихэр агуулах ёстой. Иахуб хэд хэдэн үйлдэл хийх ($0$ байж болно) зөвшөөрөлтэй. Хөдөлгөөн бүрээр тэр $i$ ба $j$ гэсэн $a_i ≤ a_j$ байх хоёр ялгаатай хайрцаг сонгож авна. Тэгээд Иахуб $j$ хайрцагнаас $i$ хайрцаг руу яг $a_i$ чихэр шилжүүлнэ. Хэрэв хайрцагнууд тэнцүү тооны чихэртэй байвал $j$ дугаартай хайрцаг хоосон болох нь тодорхой.
Чиний даалгавар бол Иахубд түүнд тоглоомны зорилгыг биелүүлэх үйлдлүүдийг зааж өгөх юм. Хэрэв Иахуб өгөгдсөн хайрцагнуудаар тоглоод бодлогод хожиж чадахгүй байвал $-1$ гэж хэвлээрэй. Хэрэв шийд оршин байгаа нөхцөлд та заавал шийдийн хамгийн бага утгыг хэвлэх шаардлагагүйг анхаарна уу.
Оролт
Эхний мөрөнд бүхэл тоо $n$ ($3 ≤ n ≤ 1000$) байна. Дараагийн мөр $n$ ширхэг дарааллын гишүүд болох сөрөг биш $a_1, a_2, ... , a_n$ тоонуудыг агуулна. $a$ дараалал дахь бүх тоонуудын нийлбэр $10^6$ аас их байх нь батлагдсан болно.
Гаралт
Шийд оршин байхгүй тохиолдолд $-1$ хэвлээрэй. Өөр тохиолдолд гаралтын эхний мөрөнд шийдийн нийт үйлдлийн тоог илэрхийлэх $c$ ($0 ≤ c ≤ 10^6$) бүхэл тоог хэвлэнэ. Дараагийн $c$ мөр тус бүр $i$ ба $j$ ($1 ≤ i, j ≤ n$, $i ≠ j$) гэсэн $2$ ширхэг бүхэл тоонуудыг агуулах хэрэгтэй. $k$ дугаар мөрөн дэх $i$, $j$ бүхэл тоонууд бол $k$ дугаар үйлдлийг $j$ хайрцагнаас $i$ хайрцаг руу чихэр шилжүүлэх үйлдэл болохыг илэрхийлж байгаа юм.
Орчуулсан: Энхдүүрэн
Жишээ тэстүүд
Оролт
3 3 6 9
Гаралт
2 2 3 1 3
Оролт
3 0 1 0
Гаралт
-1
Оролт
4 0 1 1 0
Гаралт
0
Тэмдэглэл
For the first sample, after the first move the boxes will contain 3, 12 and 3 candies. After the second move, the boxes will contain 6, 12 and 0 candies. Now all candies are in exactly 2 boxes.
For the second sample, you can observe that the given configuration is not valid, as all candies are in a single box and they should be in two boxes. Also, any move won't change the configuration, so there exists no solution.
For the third sample, all candies are already in 2 boxes. Hence, no move is needed.