Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Hanoy2016

Задача Hanoy2016. Ханойські вежі являють собою три стержні. На першому знаходиться N дисків різних розмірів. Верхній диск має розмір 1, наступний 2, і т.д., найнижчий диск має розмір N. Герой олімпіад Ваcиль Пупенко перекладає диски оптимальним способом з першого(стартового) на другий (цільовий) стержень за правилами ханойських веж (за один хід перекладається один диск, не можна класти більший диск на менший). Відомо розташування дисків на певному етапі операції. Допоможіть Васі порахувати кількість перекладань дисків, що вже відбулися.

 

Технічні умови. Програма Hanoy2016 читає з пристрою стандартного введення кількість дисків N (1<= N<=64) і далі через пропуск N чисел, кожне з яких дорівнює 1, 2 або 3 – розташування дисків, починаючи з найменшого. Програма виводить на пристрій стандартного виведення єдине число – кількість перекладань. Якщо задане розташування дисків не траплялось, вивести -1.

 

Приклади

 

Введення 2 3 2

 

Виведення 2

 

Введення 3 2 1 3

 

Виведення -1

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"