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

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


подготовка_к_олимпиаде._тур_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.

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