Codeforces Round #804 (Div. 2)
3 өдрийн дараа |
E. Үнэг ба оройн зоог
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Сиел үнэг Анхны Тоон Вант Улсын цэнгүүнд уригджээ. Энд Сиелийг оролцуулаад $n$ ширхэг үнэгнүүд ирсэн бөгөөд $i$-р үнэг нь $a_{i}$ настай.
Тэд дугуй ширээнүүдэд тойрон сууж оройн зоог барина. Та үнэгнүүдийг дараах байдлаар хуваарилахыг хүсэж байгаа:
- Үнэг бүр ямар нэг ширээнд суусан байна.
- Ширээ бүрд хамгийн багадаа $3$ үнэг сууна.
- Ширээ бүрийн аль ч зэргэлдээх хоёр үнэгний насны нийлбэр нь анхны тоо байх ёстой.
Хэрвээ $k$ ширхэг $f_{1}$, $f_{2}$, ..., $f_{k}$ үнэгнүүд цагийн зүүний дагуу ширээнд тойрон суусан бол $1 ≤ i ≤ k - 1$-н хувьд: $f_{i}$ ба $f_{i + 1}$ зэргэлдээ, мөн $f_{1}$ ба $f_{k}$ нь зэргэлдээ суусан үнэгнүүд гэсэн үг.
Хэрвээ тодорхойлсон байдлаар үнэгнүүдийг ширээнд хуваарилах боломжтой бол хэрхэн хуваарилах аргыг ол.
Оролт
Эхний мөр нь цэнгүүнд ирсэн үнэгнүүдийн тоо болох $n$ ($3 ≤ n ≤ 200$) бүхэл тоог агуулна.
Хоёр дахь мөр нь $n$ ширхэг $a_{i}$ ($2 ≤ a_{i} ≤ 10^{4}$) бүхэл тоонуудыг агуулна.
Гаралт
Хэрвээ хуваарилалтыг хийх боломжгүй бол "Impossible" гэж хэвлэнэ.
Эсрэг тохиолдолд эхний мөрөнд ширээнүүдийн тоо болох $m$ бүхэл тоог хэвлэнэ. $(1 \leq m \leq \frac{n}{3})$
Дараа нь $m$ мөрүүд хэвлэх ба мөр бүр нь $k$ гэсэн бүхэл тоогоор эхлэнэ. Энэ $k$ тоо нь тухайн ширээнд суух үнэгнүүдийн тоо юм. Ингээд түүний дараа $k$ ширхэг тоонууд хэвлэнэ. Эдгээр нь тухайн ширээнд цагийн зүүний дагуу тойрон суух үнэгнүүдийн дугаар байна.
Хэрвээ хэд хэдэн боломжит зохион байгуулалт байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
4 3 4 8 9
Гаралт
1 4 1 2 4 3
Оролт
5 2 2 2 2 2
Гаралт
Impossible
Оролт
12 2 3 4 5 6 7 8 9 10 11 12 13
Гаралт
1 12 1 2 3 6 5 12 9 8 7 10 11 4
Оролт
24 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Гаралт
3 6 1 2 3 6 5 4 10 7 8 9 12 15 14 13 16 11 10 8 17 18 23 22 19 20 21 24
Тэмдэглэл
Эхний жишээнд тэд нэг ширээнд суух боломжтой. Тэдний нас нь: $3-8-9-4$, зэргэлдээх нийлбэрүүд нь: $11, 17, 13, 7$. Нийлбэрүүд бүгд анхны тоонууд байна.
Хоёр дахь жишээнд $2 + 2 = 4$ нийлбэр анхны тоо биш учраас хуваарилах боломжгүй байна.