Задача A. Стритрейсинг ≡

Условие

Ты стоишь на светофоре на своей машине, а рядом с тобой или через машину стоит такой же, как ты. Ты с ним не знаком, ты даже понятия не имеешь, кто он такой, но ты знаешь: сейчас начнется оно... Вы не сигналите друг другу, не газуете, но оба понимаете: да, сейчас будет оно, то самое. И по сигналу светофора с визгом резины и ревом выхлопной системы вы срываетесь вперед, пытаясь выяснить, чья машина быстрее. Из всех машин, стоящих на светофоре, только вы вдвоем сорвались. Если одним из них был ты, то ты настоящий стритрейсер.

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

Однажды ночью сотрудники ГИБДД расставили вдоль трассы знаки ограничения скорости и уселись в засаде с радаром. Очередные соревнования пришлось проводить, соблюдая скоростной режим. Напоминаем, что знак ограничения скорости предписывает двигаться со скоростью, не превышающей указанную на нем. Действие знака начинается в месте установки и прерывается следующим знаком. С начала трассы до первого знака действует обычное ограничение 90 км/час.

За какое минимально возможное время проедет трассу ваша машина, если максимальное ускорение, развиваемое двигателем a₁ м/сек², а максимальное замедление торможения a₂ м/сек²? В начале трассы ваш автомобиль неподвижен.

Формат входного файла

В первой строке файла записано вещественное число S - длина трассы.

Вторая строке входного файла содержит два вещественных числа a₁ и a₂. В третьей строке находится целое число N - количество установленных знаков. В последующих N строках файла даны через пробел пары вещественных чисел S_i, V_i - расстояние от начала трассы, на котором установлен i-ый знак и ограничение скорости в км/час, указанное на нём, соответственно. Знаки записаны по порядку, по мере удаления от старта.

Формат выходного файла

Ограничения

Примеры тестов

1000
5 10
0

42.50

1000
5 10
1
100 45
0

78.81

Задача B. Прогрессии ≡

Условие

Жители страны Прогрессляндии слишком буквально поняли лозунг своего великого правителя "Больше прогрессий - хороших и разных" и решили сосчитать, сколько всего прогрессий они могут придумать. К нашему великому счастью, они знают только целочисленные строго возрастающие арифметические прогрессии в диапазоне от 0 до N, причем прогрессия обязательно должна начинаться со священного числа 0 и иметь хотя бы два элемента.

К сожалению, они недостаточно прогрессивны, чтобы решить эту проблему. Помогите им.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3

5

Задача D. Памятник ≡

Условие

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

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

Главная площадь города имеет форму прямоугольника со сторонами N и M. С одним из углов площади совмещено начало координат. Ось OX проходит по большей стороне, а OY - по меньшей. Площадка, на которую нужно поставить памятник, точно совпадает по размерам с основанием памятника. Это прямоугольник со сторонами A и B, которые параллельны сторонам площади (большая сторона площадки параллельна большей стороне площади). Расположение площадки задается координатами ее угла, ближайшего к началу координат.

Определим длину элементарного переворота памятника как длину ребра, перпендикулярного ребрам основания, на котором памятник находился до этого переворота. Длина траектории перемещения памятника определяется как сумма длин элементарных переворотов. Требуется найти наименьшую длину траектории, по которой можно переместить памятник и поставить правильно.

Формат входного файла

В первой строке входного файла записаны два числа N и M - размеры площади.

В следующей строке заданы размеры памятника и координаты площадки. Это пять чисел A, B, C, X, Y, где. А и B - длины ребер основания памятника, C - его высота, X и Y - координаты. Все числа целые и записаны через пробел.

Формат выходного файла

Ограничения

Примеры тестов

10 10
1 1 1 2 2

6

Задача F. Молекулы ≡

Условие

Органические вещества отличаются потрясающим разнообразием. Они различаются по химическому составу (по пропорциям составляющих вещество элементов), по химической формуле молекул (по порядку расположения и химическим связям атомов) и по пространственной форме молекул. Проблема восстановления по химическому составу органического вещества его химической формулы и проблема пространственного конфигурирования молекул по их химическим формулам - чрезвычайно актуальные задачи биоинформатики. К сожалению, они отличаются высокой вычислительной сложностью.

Рассмотрим проблему химической формулы и пространственной конфигурации органических молекул при следующих упрощающих предположениях:

1. вещество состоит только из атомов водорода H (валентность 1), кислорода O (валентность 2), азота N (валентность 3) и углерода C (валентность 4);
2. молекула или группа молекул вещества представляет собой плоскую прямоугольную решётку из m строк и n столбцов, в узлах которой могут находиться или атомы перечисленных элементов, или "дырки" - пустоты, не занятые никаким атомом;
3. каждый атом в решётке может быть связан с атомами, своими соседями по решётке, но с каждым соседом он связан не более чем одной связью, а общее число его связей совпадает с его валентностью.

Формат входного файла

Входной файл для программы описывает одну решетку. В его первую строку записаны через пробел два целых чисел M и N, задающих число строк и число столбцов этой решётки. Следующие M строк содержат ровно по N символов `H`, `O`, `N`, `C`, `.`, представляющих элементы или "дырки" в порядке слева направо в соответствующей строке решётки.

Формат выходного файла

Ограничения

Примеры тестов

3 4
HOH.
NCOH
OO..

Valid

Задача G. Перекачка данных ≡

Условие

Имеется два компьютера, с одного из которых нужно передать информацию размером V мегабайт на другой. В качестве носителя информации имеется два USB-диска с размерами V1 и V2 мегабайт, скоростями чтения R1 и R2 и записи W1, W2 мегабайт в секунду, соответственно.

Конструктивные особенности дисков таковы, что чтение или запись происходят целое число секунд, в том числе, если на источнике информации или на приемнике места меньше, чем может быть записано за секунду, копирование будет все равно занимать секунду. На каждом из компьютеров имеется только один USB-разъем. Поэтому в один и тот же момент времени можно либо переписывать информацию с компьютера на один носитель, либо читать данные с диска и переписывать их на компьютер. Требуется определить, за какое минимальное время можно перенести данные с одного компьютера на другой, если переключение дисков происходит за нулевое время.

Формат входного файла

В первой строке входного файла записано одно целое число V - объем информации, который нужно перекачать.

В следующих двух строках записано по три числа - параметры каждого из дисков. Сначала V1, R1, W1, а затем, соответственно, V2, R2 и W2.

Формат выходного файла

Ограничения

Примеры тестов

80
10 10 10
20 20 20

6

Задача J. Светофоры ≡

Условие

Все знают, что на ночных улицах опасно. Но в данном случае речь идет не о преступниках и маньяках. Когда наступает ночь, и силы зла властвуют безраздельно, там действуют те, с кем не встретишься днем - темные маги, вампиры и прочая нечисть. Их сила велика, и с ними нельзя справиться обычным оружием. Но по следу "ночных охотников" идут те, кто веками сражается с порождениями сумрака и побеждает их, неукоснительно соблюдая при этом Договор, заключенный тысячелетия тому назад между Светлыми и Темными: Имя им - Ночной Дозор. Их предназначение - сохранение равновесия между Добром и Злом, нарушение которого вызывает разрушения, войны, революции, вселенские катастрофы. Каждый плохой человеческий поступок - измена, предательство, убийство, равно, как и хороший, ложится на чашу весов, перевешивая их то в одну, то в другую сторону. Именно поэтому и силы Света, и силы Тьмы вынуждены существовать в двух мирах: реальном и потустороннем, пытаясь либо подтолкнуть человека к греху, либо отвратить от него:

В городе Н-ске, на одном из перекрестков силы Зла нарушили вековой договор. С другого перекрестка машина "Горсвет" направляется к злополучному месту. За какое время доедут силы Света, если у них есть карта города со схемой работы светофоров, и они поедут по оптимальному маршруту с максимально разрешенной скоростью 60 км/час?

Карта города представляет собой прямоугольник размером N x M км. Движение в Н-ске организовано по M+1 улицам, идущим параллельно с севера на юг, и N+1 авеню, идущим параллельно с запада на восток. Расстояние между двумя соседними улицами (авеню) составляет 250 метров.

По традиции, улицы нумеруются (с запада на восток) подряд идущими натуральными числами, начиная c единицы. Авеню обозначаются (с севера на юг) подряд идущими буквами латинского алфавита, начиная с A. Таким образом, каждый перекресток города можно однозначно обозначить парой из буквы и числа, например C17.

На каждом перекрестке может находиться светофор. Для i-го светофора известно целое число K_i, определяющее интервалы цикла смены его состояний: для потоков, едущих с запада и с востока, сначала (K_i - 1) секунд горит зеленый свет, затем 1 секунду горит желтый, затем Ki секунд горит красный; а для потоков, едущих с севера и с юга, сначала K_i секунд горит красный, затем (K_i - 1) секунд - зеленый, затем 1 секунду - желтый. Через перекресток разрешается проезжать напрямую или поворачивать на зеленый и желтый свет. В момент поступления сигнала о нарушении договора, каждый светофор находился в D_i секундах от начала цикла.

Формат входного файла

В первой строке входного файла через пробел записаны числа N и M. Во второй строке через пробел записаны обозначения начального и конечного перекрестка. В третьей строке записано количество светофоров K. В последующих K строках через пробел записаны обозначение перекрестка и числа K_i и D_i.

Формат выходного файла

Ограничения

Примеры тестов

5 1
F2 A2
3
A2 60 0
C1 100 10
C2 180 180

75

5 5
A1 F6
7
A3 120 0
B3 180 0
C3 180 60
D3 100 60
E3 100 0
F1 5 0
F2 3 0

150