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

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


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

Различия

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

Ссылка на это сравнение

подготовка_к_олимпиаде._тур_1 [2013/10/17 21:24]
Пронин Роман
подготовка_к_олимпиаде._тур_1 [2013/10/17 22:09] (текущий)
Пронин Роман
Строка 1: Строка 1:
-**1. Шифр.**+**1. Расстояния в плоском мире.**\\ 
 + 
 +{{ :​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>​|,​ а расстояние между городами,​ у которых 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>​ (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. Новая столешница**\\ 
 + 
 +Владелец трактира "​Залатанный барабан"​ Чарли решил изменить форму столешницы стойки бара с прямоугольной на треугольную,​ чтобы ему не приходилось вставать со стула, когда он собирает кружки,​ оставленные посетителями на углу барной стойки. Но новую столешницу нужно внести в трактир через какое-нибудь окно или дверь. 
 +Напишите программу,​ которая определяет по размерам столешницы и проема в стене, можно ли внести столешницу в трактир через этот проем. Толщину столешницы считать несущественной. Столешницу можно поворачивать при затаскивании любым образом.\\ 
 +//​Формат ввода//​\\ 
 +Первая строка ввода содержит три целых числа 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"​. Нетрудно догадаться,​ что шифром для сейфа является набор чисел на линейке,​ видимых через прорези ползунка,​ сумма которых максимальна.
Строка 13: Строка 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|
 +
 +
 +
 +В примере можно действовать следующим образом:​ переложить маленький диск с первого стержня на третий,​ затем средний диск с первого на второй,​ затем маленький с третьего на второй (поверх среднего),​ затем большой диск с первого на третий,​ и, наконец,​ последним действием пару дисков со второго стержня на третий. Всего необходимо пять действий.
 +
/home/m/mvgoru/wiki.gumnasion.ru/public_html/data/attic/подготовка_к_олимпиаде._тур_1.1382030659.txt.gz · Последние изменения: 2013/10/17 21:24 — Пронин Роман