#113689

Гонки

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача F ]

Недавно руководством одной известной автомобильной телепередачи «Верхняя шестерня» было решено провести обзор автомобилей на солнечных батареях. Для этого были выбраны две модели.

К сожалению, современные технологии еще далеки от совершенства, поэтому автомобили не могут ехать непрерывно. Руководство по эксплуатации первого автомобиля гласит, что при передвижении на большие дистанции нужно действовать следующим образом: в течение \(t_1\) часов ехать со скоростью \(v_1\) километров в час, после чего такое же время заряжать батареи. Стратегия по оптимальному использованию второго автомобиля аналогична, но числа \(t_2\) и \(v_2\) для него могут отличаться.

Для демонстрации работы автомобилей было решено устроить соревнование — заезд по прямой трассе длиной \(X\) километров, придерживаясь стратегии из руководства.

Вам поручено предсказать результат этого заезда.

Входные данные

Первая строка входного файла содержит целые числа \(t_1, \ v_1, \ t_2\) и \(v_2\), разделенные пробелами \((1 \le t_i \ , v_i \le 1000\)). Вторая строка содержит одно целое число \(x\) — длину трассы (\(1 \le x \le 1000 000\)).

Выходные данные

Если первый автомобиль финиширует первым, выведите «First». Если второй автомобиль окажется на финише раньше, выведите «Second». Если же обе машины преодолеют трассу за одинаковое время, выведите «Draw».

Примеры

Входные данные

1 1 2 1
4

Выходные данные

Second

#113690

Робот

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача G ]

Робот-марсоход «ТцТцПетя» двигается по поверхности Марса как ему вздумается, отправляя на Землю информацию о своих передвижениях.

«ТцТцПетя» пользуется следующей системой координат: начало координат совпадает с его начальным положением, ось \(OY\) направлена в сторону, в которую он направлен в начальный момент времени (при высадке на Марс).

Передвигается «ТцТцПетя» следующим образом: после высадки на Марс он проезжает вперед какое-то целое число сантиметров, от \(1\) до \(10^6;\) затем поворачивает на \(90\) градусов либо налево, либо направо; после чего снова проезжает вперед от \(1 \ до \ 10^6\) сантиметров; и снова поворачивает на \(90\) градусов либо налево, либо направо; и так далее. Наконец, проехав последний отрезок (также длиной от \(1\) до \(10^6\) сантиметров), он останавливается и начинает передавать на Землю описание своего маршрута.

В итоге Центр Управления получил от «ТцТцПети» следующее сообщение: «Я сделал n передвижений. Сообщаю \(n \ − \ 1\) поворот, который я совершил: последовательность поворотов. В итоге я оказался в точке с координатами \((x, \ y).\) Мне тут нравится. Конец связи.»

И тут-то создатели «ТцТцПети» поняли, что забыли запрограммировать его, чтобы он сообщал длины своих передвижений!

Теперь их интересует хоть какой-нибудь вариант пути «ТцТцПети», который удовлетворяет полученным от него данным. Помогите им.

Входные данные

В первой строке входного файла содержатся три целых числа \(x, \ y, \ n \ (−100 000 \le x, \ y \le 100 000; 1 \le n \le 100 000\)) — конечные координаты «ТцТцПети» и количество передвижений, которые он совершил.

Вторая строка имеет длину \(n \ − \ 1\) и состоит из символов «L» и «R» — это последовательность поворотов, которые совершил «ТцТцПетя». Символ «L» обозначает поворот налево на \(90\) градусов, символ «R» — направо на \(90\) градусов.

Выходные данные

Если информация противоречива и двигаться подобным образом робот не мог, выведите в выходной файл слово «Impossible».

В противном случае выведите n целых чисел от \(1\) до \(10^6\) — длины передвижений «ТцТцПети» в сантиметрах, такие что с учетом указанных им поворотов, «ТцТцПетя» заканчивает движение в точке \((x, \ y).\) Числа должны быть разделены пробелами и/или переводами строк.

Примечание

Поверхность Марса в рамках данной задачи считается плоской.

Примеры

Входные данные

-2 -1 4
RRR

Выходные данные

1 1 2 3

Входные данные

4 1 5
LRRL

Выходные данные

Impossible

Входные данные

0 10 1

Выходные данные

#113691

Санта Клаус

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача H ]

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

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

Входные данные

Первая строка входного файла содержит три целых числа: \(n\) — число детей, \(m\) и \(k\) — \(число\) подарков в первом и втором мешке соответственно (\(1 \le n, \ m, \ k \le 100; m + k \le n)\). Вторая строка входного файла содержит \(m\) целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит \(k\) целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими \(n\). Все дети должны получить подарок на Рождество, иначе Санта расстроится.

Выходные данные

В первой строке выведите одно число \(a\) — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке \(a\) чисел — номера детей, которым эти подарки должны быть доставлены.

Примеры

Входные данные

7 2 1
7 3
1

Выходные данные

4
2 4 5 6

#113692

Подстрока

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача I ]

Недавно разведка перехватила зашифрованное сообщение — строку \(s\). Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование.

Ваш отдел занимается шифрами нового поколения. На данный момент известно всего \(n\) таких шифров. Для каждого из них есть три характерных параметра — целые числа \(l\), \(r\) и строка \(t\). Пусть строка \(g\) была получена в результате применения этого метода. Тогда строка \(g_lg_{l+1} \dots g_{r−1}g_{r}\) (здесь \(g_i\) — это \(i\)-й символ строки \(g\)) содержит \(t\) как подстроку.

Вам поручено определить для каждого типа шифрования, могло ли сообщение \(s\) быть получено в результате его применения.

Входные данные

Первая строка входного файла содержит строку \(s\) (\(1 \le |s| \le 100 000\), где \(|s|\) — длина строки \(s\)).

Вторая строка входного файла содержит целое число \(n\) — количество типов шифрования \((1 \le n \le 100 000\)). Последующие \(n\) строк содержат по два целых числа \(l_i\), \(r_i\) и строку \(t_i\), разделенные пробелами — характерные параметры \(i\)-го метода шифрования (\(1 \le l_i \le r_i \le |s|\)).

Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех \(t_i\) не превосходит \(100 000\).

Выходные данные

Выведите одну строку — для каждого типа шифрования «+», если сообщение \(s\) могло быть получено в результате его применения, или «-» в противном случае.

Примеры

Входные данные

frommarsiam
3
6 10 i
2 11 am
1 9 human

Выходные данные

++-

#113693

Вода

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача J ]

Кто возьмет билетов пачку,
Тот получит водокачку!

из к/ф «Бриллиантовая рука»

Виталий является директором небольшой водопроводной компании. Он работает на водокачке. Водокачка представляет собой цилиндр высотой \(H\) метров, изначально целиком заполненный водой.

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

Напишите программу, которая могла бы обрабатывать следующие запросы:

В момент времени \(t\) появилась течь на высоте \(h\) со скоростью вытекания воды \(v\).
В момент времени \(t\) Виталий устранил все течи на высоте \(h\).
В момент времени \(t\) Виталий хотел бы узнать уровень воды.

Вода вытекает из отверстия, только если уровень воды выше высоты отверстия. Изначально водокачка полна. Скорость вытекания воды \(v\) означает, что за единицу времени через отверстие вытекает объем воды, соответствующий v метрам воды в водокачке.

Входные данные

В первой строке входного содержится два целых числа \(n\) и \(H\) (\(1 \le n \le 10^5 ; \ 1 \le H \le 10^9 )\) — количество запросов и высота водонапорной башни. Далее следуют n строк описывающих запросы. В каждой строке первое число \(k \ (1 \le k \le 3)\) — номер типа запроса. Далее в строке в зависимости от запроса идут от одного до трех целых чисел из \(t, \ h \ и \ v \ (0 \le t \le 10^9 ; \ 0 \le h \le H; \ 1 \le v \le 10^9\)). Запросы перечислены в порядке увеличения времени и никакие два запроса не имеют одинаковое время.

Выходные данные

На каждый запрос третьего типа выведите одно число — уровень воды в водонапорной башне в соответствующий момент времени.

Ответ должен иметь относительную или абсолютную точность \(10^{−9}\). Это означает, что если правильный ответ равен \(a\), а выведено \(p\), то значение будет признано правильным, если \(\frac{|a \ − \ p|}{max(a, \ 1)} \le 10^{−9}\).

Примеры

Входные данные

Выходные данные

8.0
6.0
4.0
4.0