Задачи второго тура

На sportprog.ru выложен разбор задач второго тура. Но нет самих задач. Вот они.

A. Скоро лето

Пока весна борется с зимой за право быть хозяйкой мартовской погоды в нашем крае, помечтаем о лете, о походах в лес за грибами и ягодами.

Один математик очень любит ходить в лес. Он живёт в таком районе города, где улицы образуют правильную сетку кварталов; все кварталы являются квадратами с длиной стороны, равной 100 метрам.

Вход в лес расположен на одном из перекрёстков; математик начинает свой путь с другого перекрёстка, который расположен южнее и западнее входа в лес. Естественно, что, выйдя из дома, математик всегда идет по улицам, ведущим либо на север, либо на восток. Некоторые кварталы, которые встречаются ему на пути, он может также пересечь по диагонали, ведущей из юго-западного угла квартала в северо-восточный. Таким образом, некоторые из маршрутов (ведущих всегда на север, восток или северо-восток), оказываются короче других. Математика интересует, сколько времени понадобится ему на преодоление кратчайшего маршрута; для этого ему нужно знать его длину.

Вы должны написать программу, которая по имеющейся информации о виде сетки кварталов рассчитывает длину кратчайшего маршрута из юго-западного угла в северо-восточный.

Формат ввода:

В первой строке находятся два целых числа N и M (0 < N, M ≤ 1000) — размер сетки кварталов с запада на восток и с юга на север соответственно. Математик начинает путь с перекрёстка, который находится к юго-западу от квартала с координатами (1, 1); вход в лес находится к северо-востоку от квартала с координатами (N, M). Во второй строке находится целое число K (0 ≤ K ≤ 100) — количество кварталов, через которые можно пройти наискось. Далее следуют K строк с парами целых положительных чисел, разделённых пробелами — координатами таких кварталов.

Формат вывода:

Требуется вывести длину кратчайшего пути от дома математика до леса в метрах, округлённую до целых метров.

Input	Output
3 2 3 1 1 3 2 1 2	383

B. Ягодники

Шли как-то два математика по лесу и собирали ягоды. Час шли, два шли, а потом вдруг остановились и решили ягодами помериться. Достали они весы (какой же математик пойдет в лес без весов?) и взвесили свои корзины с собранным урожаем, а потом записали полученные числа a₁ и b₁ на листочек. После этого второй математик пересыпал все ягоды в корзину к первому (полностью опустошив свою корзину), и они снова взвесили свои корзины, получив числа a₂ и b₂ соответственно. Наконец, первый математик пересыпал все ягоды в корзину ко второму (полностью опустошив свою корзину); после взвешивания они получили числа a₃ и b₃ соответственно. Этих данных оказалось достаточно для определения победителя, и довольные математики пошли дальше. Вам же предстоит вычислить массу ягод в корзине каждого из математиков до совершения всех пересыпаний.

Формат ввода:

Входные данные состоят из трёх строк. В i-й строке (1 ≤ i ≤ 3) записаны целые числа a_i и b_i (0 ≤ a_i, b_i ≤ 10 000).

Формат вывода:

В единственной строке выведите пару целых чисел через пробел — сколько ягод собрали, соответственно, первый и второй математик.

Input	Output
1 2 2 1 0 3	1 1

C. Перекличка

В лесу очень легко потеряться, поэтому нужно регулярно делать перекличку. Два математика для этой цели используют громкоговорители, они усиливают звук и не дают ему распространяться в стороны.

В ягодно-грибной сезон по лесам гуляет много разных людей. Поэтому, когда один математик зовёт другого, в зону действия громкоговорителя попадают другие ягодники и грибники. Сколько таких людей услышит зов математика.

Формат ввода:

В первой строке содержатся координаты зовущего математика, а также угол, на который

громкоговоритель распространяет свой звук. Во второй строке содержатся координаты второго математика. В третьей строке – целое число, количество посторонних грибников и ягодников, гуляющий по лесу. В последующих строках ввода содержатся координаты гуляющих грибников и ягодников. Все координаты – вещественные числа по модулю не превосходящие 1000. Угол действия громкоговорителя указан в градусах и не превосходит 180. Количество грибников и ягодников не превосходит 500.

Формат вывода:

Выведите количество грибников и ягодников, которые услышат зов математика.

Input	Output
0.0 0.0 45.0 2.0 2.0 3 3.0 4.0 3.2 4.1 1.2 5.1	2

D. Команда

Если собирать грибы и ягоды большой командой, на этом можно неплохо заработать. Математики считают также. Помогите математикам собрать самую лучшую команду сборщиков грибов и ягод!

Формат ввода:

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

Формат вывода:

Вывести суммарный вес грибов и ягод, которое может собрать самая лучшая команда сборщиков.

Input	Output
3 Ivanov 270 12 Petrov 950 14 Sidorov 130 11 1000	23

E. Дальняя дорога

Нам повезло, ведь наш город достаточно маленький, поэтому до леса рукой подать. Жителям крупных городов повезло гораздо меньше, ведь им частенько приходится отправляться за грибами аж в другой город. Один математик отправился за грибами на автобусе…

Для сокращения времени движения, маршрут автобуса прокладывается по городам так, чтобы меньше времени терять на светофорах. Чтобы проехать город насквозь, водитель должен выбрать всего один из всех светофоров, тот, на котором уже горит или раньше всего загорится зелёный свет. Есть и испорченные светофоры – те, у которых время горения каждого сигнала равно 0. Некоторым автобусам из-за таких поломок вообще не удавалось доехать до конечного пункта, ведь если все светофоры города сломаны, то на них горит красный свет – ехать нельзя.

Светофоры работают так, что временем горения жёлтого сигнала можно пренебречь. Также считается, что в начале пути автобус находится в первом городе, но для выезда из него требуется проехать через один из светофоров этого города. Подразумевается, что проезд города осуществляется мгновенно.

Формат ввода:

В первой строке N – число городов (0

Формат вывода:

Выведите «From », название первого города, « to », затем название последнего города. В следующей строке: «Time: » затем время, в течение которого автобус доберётся из первого города в последний. Считается, что автобус проезжает все города последовательно, начиная с первого и заканчивая последним. В момент начала движения автобуса из первого города на всех светофорах во всех городах загорелся красный свет. Если автобус не доехал до конечного пункта, выведите «NEVER» (без кавычек).

Input	Output
3 Moscow 3 10 15 35 111 Alexandrov 2 20 50 50 Tver	From Moscow to Tver Time: 190

F. Блинчики

После прогулки в лес очень хочется подкрепиться. Поэтому математики, собрав полные корзины ягод и грибов, решили посетить ресторан и заказать себе n блинчиков. Для того, чтобы приготовить блинчик, повар должен обжарить каждую из сторон блинчика на сковороде в течение одной минуты. К сожалению, у повара имеется только одна сковорода, и на ней можно одновременно жарить не более k блинчиков. Определите, сколько минут понадобится повару, чтобы выполнить заказ математиков.

Формат ввода:

В единственной строке через пробел записаны целые числа n и k (1 ≤ n, k ≤ 1000).

Формат вывода:

Выведите минимальное количество минут, за которое повар сможет приготовить n бифштексов.

Input	Output
3 2	3