Задачи на моделирование

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

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

Примечание

Шарик и Матроскин чистят дорогу от снега. Дорога разделена на N участков. Для каждого участка известно, сколько минут нужно на его расчистку. Друзья договорились: Шарик чистит первые несколько участков с начала, а Матроскин — оставшиеся с конца. Нужно разделить работу так, чтобы максимальное время работы (у того, кто работает дольше) было минимальным.

Входные данные: В первой строке число N (2 ≤ N ≤ 10). Во второй строке N положительных целых чисел, не превышающих 1000, — время расчистки каждого участка.

Выходные данные: Минимально возможное значение максимального времени работы.

У учительницы есть X конфет. Она раздаёт их ученикам по очереди, давая каждому по Z конфет. Последний ученик может получить неполную порцию, если конфет останется меньше Z. Учеников в школе достаточно много. Напишите программу, которая выведет, сколько конфет получил каждый ученик.

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

• X — количество конфет - целое число не больше 100

• Z — конфет каждому - целое число не больше 10
  Каждое число в отдельной строке

Выходные данные: номер ученика и количество конфет через пробел (каждая пара на новой строке). 

Студент Павел недавно приобрёл себе подержанный автомобиль и теперь ездит на нём в университет. На его пути в вуз имеется один загруженный перекрёсток, проезд через который регулируется светофором. Сделав ряд поездок, Павел обнаружил интересную закономерность: пока на светофоре горит зелёный свет, через перекрёсток успевает проехать не менее a, но не более b машин. Сверху над перекрёстком установлена уличная видеокамера. Павел может подключиться к ней со своего смартфона и сосчитать количество машин n, которые стоят перед светофором впереди него (свою машину он тоже считает). Назовём тактом светофора включение на нём зелёного сигнала. Напишите программу, определяющую минимальный и максимальный номер такта, на котором Павел проедет перекрёсток.
Формат входных данных
Впервых двух строках входных данных записаны целые числа a и b (1 ≤a ≤ b ≤ 10⁹). В третьей строке записано целое число n (1≤ n ≤ 10⁹).
Формат выходных данных
Выведите два целых числа минимальный и максимальный номер такта светофора, на котором Павел проедет перекрёсток.

Замечание
В примере из условия перед светофором стоят 10 машин. Если через перекрёсток будут проезжать по 5 машин на зелёный свет, то Павел проедет на втором такте. Если же будут проезжать по 3 машины, то он проедет лишь на четвёртом такте.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля, Маша, Саша и Наташа. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила ребятам сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть_2».
Правила игры оказались следующими:

• ·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;
• ·каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, по порядку слева-направо (первый игрок, второй игрок, третий и четвёртый), далее происходит определение победителей:
•     - если карты одной масти, то побеждает тот, у кого картабыла наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
•     - если карты разных мастей, то побеждает тот, у когомасть выше по значению (порядок мастей по возрастанию: червы, бубны, трефы, пики);
•     - если карт высшей масти несколько, то рассматриваетсяопределение наибольшего значения среди этих карт (например, выложили 10 червы, 8 бубны, 7 трефы, 8 трефы, то карты разных мастей, потому выбирается наибольшая масть – в данном случае трефы, таких карт две, среди них самая наибольшая 8 трефы, потому побеждает игрок 4);
• ·победитель забирает четыре карты в свою колоду по порядку,кладя сперва карту первого игрока под низ колоды, затем второго, третьего, четвёртого;
• ·побеждает тот игрок, который заберёт все картыпротивников.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого будут все 52 карты), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока, у второго, третьего, четвёртого.
Входные данные:
на первых 13 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты второго игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты третьего игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты четвёртого игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) минимум у двух игроков останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока, у второго, у третьего, у четвёртого на одной строке через пробел (например, 48 3 1 0).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля и Маша. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила Коле сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть».
Правила игры оказались следующими:
·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;

• каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, далее происходит определение, кто заберёт карты:

               - если карты одной масти, то забирает карты тот, у когокарта была наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта; 
               - если карты разных мастей, то забирает карты тот, у когомасть выше по значению (порядок мастей по возрастанию: пики, червы, бубны, трефы);

• забирающий карты забирает обе карты в свою колоду, кладясперва карту противника под низ колоды, затем свою карту также под низ колоды; 
• побеждает тот игрок, который останется без карт.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого не будет карт), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока и сколько у второго.
Входные данные:
на первых 26 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 26 строках подаются карты второго игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные: 
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) у всех останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока и у второго на одной строке через пробел (например, 50 2).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

В школе №1920 решили провести соревнование по написанию небольших игр среди школьников. Первым критерием данного соревнования было условие того, что в игре нельзя заранее рассчитать результат зная входные данные.
Коля написал игру, в которой задаётся квадратная матрица, состоящая из целых чисел, но не содержащая нулей. Суть игры в том, что в неё играют два участника и каждый может сделать одно из следующих действий:
1.Повернуть матрицу на 90 градусов по часовой стрелке
2.Повернуть матрицу на 90 градусов против часовой стрелке
3.Повернуть матрицу на 45 градусов по часовой стрелке (если есть нули,то они схлопываются (см. пример))
4.Повернуть матрицу на 45 градусов против часовой стрелке (если естьнули, то они схлопываются (см. пример))
У игроков есть ограниченное чётное количество ходов. Каждый из игроков ходит по очереди. Победой в игре считается сумма чисел на ближайшей стороне матрицы, которая находится ближе к игроку. Если матрица в конце повёрнута на 45 градусов, то результатом берётся ближайший угол матрицы к каждому из игроков (одно число в вершине).
Помогите Коле написать алгоритм, который будет по входной матрице и порядку действий ребят определять сколько очков набрал игрок №1 и игрок №2.
Поворот квадратной матрицы на 45 градусов по часовой стрелке будет выглядеть следующим образом.

Формат входных данных
На вход первой строкой подаются число N (1 <= N <= 1000) – размер исходной сгенерированной квадратной матрицы (N – количество строк). Далее на N строках подаются по N целых чисел (кроме нуля).
Далее подаётся число K (2 <= K <= 100, K – чётное)– количество ходов у игроков.
На последующих K-строках вводятся команды, которые выбрали ребята (от 1 до 4), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.

Примечание:

1	2	3
4	5	6
7	8	9

1 команда (повернуть на 90 градусов по часовой стрелке)

7	4	1
8	5	2
9	6	3

2 команда (повернуть на 45 градусов по часовой стрелке)

0	0	7	0	0
0	8	0	4	0
9	0	5	0	1
0	6	0	2	0
0	0	3	0	0

3 команда (повернуть на 90 градусов по часовой стрелке)

0	0	9	0	0
0	6	0	8	0
3	0	5	0	7
0	2	0	4	0
0	0	1	0	0

4 команда (повернуть на 45 градусов против часовой стрелке (нули схлопываются))

9	8	7
6	5	4
3	2	1

Первый игрок находится слева, значит ячейки, которые идут ему в счёт 9 + 6 + 3.
Для второго игрока справа 7 + 4 + 1.
 

Что происходит с программой, когда она запускается на компьютере?

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

Поле в игре <<Речной бой>> представляет собой полоску длины \(n\) клеток и шириной в одну клетку. Где-то на поле расположен корабль из \(k\) клеток (\(k \le n\)). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: <<мимо>>, <<ранен>> или <<убит>>.

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(1 \le n \le 10^9\)).

Вторая строка входных данных содержит целое число \(k\) (\(1 \le k \le n\)).

Формат выходных данных
Выведите одно целое число — количество выстрелов.

Замечание

В первом примере поле состоит из \(n=4\) клеток, корабль имеет длину \(k=2\). Первый выстрел нужно сделать в одну из двух центральных клеток. Если результатом будет <<ранен>>, то вторая клетка корабля находится в одной из двух соседних клеток, и за два выстрела мы гарантированно потопим корабль Если результатом первого выстрела будет <<мимо>>, то корабль занимает две единственные свободные смежные клетки, которые тоже можно подбить двумя выстрелами. Итого нужно 3 выстрела. Двух выстрелов недостаточно, так как всегда есть шанс промахнуться первым выстрелом.

Председатель жюри чемпионата по устному счету Иван Владимирович Треугольников придумал новое задание для участников чемпионата. Исходно на доске выписывается \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\). После этого участник должен выполнять команды двух типов:

1. Стереть \(i\)-е число с доски и записать вместо него число \(x\). То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_1, \ldots, a_{i - 1}, x, a_{i + 1}, \ldots, a_n\).

2. Циклически сдвинуть последовательность чисел на \(k\) вправо. То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n, a_1, a_2, \ldots, a_{n - k}\).

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

Формат входных данных
В первой строке записано целое число \(n\) — количество чисел, изначально записанных на доске (\(2 \leq n \leq 10^5\)).

Во второй строке через пробел записаны \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) — числа, изначально выписанные на доске (\(-10^9 \leq a_i \leq 10^9\)).

В третьей строке записано целое число \(q\) — количество команд, которые необходимо выполнить (\(1 \leq q \leq 10^5\)).

В каждой из следующих \(q\) строк записана очередная команда в следующем формате:

• \(1~i~x\) — это означает, что участник должен заменить \(i\)-е число последовательности на число \(x\) (\(1 \leq i \leq n\); \(-10^9 \leq x \leq 10^9\)).

• \(2~k\) — это означает, что участник должен циклически сдвинуть последовательность чисел на \(k\) вправо (\(1 \leq k < n\)).

Формат выходных данных
В качестве ответа выведите \(q\) строк, в каждой из которых записано одно целое число.

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

Обратите внимание, что ответ может быть достаточно большим и для его хранения потребуется 64-битный тип данных, int64 в паскале, long long в C++, long в Java.

Замечание
Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: \(4,~1,~2,~1,~5,~3\).

После первой команды последовательность циклически сдвигается на \(3\) элемента вправо. Новая последовательность: \(1,~5,~3,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 3 + 4 + 1 + 2 = 16\).

После второй команды необходимо заменить третий элемент последовательности на число \(10\). Новая последовательность: \(1,~5,~10,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 10 + 4 + 1 + 2 = 23\).

После третьей команды заменить четвертый элемент на число \(4\). Так как четвертый элемент уже равен \(4\), последовательность не изменяется. Сумма чисел также равна \(23\).

После четвертой команды последовательность циклически сдвигается на \(1\): \(2,~1,~5,~10,~4,~1\). Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна: \(-10,~1,~5,~10,~4,~1\). Сумма чисел в итоговой последовательности равна \(-10 + 1 + 5 + 10 + 4 + 1 = 11\).

Пандемия охватила все страны мира, и Берляндия не стала исключением. Даже на Всеберляндской олимпиаде по информатике были введены противовирусные меры.

Всего в олимпиаде участвуют \(n\) человек, и, чтобы соблюсти все предписания руководства, жюри олимпиады решило приглашать участников на тур по одному с интервалом \(x\) минут. Таким образом первый участник начнёт тур в момент времени \(0\), второй участник начнёт тур в момент времени \(x\), третий — в момент времени \(2 \cdot x\) и так далее.

Несмотря на разное время начала, длительность тура для каждого участника составляет ровно \(t\) минут. Из-за этого некоторые участники заканчивают писать тур раньше остальных. Когда участник заканчивает писать тур, величина недовольства организацией олимпиады для этого участника равна числу других участников, которые в текущий момент времени еще пишут или только начинают писать тур, но еще не закончили его.

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

Формат входных данных
В первой строке вводится единственное целое число \(n\) (\(1 \le n \le 2 \cdot 10^9\)) — число участников олимпиады.

Во второй строке вводится единственное целое число \(x\) (\(1 \le x \le 2 \cdot 10^9\)) — интервал в минутах между временами начала тура для участников.

В третей строке вводится единственное целое число \(t\) (\(1 \le t \le 2 \cdot 10^9\)) — длительность тура.

Формат выходных данных
В единственной строке выведите одно число — суммарное недовольство всех участников олимпиады.

В первом примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(5\). К этому времени второй и третий участники уже начнут писать тур, поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт писать в момент времени \(2\) и закончит в момент времени \(7\). К этому моменту третий и четвёртый участники уже начнут писать тур, поэтому недовольство второго будет равно \(2\).

Третий участник начнёт писать тур в момент времени \(4\) и закончит в момент времени \(9\). К этому времени четвёртый участник уже начнёт писать тур, поэтому недовольство третьего будет равно \(1\).

Четвёртый участник начнёт писать тур в момент времени \(6\) и закончит в момент времени \(11\). В момент времени \(9\) уже никто не будет писать тур, поэтому недовольство четвёртого будет равно \(0\).

Таким образом, суммарное недовольство всех участников будет равно \(2+2+1+0=5\).

Во втором примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(2\). К этому моменту второй участник уже будет писать тур, а третий участник как раз начнёт в момент времени \(2\). Поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт в момент времени \(1\) и закончит в момент времени \(3\). К этому моменту только третий участник будет всё ещё писать тур.

Таким образом, суммарное недовольство всех участников будет равно \(2+1=3\).

В салоне самолёта в одном ряду находится n кресел. Для удобства прохода и обсуживания пассажиров вдоль салона делается один или два прохода. Например, в салоне самолёта Sukhoi Superjet 100 в ряду 5 кресел и один проход (с одной стороны прохода два кресла, с другой стороны — три), а в самых больших современных самолётах — 10 кресел и два прохода (по три кресла по бокам салона у иллюминаторов и четыре кресла между проходами).


Предположим, что в будущем появятся самолёты большего размера, поэтому количество проходов придётся увеличить. Определите, какое минимальное число проходов должно быть в самолёте, в одном ряду салона которого находится n кресел. По бокам салона (у иллюминаторов) может находиться не более 3 кресел, а между двумя проходами — не более 4 кресел. При этом в салоне должен
быть хотя бы один проход.
Входные данные
Программа получает на вход одно натуральное число n, не превосходящее 2 · 10⁹ , — количество кресел в одном ряду салона.
Выходные данные
Программа должна вывести единственное целое число — минимальное количество проходов, которое должно быть в салоне самолёта с n креслами в одном ряду.

 Примеры

№	Входные данные	Выходные данные
1	10	2

Когда  Громозека держит в руках сразу две печеньки с числами, он сразу пробует преобразовать большее число в меньшее. При преобразовании он использует только две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка. Громозека любит, чтобы преобразование происходило как можно быстрее. Помогите Громозеке составить последовательность команд, при которой из большего числа получится меньшее, причем за наименьшее количество команд.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке). A >= B.

Выходные данные
Выведите последовательность команд преобразования. Каждая команда должна выводиться в отдельной строке. Первая команда обозначается, как -1, вторая команда как :2.
 
 

Примеры

№	Входные данные	Выходные данные
1	21 2	-1 :2 :2 -1 :2

Многие банки при оплате покупок их банковскими картами предлагают систему возврата части потраченных средств, называемую cashback .

Мама Алёны имеет три подобные карты с разными условиями возврата части потраченной суммы. На карту банка RR возвращается 5 рублей из каждых полных 100 рублей стоимости одной покупки. Например, 5 рублей возвращается и за покупку стоимостью 100 рублей, и 199 рублей. Банк BB возвращает 2 рубля с каждых 50 рублей покупки, и за покупку стоимостью 199 рублей он вернет уже 6 рублей. А банк ММ возвращает 3% с полной стоимости любой покупки (заметим, что при цене в целом числе рублей, 3% всегда будут составлять целое число копеек), поэтому за покупку в 199 рублей вернется 5 руб. 97 коп.

Алёна любит ходить вместе с мамой за покупками. Мама предложила Алёне определять, какую покупку какой картой оплачивать, чтобы сумма возврата была максимально возможной. Считайте, что оплата любой покупки возможна любой картой. Если какие-то две или все три карты дают лучшую сумму возврата с точностью до копеек, то Алёна выбирает ту из карт, которая ей больше нравится по оформлению. Больше всего Алёна любит карту банка MM, затем идёт карта банка BB, а меньше всего Алёне нравится карта банка RR.

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

Вводится одно целое число S ( 1 <= S <= 10 000 ) — стоимость покупки в рублях.

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

Выведите название банка RR , BB или MM в зависимости от того, картой какого банка выгоднее оплатить эту покупку. А при равенстве суммы возврата - название банка, определённого в условии задачи.

 

Примечание

В первом примере только банк MM вернёт часть суммы покупки. Второй пример разобран в условии задачи.

 

Примеры

№	Входные данные	Выходные данные
1	10	MM
2	199	BB
3	101	RR

Андрей вот-вот опоздает на школьный этап ВсОШ. К счастью, недавно в его городе появились порталы.
Город, в котором живет Андрей, можно представить в виде прямой. Всего в городе успели построить N порталов. Портал с номером i расположен в точке с координатой x_i . Если в текущий момент времени вы находитесь в одной точке с каким-нибудь порталом, то можете всего за одну секунду телепортироваться в любой другой портал вне зависимости от расстояния между ними. А время, требуемое для преодоления расстояния между точками с координатами p и q без использования порталов равно |p − q| секунд. Андрей является влиятельным гражданином, поэтому он может использовать систему порталов любое количество раз.
Изначально Андрей находится в точке s, а точка проведения олимпиады имеет координату e.
Помогите Андрею понять, как быстро он может попасть на олимпиаду, ведь каждая секунда на счету.

Входные данные
В первой строке входных данных записано одно целое число s — начальное положение Андрея.
Во второй строке записано одно целое число e — место проведения олимпиады. 
В третьей строке записано количество порталов N (2 ≤ N ≤ 2 · 10⁵).
В каждой из N следующих строк записано целое число x_i — координата портала с номером i.
Все числа s, e, x_i по модулю не превосходят 10⁸.

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

№	Входные данные	Выходные данные
1	0 4 3 1 3 5	3

Замечание
Рассмотрим пример из условия. Если бы Андрей не мог пользоваться порталами, он бы смог добраться до точки проведения олимпиады за |0 − 4| = 4 секунды. Однако, можно действовать так:
1. Дойти до портала с номером 1 за |0 − 1| = 1 секунду.
2. Телепортироваться в портал с номером 2 за одну секунду.
3. Дойти от портала с номером 2 до точки проведения олимпиады за |3 − 4| = 1 секунду.
Суммарно получаем 1 + 1 + 1 = 3 секунды.

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

Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").

Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).

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

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

Выходные данные
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

№	Входные данные	Выходные данные
1	1 3 5 7 9 2 4 6 8 0	second 5

Володе очень понравились задачи олимпиады по информатике, поэтому он решил ходить на занятия кружка по программированию. Придя на первое занятие кружка, он узнал, что занятия будут проходить еженедельно в один и тот же день недели. Помогите Володе составить календарь занятий до конца года – определите даты всех занятий, начиная с первого занятия и до конца года.
Программа получает на вход два числа, записанных в разных строках: номер месяца и номер дня месяца, когда проходит первое занятие. Номер месяца может быть одним из четырёх возможных чисел – 9, 10, 11, 12. Номер дня месяца – число от 1 до 30 для сентября и ноября (месяцы с номерами 9 и 11) или от 1 до 31 для октября и декабря (месяцы с номерами
10 и 12). 
Программа должна вывести даты всех занятий кружка до конца года в хронологическом порядке, по одной дате в строке, сначала месяц, затем день месяца, через пробел. Занятия проходят еженедельно, в тот же день недели, что и первое занятие. Формат вывода дат такой же, как в условии. Считайте, что каникулы отсутствуют, а последнее занятие может происходить в любой день декабря, в том числе и 31 числа.
 

Примеры

№	Входные данные	Выходные данные
1	11 20	11 20 11 27 12 4 12 11 12 18 12 25

На столе стоят три вазы с конфетами. В левой вазе лежат A конфет, в средней вазе лежат B конфет, в правой вазе лежат C конфет. Лена съедает одну конфету из левой вазы,
затем – одну конфету из средней вазы, затем из правой, средней, левой, средней, правой, средней и т. д. (слева направо, затем налево, опять направо и т.д.)
Если Лена хочет взять конфету из какой-то вазы, а конфет там нет, она расстраивается и идёт спать. Определите, сколько конфет съест Лена.
Программа получает на вход три целых неотрицательных числа A, B, C – количество конфет в левой, средней, правой вазе. Сумма трёх данных чисел не превосходит 2×10⁹.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 3	7	Лена съест конфеты из левой, средней, правой, средней, левой, средней, правой вазы. После этого она захочет съесть конфету из средней вазы, но в ней уже не осталось конфет.

У Индианы Джонса есть ключ от двери, ведущей к тайным богатствам инков. Ключ имеет форму правильного треугольника, который, в свою очередь, разбит на n² маленьких правильных треугольников, в каждом из которых написана одна десятичная цифра. Пример ключа приведен ниже на рисунке.


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


Поскольку вы не хотите смерти Индианы и хотите получить свою долю сокровищ, вам придется помочь ему!

Входные данные
В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100). В следующих n строках описан сам треугольник. Строка входного файла, имеющая номер i + 1, содержит 2i - 1 цифру — содержание i-й строки ключа-треугольника.

Последняя строка содержит слово counterclockwise, если треугольник необходимо повернуть против часовой стрелки, и clockwise в противном случае.

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 4 5 6 7 8 9 counterclockwise	9  4 8 7  1 3 2 6 5
2	3 1 2 3 4 5 6 7 8 9 clockwise	5  7 6 2  9 8 4 3 1

Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику — все n его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.

Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из n машинок находится на некотором расстоянии от старта — имеет фору x_i метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью v_i метров в секунду. Все машинки движутся в одном направлении — удаляются от старта.

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

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

Входные данные
В первой строке входного файла содержится единственное число n — количество машинок на трассе (2 ≤ n ≤ 100). Каждая из следующих n строк содержит по два целых числа x_i и v_i — расстояние от старта (в метрах) и скорость машинки i (в метрах в секунду) соответственно (1 ≤ x_i, v_i ≤ 1000).

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

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 1 3 4 2	3.00000	На рисунке точкой A обозначено место обгона.
2	2 12 20 2 21	10.00000