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


Годинник
 
Hanoy2015

Задача Hanoy2015. Герой задачі Hanoysotf Вася Пупкін вирішив удосконалити свої Ханойські вежі. Він замовив N дисків та три стержні, але коли отримав замовлення, здивуванню Васі не було межі. Деякі диски виявились однаковими! Вася вирішив, що при перекладанні можна диск покласти на диск не меншого розміру. Допоможіть Васі обчислити мінімальну кількість перекладань дисків з першого стержня на другий. Нагадаємо, що за один хід можна перекласти лише один диск. Дозволено перекладати диск з будь-якого стержня на будь-який, але заборонено класти більший диск на менший.

Технічні умови. Програма Hanoy2015 читає з клавіатури кількість дисків N (1<=N<=64) і далі N натуральних чисел, не більших 10000 – діаметри дисків. Програма виводить на екран шукану мінімальну кількість перекладань.

Приклад.

Введення 7 3 5 3 5 3 3 3

Виведення 12

Коментар. На початку на першому стержні буде розміщено 2 диски діаметром 5, а на них 5 дисків діаметром 3. Перекладаємо 5 менших дисків на третій стержень, потім 2 більших диски на стержень 2, потім 5 менших дисків з третього стержня на другий.


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