понедельник, 24 октября 2016 г.

Разбор задач 1 личного тура

Разбор задач приводит А.Ю. Кораблев в своем блоге, посвященном программированию sportprog.ru  Перейдите по ссылке.

Отмечу, что в ряде случаев Time limit возникал не из-за неправильного решения. Иногда участники забывали убрать из текста программы задержку, что-нибудь вреде Readln(n)

 Так как тексты задач в разборе не приводятся, помещаю их здесь.

A. Лифты
Лифты – очень сложные устройства. Лифты бывают пассажирские и грузовые, скоростные и не очень, дорогие и подешевле. Разобраться в том, какой лифт перед тобой не всегда просто, но мы постараемся.
Пассажирские лифты предназначены для перевозки людей и небольшого груза. Обычно грузоподъёмность таких лифтов не превосходит 400 килограмм. Грузовые лифты напротив ориентированы на перевозку больших и габаритных предметов, поэтому производители делают их грузоподъёмность больше 400 килограмм.
Скорость обычных, так называемых медленных лифтов меньше 4 м/с, все остальные обычно относят к скоростным. Кстати, в некоторых дубайских небоскрёбах скорости лифтов достигают 18 м/с!
Формат ввода:
В первой строке ввода содержится три целых числа – описание здания: N – количество этажей, H – высота каждого этажа в метрах, M – количество лифтов (числа не превосходят 100).
В последующих M строках содержатся описания лифтов. Каждое описание состоит из двух вещественных чисел: T – время в секундах за которое лифт может доехать от первого этажа до последнего, W – грузоподъёмность лифта в килограммах.
Формат вывода:
В M строках выведите описание каждого лифта, состоящее из двух слов по критериям грузоподъёмности и скорости. Пассажирские лифты обозначаются словом PASS, грузовые – CARGO, скоростные – FAST, медленные – SLOW.
Input
Output
10 3 2
50.2 345
3.4 1064.4
PASS SLOW
CARGO FAST


B. Нужный этаж

В очень больших зданиях обычно есть очень много лифтов. Системы управления лифтами настраивают профессионалы с учётом потребностей посетителя каждого конкретного здания. Например, скоростные лифты могут не останавливаться на некоторых этажах, чтобы сэкономить время, а медленные лифты часто не ездят выше определённого количества этажей.
Одному сотруднику одного очень большого офисного здания очень везло. Он всегда перемещался по этажам здания максимально быстро. Так уж получалось, что когда сотрудник приезжал на этаж, другие лифты, которые останавливались на этом этаже уже ждали его, поэтому ему удавалось мгновенно пересаживаться с одного лифта на другой. Так могло происходить многократно и, надо сказать, противоречило законам физики!
Формат ввода:
В первой строке ввода содержится три целых числа – описание здания: N – количество этажей, M – количество лифтов (числа не превосходят 100).
В последующих M строках содержатся описания лифтов. Каждое описание состоит из целых чисел. Первое число – время в секундах, за которое лифт проезжает один этаж. Второе число – количество этажей на которых останавливается лифт. Остальные числа – номера этажей, на которых останавливается конкретный лифт.
В последней строке ввода содержится два целых числа. Первое – номер этажа с которого сотрудник намеревается уехать. Второе – номер этажа, на который хочет попасть сотрудник.
Формат вывода:
В единственной строке выведите время в секундах, которое понадобится сотруднику, чтобы преодолеть на лифтах путь от одного этажа до другого. Если сотрудник никогда не доберётся до нужного этажа, выведите -1.
Input
Output
4 3
15 4 1 2 3 4
3 3 1 3 4
4 3 2 3 4
1 2
10

C. Дорога к начальнику


Одного офисного сотрудника одного большого офисного здания вызвал начальник. Между этажом, на котором находится сотрудник и этажом, где его ждёт начальник ходит лифт. Между этажами начальника и подчинённого находится L этажей. Лифт может ехать только так, чтобы любой отрезок пути длиной K этажей проезжать ровно за H секунд. Через какое минимальное и максимальное время сотрудник сможет доехать на лифте до начальника.
Формат ввода:
В единственной строке через пробел записаны целые числа L, K и H (1<=K<=L<=1000, 1<=H<=1000).
Формат вывода:
Выведите через пробел минимальное и максимальное время за которое подчинённый сможет доехать на лифте до начальника с точностью не менее 10^-5.
Input
Output
30 10 1
3.00000000 3.00000000

D. Быстрый спуск


Один сотрудник оказался на верхнем (n-м) этаже небоскрёба и хочет спуститься на первый. На табло он видит, что лифт в данный момент едет вниз до первого этажа и находится точно на кровне k-го этажа. Сотрудник смекнул, что, возможно, будет быстрее спуститься на несколько этажей вниз и вызвать лифт оттуда. Помогите сотруднику определить до какого этажа ему надо спуститься пешком, чтобы как можно быстрее оказаться на первом этаже.
Лифт проезжает этаж за v секунд, а сотрудник пробегает его за u секунд. Когда лифт спустится на первый этаж, он должен будет простоять там 15 секунд, после чего сможет ехать вверх. Если сотрудник вызовет лифт не сразу, то можно считать, что его никто не «угонит». На посадку в лифт сотрудник потратит 5 секунд. Всеми остальными временными задержками можно пренебречь.
Формат ввода:
В единственной строке задано 4 число – n, k, u и v (1
Формат вывода:
Выведите единственное число – этаж, до которого нужно спуститься сотруднику. Если есть несколько равноценных вариантов, то выведите такой, при котором сотрудник меньше пройдёт пешком.
Input
Output
50 49 4.8 0.2
45

E. Половина лифтов


Помните старые лифты, в которых нужно было договариваться на какой этаж лифт поедет сначала, а на какой потом? В одном небоскрёбе были как раз такие – лифты ехали сначала на тот этаж, который нажимали первым.
Однажды в этом здании проходила большая и представительная конференция. Организаторы подготовились на славу. Они решили выделить людей, которые должны были встречать лифты с участниками. Чтобы оптимизировать расходы на персонал организаторы решили, что будет достаточно, если количество встречающих будет рассчитано таким образом, что их количество не будет больше, чем половина лифтов, которые находятся в здании.
С утра к зданию начали подъезжать автобусы с участниками конференции. Они стали заходить в лифты… Также в лифтах оказались люди, которые ехали по другим этажам. Как же решить, на какой этаж лифт поедет сначала, а на какой потом? Решение простое – нужно проголосовать и большинством голосов решить.
Формат ввода:
В первой строке записано нечётное число K – количество лифтов в здании (0
Формат вывода:
Выведите минимальное количество участников конференции, которое должно находится во всех лифтах, чтобы организаторам не хватило встречающих.
Input
Output
3
5 7 5
6

F. Задачка для лифтёров


На секунду представим, что нам нужно построить лифт на Луне. Чтобы посетителям лифта было комфортно, в шахту лифта нужно закачать воздух. Возникает вопрос – сколько воздуха нужно, чтобы заполнить шахту лифта целиком.
Один космический лифтёр придумал интересный способ. Он залезал в шахту лифта и измерял в метрах любое из наибольших расстояний между стенками шахты в любом горизонтальном сечении шахты. Для простоты обозначим это расстояние за А. Потом лифтёр мерял высоту шахты лифта, обозначим её за B.
После этого он считал загадочное число лифтёра путём перемножения числа А на самого себя и на высоту шахты лифта.
Но самая настоящая магия происходила потом! Он умножал загадочное число лифтёра на ещё более загадочное число инопланетного происхождения равное
Так он и получал объём воздуха в кубометрах, который нужно было закачать в шахту.
Формат ввода:
В первой строке ввода содержится два вещественных числа. Первое – число А, второе – объём воздуха в литрах, который закачивали в шахту.
Формат вывода:
Выведите число В – высоту шахты лифта.
Input
Output
2 100000
31.830988618379067













Комментариев нет:

Отправить комментарий