Здесь показаны различия между выбранной ревизией и текущей версией данной страницы.
подготовка_к_олимпиаде._тур_1 [2013/10/17 21:37] Пронин Роман |
подготовка_к_олимпиаде._тур_1 [2013/10/17 22:09] (текущий) Пронин Роман |
||
---|---|---|---|
Строка 2: | Строка 2: | ||
{{ :disk.png?170|}}Плоский мир имеет форму диска. Существует только одна дорога, ведущая с севера на юг диска. Эта дорога проходит через центр диска и её называют Осевой. Остальные дороги проложены с запада на восток или с востока на запад от городов Плоского мира до Осевой дороги. Если два города не расположены на одном отрезке дороги, ведущем до Осевой дороги, то, чтобы добраться из одного города в другой, путешественникам нужно сначала дойти до Осевой дороги, затем дойти до дороги, ведущей в нужный город, и затем по ней дойти до города. | {{ :disk.png?170|}}Плоский мир имеет форму диска. Существует только одна дорога, ведущая с севера на юг диска. Эта дорога проходит через центр диска и её называют Осевой. Остальные дороги проложены с запада на восток или с востока на запад от городов Плоского мира до Осевой дороги. Если два города не расположены на одном отрезке дороги, ведущем до Осевой дороги, то, чтобы добраться из одного города в другой, путешественникам нужно сначала дойти до Осевой дороги, затем дойти до дороги, ведущей в нужный город, и затем по ней дойти до города. | ||
- | Установим систему координат следующим образом. Центр диска имеет координаты (0,0). Ось Y совпадает с Осевой дорогой. Пусть один город имеет координаты (X<sub>1</sub>, Y<sub>1</sub>), а другой город – координаты (X<sub>2</sub>, Y<sub>2</sub>). Тогда расстояние между городами, у которых Y<sub>1</sub> ≠ Y<sub>2</sub>, вычисляется по формуле |X<sub>1</sub>| + |X<sub>2</sub>| + |Y<sub>1</sub>−Y<sub>2</sub>2|, а расстояние между городами, у которых Y<sub>1</sub> = Y<sub>2</sub>, вычисляется по формуле |X<sub>1</sub> − X<sub>2</sub>|, где |a| означает абсолютное значение (модуль) числа a. | + | Установим систему координат следующим образом. Центр диска имеет координаты (0,0). Ось Y совпадает с Осевой дорогой. Пусть один город имеет координаты (X<sub>1</sub>, Y<sub>1</sub>), а другой город – координаты (X<sub>2</sub>, Y<sub>2</sub>). Тогда расстояние между городами, у которых Y<sub>1</sub> ≠ Y<sub>2</sub>, вычисляется по формуле |X<sub>1</sub>| + |X<sub>2</sub>| + |Y<sub>1</sub>−Y<sub>2</sub>|, а расстояние между городами, у которых Y<sub>1</sub> = Y<sub>2</sub>, вычисляется по формуле |X<sub>1</sub> − X<sub>2</sub>|, где |a| означает абсолютное значение (модуль) числа a. |
Напишите программу, определяющую расстояние, которое нужно пройти по дорогам, чтобы попасть из города с координатами (X<sub>1</sub>, Y<sub>1</sub>) в город с координатами (X<sub>2</sub>, Y<sub>2</sub>).\\ | Напишите программу, определяющую расстояние, которое нужно пройти по дорогам, чтобы попасть из города с координатами (X<sub>1</sub>, Y<sub>1</sub>) в город с координатами (X<sub>2</sub>, Y<sub>2</sub>).\\ | ||
- | **Формат ввода**\\ | + | //Формат ввода//\\ |
Первая строка ввода содержит четыре целых числа X<sub>1</sub>, Y<sub>1</sub>, X<sub>2</sub>, Y<sub>2</sub> (0 ≤ X1<sup>2</sup>+Y1<sup>2</sup> ≤ 10<sup>8</sup>, 0 ≤ X2<sup>2</sup>+Y2<sup>2</sup> ≤ 10<sup>8</sup>) – координаты двух городов.\\ | Первая строка ввода содержит четыре целых числа X<sub>1</sub>, Y<sub>1</sub>, X<sub>2</sub>, Y<sub>2</sub> (0 ≤ X1<sup>2</sup>+Y1<sup>2</sup> ≤ 10<sup>8</sup>, 0 ≤ X2<sup>2</sup>+Y2<sup>2</sup> ≤ 10<sup>8</sup>) – координаты двух городов.\\ | ||
- | **Формат вывода**\\ | + | //Формат вывода//\\ |
В первой строке вывести одно целое число – расстояние между городами по дорогам. | В первой строке вывести одно целое число – расстояние между городами по дорогам. | ||
+ | ^Пример ввода^Пример вывода^ | ||
+ | |10 15 -10 -5| 40| | ||
- | **2. Шифр.** | + | **2. Новая столешница**\\ |
+ | |||
+ | Владелец трактира "Залатанный барабан" Чарли решил изменить форму столешницы стойки бара с прямоугольной на треугольную, чтобы ему не приходилось вставать со стула, когда он собирает кружки, оставленные посетителями на углу барной стойки. Но новую столешницу нужно внести в трактир через какое-нибудь окно или дверь. | ||
+ | Напишите программу, которая определяет по размерам столешницы и проема в стене, можно ли внести столешницу в трактир через этот проем. Толщину столешницы считать несущественной. Столешницу можно поворачивать при затаскивании любым образом.\\ | ||
+ | //Формат ввода//\\ | ||
+ | Первая строка ввода содержит три целых числа A, B, C (1 ≤ A ≤ B ≤ C ≤ 1000, A+B > C) – размеры сторон треугольной столешницы. Вторая строка ввода содержит два целых числа W, H (1 ≤ W, H ≤ 1000) – размеры прямоугольного проема в стене трактира. | ||
+ | //Формат вывода// | ||
+ | В первой строке вывести сообщение YES, если столешницу можно пронести в проем, иначе вывести сообщение NO. | ||
+ | |||
+ | |||
+ | ^Пример ввода^Пример вывода^ | ||
+ | |30 30 40\\ 10 20|YES| | ||
+ | |30 30 40\\ 10 19 |NO| | ||
+ | |||
+ | |||
+ | |||
+ | **3. Шифр.** | ||
Для открытия замка сейфа в компьютерной игре из серии "Побег из комнаты" нужно найти шифр. Имеется подсказка – линейка с нанесенными на ней числами, по которой движется ползунок с прорезями, через которые видны числа на линейке. Края ползунка не могут выйти за границы линейки из-за ограничителей на концах линейки. Рядом с прорезями на ползунке нарисованы знаки + и есть текст "max". Нетрудно догадаться, что шифром для сейфа является набор чисел на линейке, видимых через прорези ползунка, сумма которых максимальна. | Для открытия замка сейфа в компьютерной игре из серии "Побег из комнаты" нужно найти шифр. Имеется подсказка – линейка с нанесенными на ней числами, по которой движется ползунок с прорезями, через которые видны числа на линейке. Края ползунка не могут выйти за границы линейки из-за ограничителей на концах линейки. Рядом с прорезями на ползунке нарисованы знаки + и есть текст "max". Нетрудно догадаться, что шифром для сейфа является набор чисел на линейке, видимых через прорези ползунка, сумма которых максимальна. | ||
Строка 25: | Строка 43: | ||
Пояснение к примеру: Числа, которые появляются в прорезях при движении ползунка от самой левой возможной позиции до самой правой: 7+3, 11+5, 4+15, 3+2, 5+1, 15+0. Число 25 не может появиться в прорези ползунка из ограничителей на концах линейки. Максимум суммы чисел в прорезях достигается на числах 4 и 15. | Пояснение к примеру: Числа, которые появляются в прорезях при движении ползунка от самой левой возможной позиции до самой правой: 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| | ||
+ | |||
+ | |||
+ | |||
+ | В примере можно действовать следующим образом: переложить маленький диск с первого стержня на третий, затем средний диск с первого на второй, затем маленький с третьего на второй (поверх среднего), затем большой диск с первого на третий, и, наконец, последним действием пару дисков со второго стержня на третий. Всего необходимо пять действий. | ||
+ |