Различия

Здесь показаны различия между выбранной ревизией и текущей версией данной страницы.

--- подготовка_к_олимпиаде._тур_1 [2013/10/17 21:44]
Пронин Роман
+++ подготовка_к_олимпиаде._тур_1 [2013/10/17 22:09] (текущий)
Пронин Роман
@@ Строка 10: / Строка 10: @@
 ^Пример ввода^Пример вывода^
 |10 15 -10 -5| 40|
 **2. Новая столешница**\\
 Владелец трактира "Залатанный барабан" Чарли решил изменить форму столешницы стойки бара с прямоугольной на треугольную, чтобы ему не приходилось вставать со стула, когда он собирает кружки, оставленные посетителями на углу барной стойки. Но новую столешницу нужно внести в трактир через какое-нибудь окно или дверь.
 Напишите программу, которая определяет по размерам столешницы и проема в стене, можно ли внести столешницу в трактир через этот проем. Толщину столешницы считать несущественной. Столешницу можно поворачивать при затаскивании любым образом.\\
@@ Строка 22: / Строка 24: @@
 ^Пример ввода^Пример вывода^
-|30 30 40\\ 10 205|YES|
+|30 30 40\\ 10 20|YES|
 |30 30 40\\ 10 19 |NO|
@@ Строка 41: / Строка 43: @@
 Пояснение к примеру: Числа, которые появляются в прорезях при движении ползунка от самой левой возможной позиции до самой правой: 7+3, 11+5, 4+15, 3+2, 5+1, 15+0. Число 25 не может появиться в прорези ползунка из ограничителей на концах линейки. Максимум суммы чисел в прорезях достигается на числах 4 и 15.
+**4. Пизанская башня **\\
+Многим из вас, наверное, известна легенда про Ханойскую башню. Легенда гласит, что в одном далеком монастыре находится бронзовый диск, на котором закреплены три алмазных стержня. Давным-давно, в самом начале времен, монахи этого монастыря провинились перед богами. Разгневанные боги положили n дисков на один из стержней, все диски имели разные радиусы и были расположены по убыванию радиуса — самый большой диск лежал снизу, на нем диск поменьше, … , самый маленький диск располагался сверху. Монахи должны перекладывать диски между стержнями, причем каждый раз должны класть диск либо на пустой стержень, либо поверх большего диска. Как только все n дисков будут переложены со стержня, на который боги сложили их, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.\\
+Однако недавно Петя прочитал новую версию легенды. Согласно этой легенде, в Пизанской башне есть аналогичная головоломка, но второй стержень у нее наклонен. Со второго стержня можно снимать сразу несколько дисков, лежащих сверху, и перекладывать их вместе, не меняя порядка, на другой стержень. При этом группу дисков также можно перекладывать либо на пустой стержень, либо на диск, который больше нижнего из перекладываемых дисков.
+По легенде, когда все диски будут перенесены с первого стержня на третий, Пизанская башня перестанет наклоняться и начнет стоять ровно.\\
+Петю заинтересовало, за какое минимальное число действий можно перенести все диски с первого стержня Пизанской головоломки на третий. Помогите ему выяснить это.\\
+//Формат ввода//\\
+Во входном файле задано единственное натуральное число n (1 ≤ n ≤ 40) — количество дисков.\\
+//Формат выводa//\\
+Выведите единственное число — минимальное число перекладываний, необходимое для того, чтобы все диски оказались на третьем стержне.
+^Пример ввода^Пример вывода^
+|3 | 5|
+В примере можно действовать следующим образом: переложить маленький диск с первого стержня на третий, затем средний диск с первого на второй, затем маленький с третьего на второй (поверх среднего), затем большой диск с первого на третий, и, наконец, последним действием пару дисков со второго стержня на третий. Всего необходимо пять действий.

База знаний гимназии 1 им. Барсукова

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы