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

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


подготовка_к_олимпиаде._тур_1

1. Расстояния в плоском мире.

Плоский мир имеет форму диска. Существует только одна дорога, ведущая с севера на юг диска. Эта дорога проходит через центр диска и её называют Осевой. Остальные дороги проложены с запада на восток или с востока на запад от городов Плоского мира до Осевой дороги. Если два города не расположены на одном отрезке дороги, ведущем до Осевой дороги, то, чтобы добраться из одного города в другой, путешественникам нужно сначала дойти до Осевой дороги, затем дойти до дороги, ведущей в нужный город, и затем по ней дойти до города. Установим систему координат следующим образом. Центр диска имеет координаты (0,0). Ось Y совпадает с Осевой дорогой. Пусть один город имеет координаты (X1, Y1), а другой город – координаты (X2, Y2). Тогда расстояние между городами, у которых Y1 ≠ Y2, вычисляется по формуле |X1| + |X2| + |Y1−Y2|, а расстояние между городами, у которых Y1 = Y2, вычисляется по формуле |X1 − X2|, где |a| означает абсолютное значение (модуль) числа a. Напишите программу, определяющую расстояние, которое нужно пройти по дорогам, чтобы попасть из города с координатами (X1, Y1) в город с координатами (X2, Y2).
Формат ввода
Первая строка ввода содержит четыре целых числа X1, Y1, X2, Y2 (0 ≤ X12+Y12 ≤ 108, 0 ≤ X22+Y22 ≤ 108) – координаты двух городов.
Формат вывода
В первой строке вывести одно целое число – расстояние между городами по дорогам.

Пример вводаПример вывода
10 15 -10 -5 40

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». Нетрудно догадаться, что шифром для сейфа является набор чисел на линейке, видимых через прорези ползунка, сумма которых максимальна. Напишите программу, которая определит шифр для открытия сейфа. Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 10) – размеры ползунка. Вторая строка содержит N целых чисел от 0 до 1, разделенных пробелами – описание формы ползунка слева направо. Число 0 означает, что эта часть ползунка не имеет прорезей, а число 1 соответствует части ползунка с прорезью. В описании ползунка есть по крайней мере одно число 1. Третья строка ввода содержит одно целое число M (N < M ≤ 1000) – количество чисел на линейке. Четвертая строка ввода содержит M целых чисел от 0 до 99, разделенных пробелами – числа на линейке, перечисленные в порядке их размещения на линейке. Вывести в первой строке K целых чисел, разделяя их пробелами – шифр для открытия сейфа, где K – количество прорезей на ползунке. Числа вывести в том порядке, в котором они видны в прорезях ползунка. Если существует несколько вариантов с максимальной суммой, то вывести вариант, при котором ползунок расположен левее. Допускается вывод лишних ведущих и завершающих пробелов в строке.

Пример вводаПример вывода
5
1 0 0 1 0
10
7 11 4 3 5 15 2 1 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

В примере можно действовать следующим образом: переложить маленький диск с первого стержня на третий, затем средний диск с первого на второй, затем маленький с третьего на второй (поверх среднего), затем большой диск с первого на третий, и, наконец, последним действием пару дисков со второго стержня на третий. Всего необходимо пять действий.

/home/m/mvgoru/wiki.gumnasion.ru/public_html/data/pages/подготовка_к_олимпиаде._тур_1.txt · Последние изменения: 2013/10/17 22:09 — Пронин Роман