Разглеждаме 3 вертикално
поставени колчета
(A, B
и C),
върху които могат да се нанизват дискове. Колчето A
съдържа n
диска, които са от
k различни
размера d1>d2>...>dk,
т.е.
има m1
диска с диаметър
d1, m2
диска с диаметър d2, ..., mk
диска с диаметър dk.
Очевидно m1+m2+...+mk=n.
Първоначално дисковете са нанизани на колчето
A
по реда на намаляване на размера им от долу нагоре (най-долу
има m1
диска с диаметър d1,
след това има m2
диска с диаметър d2, ...).
При един ход един диск може да бъде преместен от едно колче на
друго, но не е позволено диск с по-голям диаметър да бъде поставен върху диск с
по-малък диаметър.
Целта на преместванията е да се
поставят всички дискове върху колчето
B, като през
целия процес на местене да се запазва описаната наредба за размерите.
Колчето C
може да се използва като спомагателно - за поставяне и вземане
на дискове от там при процеса на преместване.
Задача
Напишете програма, която определя минималния брой ходове, чрез които може да се преместят n-те диска от колчето A на колчето B.
Вход
Входният фаил hanoig.in съдържа на първия си ред положителното цяло число k. Вторият ред на файла съдържа k положителни цели числа, разделени с по един интервал, m1 m2 ... mk.
Изход
Изходният файл hanoig.out трябва да съдържа един ред с търсения минимален брой ходове.
Ограничения и пояснения
hanoig.in | hanoig.out |
2 |
8 |
Time limit: 0.1 сек за тест
prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com
Превод на български: Емил Келеведжиев