D. Лам нарт туслаарай!

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

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

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

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

Хаант улсаас холын холд алдарт Лио Шан хийд байдаг. Эрт дээр үед бурхад хийдэд гурван алмазан шон байрлуулсан. Бурхад бас $n$ ширхэг өөр диамерттэй алтан дискүүдийг эхний шонд нь доороос нь дээшээ диаметр нь буурахаар байршуулсан. Түүнчлэн бурхад эхний шонгоос гуравдах шонруу дараах дүрмүүдээр шилжүүл гэж тушаасан :

  • Нэг үйлдлээр нэг л диск зөөнө.
  • Жижиг дискэн дээр том дискийг тавьж болохгүй

Бурхны тушаал ирснээс хойш хэнч биелүүлэхгүй бол юу тохиолдохыг сонирхож байсангүй. Зарим хүмүүс дэлхий ертөнцөд энх тайван, мөнхийн аз жаргал ирнэ гэж амласан, зарим нь Хаант улс сүйрэлтэй нүүр тулна гэж таамагласан. Хүн болгон тушаалыг $2^{n} - 1$ үйлдлээс бага үйлдлээр хийж чадахгүй гэдгийг мэдэж байсан ба хүмүүс сүйрлээс айж эмээхээс өмнө залхуу Лио Шан хийдийн лам нар хэзээ ч оролдож үзээгүй байв.

Хийдийн цэцэн лам Ку Сиэн Сүн зарим дискийн ирмэгүүдийг зүсч өөр эд зүйлсэд хэрэглэчихэж. Түүнчлэн хийдэд жилжингээ байна гэдэг уйтгартай юм. Ку Сиэн Сүн ямар том алдаа хийснээ хожим ухаарав : Зарим дискнүүдийн диаметр ижилхэн болчихож. Ингэснээр зарим үйлдлүүд хийгдэх боломжгүй болсон (гэхдээ, бурхад хэзээ ч ижилхэн хэмжээтэй дискийг тавихыг хориглож байгаагүй). Тэгэхээр сүйрэл бурхдын төлөвлөж байснаас хамаагүй эрт болно гэсэн үг юм.

Цэцэн лам өмнө нь болсон явдлыг хэзээ ч давтахгүй хэмээн хөгшин цэцэн Пикиведиа шулмаас тушаалыг шийдвэрлэхийг гуйсан юм. Харамсалтай нь тэр юу ч хийж чадаагүй учир таны тусламж түүнд хэрэг болоод байна.

Таны даалгавар бол тушаалыг биелүүлэхийн тулд хамгийн багадаа хэдэн үйлдэх шаардах болон үйлдлүүдийг олж өгөх юм. Эхний шонд байсан пискнүүдийг гуравдугаар шонд шилжүүлж дууссаны дараа яг анхны хэлбэртэйгээ ижилхэн харагдах ёстой бөгөөд ижил диаметртай дискүүдийг дээр нь байрлууж болно.

Оролт

Эхний мөрөнд $n$ - дискүүдийн дугаар ($1 ≤ n ≤ 20$). Дараагийн мөр $n$ тоо $d_{i}$ - дискүүдийг зүссэний дараах диаметрүүд. Диамертүүд доороос дээш өгөгдөнө. ($1 ≤ d_{i} ≤ 20$, түүнчлэн, $1 ≤ i < n$ хувьд $d_{i} ≥ d_{i + 1}$ байна).

Гаралт

Эхний мөрөнд $m$ - бурхны тушаалыг биелүүлэхэд шаардлагатай хамгийн бага үйлдлийн тоо. Дараагийн $m$ мөрөнд үйлдлүүдийг илэрхийлэх зайгаар тусгаарлагдсан хоёр тоо $s_{i}$ болон $t_{i}$ харгалзан аль шонгоос аль шонд хамгийн дээд дискийг шилжүүлсэн болох мэдээлэл ($1 ≤ s_{i}, t_{i} ≤ 3$, $s_{i} ≠ t_{i}$).

Орчуулсан: Б.Алтангэрэл

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

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

Тэмдэглэл

Гуравдах жишээнд анхаарлаа хандуулъя. Бид гурван үйлдлээр шилжүүлж болох ч гэсэн эхний шонгоос гуравдах шонд шилжүүлсний дараа яг анхны хэлбэртэй байх ёстой.

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