Год Коровы

Известно, что в Китайском календаре года следуют 12-летнему циклу: Ox(Бык), Tiger(Тигр), Rabbit(Кролик), Dragon(Дракон), Snake(Змея), Horse(Лошадь), Goat(Коза), Monkey(Обезьяна), Rooster(Петух), Dog(Собака), Pig(Свинья), Rat(Крыса), и затем Ox опять. 
Уже много лет корова Беси гордится, что она родилась в год Быка. Её подружка Эльза хочет узнать сколько лет отделяет её рождение от рождения Беси и надеется, что вы поможете ей узнать это, основываясь на отношениях между датами рождения некоторых коров на ферме.

"Mildred born in previous Dragon year from Bessie",

или

"Mildred born in next Dragon year from Bessie" (previous - предыдуший, next-следующий).

Последнее слово - имя коровы, которое или Bessie или корова ранее упомянутая в предыдущей строке ввода.
Первое слово - имя коровы, которая не Bessie и ещё не упоминалась на вводе. Все имена коров имеют не более 10 символов a..z или A..Z.

5-ое слово - один из знаков зодиака, указаных ранее.

4-ое слово либо "previous" либо "next". Например, фраза "Mildred born in previous Dragon year from Bessie", означает, что год рождения Mildred был год Дракона(Dragon), ближайший и строго раньше (не равен) года рождения Беси.

Примеры

Конец K-ого урока

В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается K-ый урок?»

Формат входных данных
Вводится одно натуральное число K, не превышающее 15.

Формат выходных данных
Выведите время окончания K-ого урока: сначала часы, потом минуты, разделяя их пробелом.

Карточки

Вася изготовил карточки, написав на них N первых заглавных букв латинского алфавита. Карточки Вася положил в стопку.

Дальше он берет первую сверху карточку и кладет ее в новую стопку. Далее вторую карточку он кладет вниз этой новой стопки, третью — наверх новой стопки, потом четвертую — опять вниз, следующую — наверх и т.д.

После этого оказалось, что карточки лежат строго по алфавиту, если просматривать их сверху вниз.

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

Входные данные
Вводится натуральное число N (N не превышает 26).

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

Примеры

Рассадка участников

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

Входные данные
Программа получает на вход целое положительное число участников олимпиады N1000. Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.

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

Если задача не имеет решения, необходимо вывести одно число 0.

Числа можно выводить как в отдельных строках, так и в одной строке через пробел. Если есть несколько вариантов рассадки, то необходимо вывести любой из них (но только один).

Примеры

Черно-белые палиндромы

Дана полоса клетчатой бумаги длиной N клеток и шириной 1 клетка, в которой некоторые клетки покрашены в черный цвет, а остальные — в белый. Такая полоса называется палиндромом, если последовательность черных и белых клеток при просмотре этой полосы слева направо оказывается такой же, как при просмотре справа налево.

Вам дана полоса длины N. Требуется разрезать ее на полоски, являющиеся палиндромами, так, чтобы количество получившихся полосок было строго меньше величины (2/5)N + 3.

Входные данные
Первая строка входного файла содержит число N — длину исходной полосы (N — натуральное число, не превышающее 100000). Далее идет N чисел, описывающих раскраску полосы: 0 означает черную клетку, а 1 — белую.

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

Примеры

Коллайдер

Физики проводят эксперимент для исследования частиц трёх типов: x, y и z. Они запускают в коллайдер пронумерованный ряд из n частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с i-ого места ряда и моментально появляется на месте j. После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте k. Напишите программу, которая поможет физикам.

Входные данные
В первой строке файла два целых числа: n – количество частиц и m — общее количество воздействий и вопросов (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). Во второй строке — последовательность из символов x, y и z длиной n. На каждой из следующих m строк (1 ≤ m ≤ 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом a и после пробела дается два целых числа из интервала [1; n]. Первое из них показывает начальное, а второе  - конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом q и после пробела дается одно целое число из интервала [1; n]. Оно указывает позицию, которая интересует физиков.

Выходные данные
Выведите столько строк, сколько вопросов во входном файле. В строке номер i надо записать ответ на вопрос i — название соответствующей частицы x, y или z.

Пояснения к примеру
Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,
 

Примеры

"Сортировка" с конфеткой

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

Выходные данные
Требуется вывести массив после сортировки.

Примеры

Переключение между окнами

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

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

Входные данные
В первой строке вводится целое число n – количество действий пользователя ( 1 ≤ n ≤ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

Выходные данные
Выведите  n строк – последовательность имен приложений, с которыми работал пользователь в порядке, в котором их окна становились активными.
 

Примеры

Отслеживание контактов

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

1. Ровно одна корова была инфицирована изначально (нулевой пациент).
2. После того, кaк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
3. Однажды заболев, она остаётся больной.

Примеры

Trapped in the Haybales

Турнир

В турнире участвуют N команд. Турнир проводится по олимпийской системе (команды играют на вылет, проигравшие команды выбывают из турнира, выигравшие проходят в следующий тур, ничьих не бывает). Число команд в этой задаче будет степенью двойки: N = 2 ^k .

Все команды пронумерованы числами от 1 до N. В первом туре играют команды с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 матчей. По результатам этих матчей команды выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д.

Вам даны результаты всех матчей. Определите номер команды, которая стала победителем турнира.
В первой строке входных данных записано число N – количество команд, участвовавших в турнире. Оно является степенью двойки и может принимать значения от 2⁰ = 1 до 2¹⁶ = 65536. Следующие N − 1 строк содержат результаты всех сыгранных матчей. Первые N/2 строк из них являются результатами матчей первого тура, затем идёт N/4 строк с результатами второго тура, N/8 строк с результатами третьего тура и т. д.

Результат каждого матча является одним из двух возможных чисел: 1 или 2. Число 1 означает, что в матче выиграла первая команда (номер которой меньше), число 2 означает, что в матче выиграла вторая команда (номер которой больше).
Программа должна вывести одно число – номер победившей в турнире команды.
 

Наша Таня громко плачет

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

Сегодня рабочий день системного администратора Миши начался со звонка секретаря Тани, которая в очередной раз не справилась с редактированием документа. Миша моментально пришёл к Тане и узнал, что в результате ошибки в папке на ее компьютере оказалось n копий документа, над которым она сейчас работает. Других документов в папке нет. Таня просит Мишу удалить лишние копии, чтобы у неё осталась ровно одна копия нужного файла.

Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

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

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

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

В первой строке содержится целое число n ( 1 <= n <= 2*10⁹ ) - количество копий документа в папке у Тани. 
Во второй строке содержится целое число k ( 1 <= k <= 2*10⁹ ) - количество раз, в которое уменьшает количество файлов вторая команда.
В третьей строке содержится целое число A ( 1 <= A <= 2*10⁹ ) - количество секунд, которое Миша тратит на выполнение первой команды.
В четвёртой строке содержится целое число B ( 1 <= B <= 2*10⁹ ) - количество секунд, которое Миша тратит на выполнение второй команды.

Выведите единственное число - минимальное количество секунд, которое придётся потратить Мише на решение проблемы.

В первом тестовом примере оптимальная стратегия Миши такова:

• За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .
• За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
• За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
• За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

На выполнение этих четырёх операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.
 

Примеры

Полимино

Известный математик Соломон В. Голомб предложил название полимино для связной фигуры, вырезанной из клетчатой бумаги по линиям сетки. Фигура называется связной, если из любой ее клетки можно добраться в любую другую, переходя из клетки в клетку через их общую сторону. Шахматист, добавил Голомб, сказал бы, что из любой клетки полимино можно дойти ладьей в любую другую. На рис. 1 приведены примеры восьми полимино.

Сашу заинтересовало, сколько существует различных способов вырезать новое полимино из старого при заданном значении K, если повороты, отражения и переворачивания как нового полимино, так и старого, недопустимы.

Например, на рис. 2б приведены все возможные способы вырезания полимино, приведенного на рис. 2а, при K = 2.

Напишите программу, которая ответит на интересующий Сашу вопрос.

Первая строка входных данных содержит число K (1 ≤ K ≤ 10 000).

Далее следуют описания двух полимино, сначала нового, затем старого. Каждое полимино задается следующим образом — в первой строке описания задаются размеры H (высота) и W (ширина) минимально возможного прямоугольника, в котором можно разместить данное полимино. Следующие Н строк содержат по W символов описания клеток. При этом клетка, входящая в полимино, обозначается символом « X» (прописная латинская буква «икс»), а не входящая — символом «.» (точка). Количество клеток в каждом полимино не превышает 300.

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

Форматирование документа

Вася пишет новую версию своего офисного пакета <<Closed Office>>. Недавно он начал работу над редактором <<Dword>>, входящим в состав пакета.

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

Документ в формате редактора <<Dword>> представляет собой последовательность абзацев. Каждый абзац представляет собой последовательность элементов — слов и рисунков. Элементы одного абзаца разделены пробелами и/или переводом строки. Абзацы разделены пустой строкой. Строка, состоящая только из пробелов, считается пустой.

Слово — это последовательность символов, состоящая из букв латинского алфавита, цифр, и знаков препинания: <<.>>, <<,>>, <<:>>, <<;>>, <<!>>, <<?>>, <<->>, <<’>>.

Рисунок описывается следующим образом: <<(image параметры рисунка)>>. Каждый параметр рисунка имеет вид <<имя=значение>>. Параметры рисунка разделены пробелами и/или переводом строки. У каждого рисунка обязательно есть следующие параметры:

Документ размещается на бесконечной вверх и вниз странице шириной \(w\) пикселей (разбиение на конечные по высоте страницы планируется в следующей версии редактора). Одна из точек на левой границе страницы условно считается точкой с ординатой равной нулю. Ордината увеличивается вниз.

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

Абзац размещается следующим образом. Элементы располагаются по строкам. Каждая строка исходно имеет высоту \(h\) пикселей. В процессе размещения рисунков высота строк может увеличиваться, и строки могут разбиваться рисунками на фрагменты.

Слова размещаются следующим образом. Считается, что каждый символ имеет ширину \(c\) пикселей. Перед каждым словом, кроме первого во фрагменте, ставится пробел шириной также в \(c\) пикселей. Если слово помещается в текущем фрагменте, то оно размещается на нем. Если слово не помещается в текущем фрагменте, то оно размещается в первом фрагменте текущей строки, расположенном правее текущего, в котором оно помещается. Если такого фрагмента нет, то начинается новая строка, и поиск подходящего фрагмента продолжается в ней. Слово всегда <<прижимается>> к верхней границе строки.

Размещение рисунка зависит от его расположения относительно текста.

Если расположение рисунка относительно текста установлено в <<embedded>>, то он располагается так же как слово, за тем исключением, что его ширина равна ширине, указанной в параметрах рисунка. Кроме того, если высота рисунка больше текущей высоты строки, то она увеличивается до высоты рисунка (при этом верхняя граница строки не перемещается, а смещается вниз нижняя граница). Если рисунок типа <<embedded>> не первый элемент во фрагменте, то перед ним ставится пробел шириной \(c\) пикселей. Рисунки типа <<embedded>> также прижимаются к верхней границе строки.

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

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

Если расположение рисунка относительно текста установлено в <<floating>>, то рисунок размещается поверх текста и других рисунков и никак с ними не взаимодействует. В этом случае у рисунка есть два дополнительных параметра: <<dx>> и <<dy>> — целые числа, задающие смещение в пикселях верхнего левого угла рисунка вправо и вниз, соответственно, относительно позиции, где находится верхний правый угол предыдущего слова или рисунка (или самой левой верхней точки первой строки абзаца, если рисунок — первый элемент абзаца).

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

Верхняя граница следующего абзаца совпадает с более низкой точкой из нижней границы последней строки и самой нижней границы рисунков типа <<surrounded>> предыдущего абзаца.

По заданным \(w\), \(h\), \(c\) и документу найдите координаты верхних левых углов всех рисунков в документе.

Формат входных данных
Первая строка содержит три целых числа: \(w\), \(h\) и \(c\) (\(1 \le w \le 1000\), \(1 \le h \le 50\), \(1 \le c \le w\)).

Далее следует документ. Размер входного файла не превышает 1000 байт. Гарантируется, что ширина любого слова и любого рисунка не превышает \(w\). Высота всех рисунков не превышает \(1000\). Относительное смещение всех рисунков типа <<floating>> не превышает \(1000\) по абсолютной величине.

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

На лифтах через пропасть

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

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

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

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

Формат входных данных
Первая строка содержит целое число \(n\) — количество лифтов (\(1 \le n \le 100\)). Следующие \(n\) строк содержат описания лифтов.

Каждое описание состоит из четырех целых чисел: \(l\), \(u\), \(s\) — самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах (\(-100 \le l \le s \le u \le 100\), \(l < u\)), и \(d\) — направление движения лифта в начальный момент (\(d = 1\) означает, что лифт двигается вверх, \(d = -1\) — вниз).

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

Парикмахерская

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

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

Входные данные
В первой строке вводится натуральное число N, не превышающее 100 – количество клиентов.

N строках вводятся времена прихода клиентов – по два числа, обозначающие часы и минуты (часы – от 0 до 23, минуты – от 0 до 59). Времена указаны в порядке возрастания (все времена различны).
Гарантируется, что всех клиентов успеют обслужить до полуночи.

Выходные данные
Требуется вывести N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-го клиента (часы и минуты).

Маджонг

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

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


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

Цель игры состоит в том, чтобы сделать как можно больше ходов.

Задана начальная расстановка фишек на доске. Требуется найти самую длинную последовательность ходов, которую может сделать Петя из заданной позиции.
Входные данные
Первая строка входного файла содержит размеры доски: два целых числа m и n (1 ≤ m, n ≤ 300, хотя бы одно из этих чисел четно). Далее следуют m строк по n
 чисел в каждой, j-е число в i-й из этих строк представляет собой номер цвета j-й слева фишки в i-й горизонтали. Цвета пронумерованы натуральными числами от 1 до n*m / 2. На доске ровно две фишки каждого цвета.

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

Сортировка вагонов

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.




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

Входные данные
Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

Выходные данные
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

 

Примеры

Исследование зеркальных цветов

Члены экипажа космического корабля «Пегас» приземлились на третьей планете Системы Медуза, для изучения зеркальных цветов. Их корабль приземлился в начале узкого поля фермы, на которой выращивают цветы. Зеркальные цветы начинают прорастать после полуночи. Любезные работники фермы предоставили экипажу план прорастания цветов в виде точки и времени прорастания. Экипажу корабля необходимо улетать с планеты в следующую полночь. Исследовательская группа корабля может передвигаться по планете с максимальной скоростью vmax. На исследование одного цветка группе необходимо время d. Исследовать цветок необходимо сразу весь, нельзя будет к нему вернуться позже. Цветы прорастают тем позже, чем дальше они расположены от начала поля. В одной точке прорастает только один цветок, и каждый цветок прорастает в свой момент времени. Нет двух цветков, которые бы проросли одновременно.
Команда экипажа хочет определить момент времени, когда исследовательская группа сможет вернуться на корабль, исследовав все цветы и затратив на исследование как можно меньше времени.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит 2 целых числа через один пробел: vmax (в см/мин) и d (в минутах), 0 < vmax <= 200, 0 <= d <= 500.
Вторая строка содержит одно число N – количество цветов (в штуках). 0 <= N <= 1400 при d = 0, в противном случае 0 <= N <= 200.
Далее идут N строк, в каждой из которых записано по два числа через пробел: целое число xi – расстояние от цветка до начала поля (в сантиметрах), 0 <= x_i <= 32767, и число ti – момент прорастания цветка (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

Выходные данные
Выведите момент времени возвращения исследовательской группы на корабль (в формате hh:mm), округленный до целых минут в большую сторону.

Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Можно считать, что исследовательская группа не меняет направления движения до тех пор, пока не дойдет до последнего цветка.

 

Примеры

3 1 
1
100 00:01

01:08

Часы с боем

Старинные часы бьют каждые полчаса. Причем в начале каждого часа они бьют столько раз, сколько сейчас часов (по 1 разу – в час ночи и в час дня, по 2 раза – в два часа ночи в два часа дня и т.д., в полночь и в полдень они бьют, соответственно, по 12 раз). И еще 1 раз они бьют в середине каждого часа.

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

Входные данные
В первой строке записан начальный момент времени, во второй строке — конечный. Моменты времени задаются двумя целыми числами, разделяющимися пробелом. Первое число задает часы (от 0 до 23), второе — минуты (от 1 до 59, при этом оно не равно 30).

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

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

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

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

21739

В каком из вариантов ответов верно соблюден порядок осуществления информационных процессов?

1. сбор, передача, обработка, хранение
2. сбор, хранение, передача, обработка
3. сбор, обработка, хранение, передача
4. сбор, хранение, передача, обработка

18756

Пользователь работал с каталогом Химия. Сначала он поднялся на один уровень вверх, затем спустился на один уровень вниз, потом ещё раз спустился на один уровень вниз. В результате он оказался в каталоге C:\Школа\Уроки\Информатика Запишите полный путь каталога, с которым пользователь начинал работу.

1) C:\Школа\Уроки\Химия
2) C:\Химия
3) C:\Школа\Уроки\Класс\Химия
4) C:\Школа\Химия

18748

18746

1606

 Поиск слова в тексте по заданному образцу является процессом:

1297

Пользователь работал с каталогом C:\Учеба\Математика\Задания. Сначала он поднялся на один уровень вверх, затем еще раз поднялся на один уровень вверх и после этого спустился в каталог Биология, далее спустился в каталог Оценки. Запишите полный путь каталога, в котором оказался пользователь.

Время (while): длинные перерывы

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

Формат входных данных

Каждая строка содержит два целых числа: часы и минуты начала урока (0 ≤ часы ≤ 20, 0 ≤ минуты ≤ 59). Последовательность заканчивается строкой «0 0». Она не является временем урока. Гарантируется, что уроков не менее двух.

Формат выходных данных

Одно число — количество перерывов длительностью строго более 30 минут.

Конвейерный отель

Вы с друзьями уже давно заехали в отель, но только сейчас выяснилось, что в отеле существуют так называемые <<Тихие часы>>. Во время этих часов все должны находиться в своих комнатах, и обойти это ограничение нельзя, потому ключи от комнат на время <<Тихих часов>> забирает персонал отеля. К счастью, вам повезло и вы с друзьями живёте на одном этаже, в последовательных комнатах с номерами от \(1\) до \(n\). Расстояние между соседними комнатами равно 5 метрам.

Вы пришли к достаточно изящной идее, которая поможет справиться со столь сложной ситуацией. За одну ночь под всеми комнатами вы проложили конвейер из \(3n\) ячеек, позволяющий перевозить посылки. Соседние ячейки, так же, как и комнаты, находятся на расстоянии 5 метров друг от друга. Ячейки конвейера с номерами от \(n + 1\) до \(2n\) находятся под комнатами друзей, ячейки с номерами от \(1\) до \(n\) – левее комнаты номер \(1\), а ячейки с номерами от \(2n + 1\) до \(3n\) – правее комнаты с номером \(n\).

В один из таких <<Тихих часов>> каждый друг отправил посылку одному другому другу. Для того, чтобы перемещать посылки, есть две кнопки: <<ВПРАВО>> и <<ВЛЕВО>>, сдвигающие конвейер на 5 метров вправо и влево соответственно.

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

Первая строка входных данных содержит одно целое число \(n\) (\(2 \le n \le 100\,000\)) — число друзей, обменивающихся посылками.

Вторая строка содержит \(n\) целых чисел \(a_i\) (\(1 \le a_i \le n, a_i \ne i\)) — номер друга, которому адресована посылка \(i\)-го из друзей.

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

Разберём пример из условия. Сначала можно 1 раз нажать кнопку <<ВПРАВО>>, после этого второй друг получит посылку от первого, а третий — от второго. После этого необходимо 2 раза нажать на кнопку <<ВЛЕВО>>, тогда второй друг получит посылку от третьего. И наконец, нужно ещё 2 раза нажать кнопку <<ВЛЕВО>>, после чего первый друг получит посылку от четвёртого. Итого потребуется 5 нажатий.

B. Очередь в школе

Why Did the Cow Cross the Road III

Фермер Джон на старости лет стал параноиком. Он построил огромную изгородь вокруг фермы для защиты своих коров. Коровам такая идея не понравилась.

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

Для каждой из \(N\) коров, посещающих ферму, вам сообщается время, когда она прибывает к воротам и количество времени, которое её требуется для ответов на вопросы. В каждый момент времени только одна корова опрашивается, поэтому, если много коров прибывает примерно в одно и то же время, они должны ждать своей очереди отвечать на вопросы. Например, если корова прибыла во время 5 и отвечает на вопросы 7 единиц времени, то другая корова, прибывшая во время 8 должна подождать до времени 12, что начать отвечать на вопросы.

Определите минимально возможное время, за которое все коровы войдут на ферму.

Hoof, Paper, Scissors

Возможно Вы слышали об игре "Камень, Бумага, Ножницы". Коровы любят играть в похожую игру "Копыто, Бумага, Ножницы" Правила игры "Копыто, Бумага, Ножницы" просты. Две коровы играют друг против друга. Они обе считают до трёх, а затем одновременно делают жест, представляющий копыто, бумагу или ножницы. Копыто выигрывает у ножниц, ножницы выигрывают у бумаги, бумага выигрывает у копыта. Конечно может быть и ничья, если обе коровы сделали один и тот же жест.

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом переключившись на другой не более одного раза за все игры. Например, она может играть "Копыто" первые \(x\) игр, и затем переключится на "бумагу" на оставшиеся \(N-x\) игр.

По заданной последовательности жестов ФД, определите максимальное количество игр, которое выиграет Бесси.

Fort Moo

Беси строит форт прямоугольной формы.

Она уже выбрала место - кусок земли \(N\) метров по \(M\) метров (\(1 \leq N, M \leq 200\)). К несчастью, на этом месте есть болотистые участки, на которых строительство невозможно. Помогите Беси определить наибольшую (по площади) область, на которой можно построить форт, так , чтобы форт не проходил через болотистые участки.

Cow Routing

Устав от холодной зимы Беси планирует слетать куда потеплее на каникулах.
К несчастью, только одна кампания Air Bovinia продаёт билеты коровам.

Air Bovinia имеет N самолётов (1 <= N <= 500), каждый из которых
летает по собственному маршруту, состоящему из
двух или более городов. Например, такому: маршрут
начинается в городе 1, затем самолёт летит в город 5,
затем в город 2, затем в город 8. Никакой город не появляется
в этом маршруте дважды и более раз. Если Беси
выбрала маршрут, то она может сесть на него в любом городе
этого маршрута и сойти также в любом городе этого маршрута.
Она не обязана садиться в самолёт в первом городе маршрута
и выходить в последнем. Каждый маршрут имеет определённую цену,
которую Беси должна заплатить, если она использует
любую часть маршрута, не зависящую от количества городов,
которые она посетит во время маршрута.

Беси хочет найти самый дешёвый способ пропутешествовать от её фермы
(город A) до её "тёплого местечка" (город B).
При этом она хочет использовать только один маршрут,
чтобы не мучиться с пересадками.
Помогите ей определить минимальную цену, которую ей придётся заплатить.

Формат входных данных

Первая строка содержит числа A,B,N разделённые одиночными пробелами.

Следующие 2N строк описывают доступные маршруты - по две строки на маршрут.

Первая строка содержит цену этого маршрута (целое число от 1 до 1000)
и количество городов, вдоль этого маршрута (целое число от 1 до 500).

Вторая строка содержит список городов в порядке посещения вдоль этого
маршрута. Каждый город идентифицируется целым числом от 1 до 10,000.

Формат выходных данных

Выведите минимальную стоимость одного маршрута, который Беси
может использовать для перемещения из города A в город B.
Если такого маршрута нет, выведите -1.

Примечание

Хотя имеется более дешёвый решение из двух маршрутов (маршрут 2
из города 1 в город 3, затем маршрут 1 из города 3 в город 2),
Беси выбирает только прямой маршрут
- маршрут 3, цена которого равна 8.

Speeding Ticket

Беси, которая всегда создаёт проблемы, украла трактор Фермера Джона и помчалась вниз по дороге!

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

По заданной выше информации, определите максимальное превышение скорости, которое допустила Беси во время путешествия.

Speeding Ticket

Беси, которая всегда создаёт проблемы, украла трактор Фермера Джона и помчалась вниз по дороге!

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

По заданной выше информации, определите максимальное превышение скорости, которое допустила Беси во время путешествия.

Reflection

п»ї

У Фермера Джона есть квадратный холст, представленный решёткой из \(N\) * \(N\) ячеек, (\(2 \leq N \leq 2000\), \(N\) чётное). Он рисует по следующим правилам:

1. Сначала он делит холст на четыре равных квадранта, разделённых горизонтальными и вертикальными линиями через центр холста.
2. Далее он рисует любимую картинку в правом верхнем квадранте холста. Каждая ячейка верхнего правого квадранта или закрашена (представлено символом '#') или не закрашена (представлено символом '.').
3. Наконец, гордясь своим рисунком, он отражает его через ранее указанные вертикальные и горизонтальные линии в другие квадранты холста.

Например, предположим \(N=8\) и ФД нарисовал следующую картинку в правом верхнем квадранте на шаге 2:

.#..
.#..
.##.
....

Тогда после отображения через горизонтальные и вертикальные линии в другие квадранты на шаге 3, холст будет выглядеть так:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

Однако, пока ФД спал, Беси пробралась в его амбар и украла холст. А затем занялась вандализмом: Она стерла некоторые ячейки и закрасила некоторые другие ячейки. После чего вернула холст ФД.

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

Вам задан холст после вандализма Беси, а также последовательность \(U\) (\(0\le U \leq 10^5\)) модификаций холста, каждое переключает ячейку в '.', если в ней была '#' и наоборот. Прежде каждого обновления и после каждого обновления выведите минимальное количество операций \(x\), которое требуется выполнить, чтобы отражение было удовлетворено.

ПР�МЕР ВВОДА:

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

ПР�МЕР ВЫВОДА:

4
3
2
1
0
1

Следующий холст удовлетворяет условию отражения и отличается от оригинального холста на 4 операции:

....
####
####
....

Невозможно сделать исходный холст удовлетворяющим условию отражения испольуя менее чем 4 операции.

После обновления \((1, 3)\), холст выглядит так:

....
##.#
####
..##

Требуется 3 операции, чтобы холст стал удовлетворять условию отражения.

После обновления \((2, 3)\), холст выглядит так:

....
####
####
..##

Требуется 2 операции, чтобы сделать холст удовлетворяющим условию отражения.

Автор: Chongtian Ma

Walking in Manhattan

п»ї

Фермер Джон и его \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) коров на Манхеттене. Коровы сбежали и гуляют по городу. В Манхеттене \(N\) (\(1 \le N \le 2 \cdot 10^5\)) дорог проходящие бесконечно на \(x\)-\(y\)-плоскости. Все они расположены или горизонтально, или вертикально. Каждая горизонтальная или вертикальная может быть смоделирована уравнением вида \(y = c_i\) или \(x = c_i\), где \(c_i\) целое число в интервале от \(0\) до \(10^9\) включительно.

ФД знает точно где каждая корова начала путешествие и время путешествия. Каждая из коров движется по следующему шаблону:

• РћРЅР° двигается РЅР° север (\(+y\)) или восток (\(+x\)) РЅР° РѕРґРЅСѓ единицу РІ секунду.
• Если РѕРЅР° РЅР° одиночной РґРѕСЂРѕРіРµ, РѕРЅР° продолжает двигаться РїРѕ ней.
• Если РѕРЅР° РЅР° пересечении РґРІСѓС… РґРѕСЂРѕРі, РѕРЅР° идёт РЅР° север, РЅР° чётной секунде путешествия Рё РЅР° восток иначе.

ВАм дана карта Манхэттена и информация о каждой корове, помогите ФД где его коровы сейчас.

ПР�МЕР ВВОДА:

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

ПР�МЕР ВЫВОДА:

14 5
7 13
6 15
6 16
110 4

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Автор: Benjamin Qi

Majority Opinion

У Фермера Джона важная задача - решить какой тип сена купить для своих коров.

У Фермера Джона есть \(N\) коров (\(2 \le N \le 10^5\)) пронумерованных от \(1\) до \(N\). Каждая корова любит ровно один тип сена \(h_i\) (\(1 \le h_i \le N\)). ФД хочет, чтобы все его коровы любили один тип сена.

Чтобы это случилось, ФД может сформировать фокус-группы. Фокус-группа состоит из всех коров в непрерывном интервале от \(i\) до \(j\), включительно. Если в фокус-группе более половины коров любит один и тот же некоторый тип сена, то все коровы начинают любить этот тип сена, иначе ни у одной коровы не изменяется любимый тип сена. Например, если фокус группа состоит из 16 коров, 9 или более из которых любят один и тот же тип сена, то и остальные 7 коров теперь будут любить этот же тип сена.

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

Milk Exchange

\(N\) \((1 \leq N \leq 5 \cdot 10^5)\) коров Фермера Джона выстроены в круг. \(i\)-ая корова имеет ведро с целой вместимостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально полные.

Каждую минуту корова \(i\) передаёт всё молоко из своего ведра корове \(i+1\) для \(1\le i<N\), а корова \(N\) передаёт своё молоко корове \(1\). Все обмены проходят одновременно (то есть, если корова отдаёт \(x\) литров молока и также получает \(x\) литров молока, её количество молока не изменяется). Если количество молока у коровы \(i\) превысит значение \(a_i\), тогда лишнее молоко теряется.

После каждой из минут \(1, 2, \dots, N\) - сколько молока останется у всех коров вместе?

Rotate and Shift

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

Чтобы отпраздновать начало весны, \(N\) коров фермера Джона (\(1 \leq N \leq 2 \cdot 10^5\)) придумали новый интригующий танец, в котором они встают в круг и перестраиваются предсказуемыv способом.

В частности, по кругу есть \(N\) позиций, пронумерованные последовательно от \(0\) до \(N-1\), причем позиция \(0\) следует за позицией \(N-1\). На каждой позиции находится корова. Коровы также последовательно нумеруются от \(0\) до \(N-1\). Изначально корова \(i\) находится в позиции \(i\). Вам сообщают набор из \(K\) позиций \(0=A_1<A_2< \ldots< A_K<N\), которые являются «активными», что означает, что коровы в этих позициях будут двигаться следующими (\(1 \leq K \leq N\)).

В каждую минуту танца происходят две вещи. Во-первых, коровы в активных позициях меняются: корова в позиции \(A_1\) перемещается в позицию \(A_2\), корова в позиции \(A_2\) перемещается в позицию \(A_3\) и так далее, с коровой в позиции \(A_K\) переход на позицию \(A_1\). Все эти \(K\) перемещения происходят одновременно, поэтому после завершения вращения все активные позиции по-прежнему содержат ровно одну корову. Далее смещаются сами активные позиции: \(A_1\) становится \(A_1+1\), \(A_2\) становится \(A_2+1\) и так далее (если \(A_i = N-1\) для некоторой активной позиции, то \(A_i\) возвращается к \(0\)).

Рассчитайте порядок коров после \(T\) минут танца (\(1\le T\le 10^9\)).

Following Directions

**Замечание: Время на тест в этой задаче 8s, в четыре раза больше чем по умолчанию.**

У Фермера Джона есть большое квадратное поле из \((N+1)\times (N+1)\) (\(1\le N\le 1500\)) ячеек. Пусть ячейка \((i, j)\) обозначает ячейку в \(i\)-ой строке сверху, и в \(j\)-ом столбце слева. В каждой ячейке \((i, j)\) живёт по одной корове (\(1 \le i, j \le N\)), и каждая ячейка содержит указатель или вправо или вниз. Также каждая ячейка \((i, j)\) такая, что \(i=N+1\) или \(j=N+1\), кроме \((N+1, N+1)\), содержит бак с коровьей едой. Каждый чан содержит еду различной цены. Чан в ячейке \((i, j)\) стоит \(c_{i, j}\) (\(1 \le c_{i,j} \le 500\)).

Каждый день во время обеда ФД звонит в колокол и каждая корова движется по направлениям указателей пока не достигнет чана с едой и затем есть из этого чана. Затем все коровы возвращаются в исходные позиции к следующему дню.

Чтобы поддержать свой бюджет, ФД хочет узнать общую стоимость еды съедаемой коровами каждый день. Однако, каждый день перед обедом корова в некоторой ячейке \((i, j)\) меняет направление указателя "вправо" на "вниз" или наоборот. Этот знак остаётся в таком направлении и в последующие дни, пока не будет перевёрнут обратно позже.

Вам даны координаты указателя, который меняется каждый день. Выведите стоимость каждого дня (всего \(Q\) дней, \(1 \le Q \le 1500\)).

Leaders

У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 10^5\)). Каждая корова имеет породу Guernsey или Holstein. Коровы стоят в ряд пронумерованные \(1 \ldots N\).

Каждая корова записала свой список коров. А именно, список коровы \(i\) содержит диапазон коров, начиная с неё самой (коровы \(i\)) и до коровы \(E_i\) (\(i \leq E_i \leq N\)) включительно.

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

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

Hungry Cow

Беси - голодная корова. Каждый день на обед если есть пакеты сена в амбаре, она съедает ровно один пакет. Чтобы Беси не голодала, Фермер Джон присылает в некоторые дни некоторое количество пакетов с сеном, которые прибывают утром (до обеда). В частности в день \(d_i\), ФД присылает \(b_i\) пакетов сена (\(1\leq d_i \leq 10^{14}\), \(1 \leq b_i \leq 10^9\)).

Вычислите общее количество пакетов сена, которые съест Беси в течение \(T\) дней.

Farmer John Actually Farms

Фермер Джон вырастил \(N\) (\(1 \leq N \leq 2\cdot 10^5\)) аспарагусов на своей ферме. Однако некоторые из этих растений имеют генетические отличия, поэтому некоторые растения растут быстрее чем другие. Изначальная высота \(i\)-го растения равна \(h_i\) дюймов и после каждого дня \(i\)-ое растение вырастает на \(a_i\) дюймов.

ФД любит некоторые растения больше чем другие, и он хочет, чтобы некоторые растения были выше чем другие. Он дал Вам массив различных целых чисел \(t_1,\dots,t_N\), содержащих все целые числа от \(0\) до \(N-1\) и хочет, чтобы \(i\)-ое растение имело ровно \(t_i\) растений, которые выше этого. Определите минимальное количество дней, чтобы требование ФД было удовлетворено или укажите, что это невозможно.

Заметим, что тесты этой задачи могут потребовать использования 64-битного целого типа (например, "long long" в C/C++).

Candy Cane Feast

Коровы Фермера Джона любят конфетные трости. У ФД \(N\) коров с определённой начальной высотой. Он хочет скормить им \(M\) конфетных тростей, различной высоты (\(1\le N,M\le 2\cdot 10^5\)).

ФД планирует кормить коров конфетными тростями одну за одной в порядке, в котором они заданы на вводе. Чтобы кормить коров ФД вывешивает конфетные трости так, чтобы изначально они касались земли. Коровы выстраиваются одна за одной в порядке, как они заданы на входе. Каждая ест до своей высоты (потому что выше не достаёт). Трость остаётся на месте где она изначально была подвешена и не опускается к земле, даже после того как её нижняя часть съедена. Возможно, что когда подойдёт очередь некоторой коровы она ничего не сможет съест, если нижняя часть трости уже выше высоты этой коровы. После того как пройдёт очередь всех коров, они подрастают на высоту равную количеству единиц трости, которую съела корова, а ФД вывешивает новую конфетную трость и коровы повторяют процесс опять (корова 1 всегда начинает есть первой).

Email Filing

Фермер Джон реорганизует свою электронную почту. Его экран выглядит как вертикальный список папок с левой стороны экрана и и вертикальный список писем с право стороны экрана. Имеется \(M\) папок, пронумерованных \(1 \ldots M\) (\(1 \le M \le 10^4)\). Его почта сейчас содержит \(N\) писем, пронумерованных \(1\ldots N\) (\(1 \le N \le 10^5\)); \(i\)-ое письмо необходимо переместить в папку \(f_i\) (\(1\le f_i\le M\)).

Экран ФД небольшой, поэтому он может видеть одновременно \(K\) (\(1\le K\le \min(N,M)\)) папок и \(K\) писем одновременно. Изначально, его экран показывает папки \(1 \ldots K\) слева и письма \(1 \ldots K\) справа. Для того чтобы увидеть другие папки и письма, он должен скроллить соответствующие списки. Например, если он проскроллит вниз на одну позицию в списке папок, он увидит папки \(2 \ldots K+1\), а если проскроллит ещё на одну позицию вниз, он увидит папки \(3 \ldots K+2\). Когда ФД переносит письмо в папку, оно исчезает из списка писем, и все нижние письма поднимаются на одну позицию вверх. Например, пусть на экране отображены письма \(1, 2, 3, 4, 5\) и ФД переносит письмо 3 в соответствующую папку, тогда видимая часть списка писем станет такой: \(1, 2, 4, 5, 6\). ФД может переносить письма только в назначенные им папки.

К несчастью, колесо скроллинга на мышке ФД сломалось, и он может скроллить только вниз и не может скроллить вверх. Единственное подобие скроллинга вверх если он видит последние \(K\) писем из своего списка и переносит в папку одно из них. В этом случае после переноса список опять покажет последние \(K\) ещё не разнесенных писем, что соответствует скроллингу вверх на одно письмо. Если осталось менее \(K\) писем, они отображаются все.

Помогите ФД определить, может ли он разнести по папкам все свои письма.

Loan Repayment

Фермер Джон должен Беси \(N\) галлонов молока (\(1\le N\le 10^{12}\)). Он должен вернуть ей молоко в течение \(K\) дней. Однако он не хочет отдавать молоко слишком быстро. С другой стороны, он должен показывать прогресс в возвращении долга. Поэтому он должен возвращать Беси не менее \(M\) галлонов молока (\(1\le M\le 10^{12}\)) каждый день.

ФД собирается делать так. Он выбирает положительное целое число \(X\). А затем повторяет следующую процедуру каждый день:

1. Предположим, что ФД уже отдал Беси \(G\) галлонов молока, он вычисляет \(\frac{N-G}{X}\) с округлением вверх. Назовём это число \(Y\).
2. Если \(Y\) меньше чем \(M\), то устанавливает \(Y\) равным \(M\).
3. Даёт Беси \(Y\) галлонов молока.

Определите максимальное \(X\) такое, что если ФД будет следовать этой процедуре, то ФД отдаст Беси не менее \(N\) галлонов молока после \(K\) дней (\(1\le K\le 10^{12}\)).

Left Out

Фермер Джон снова фотографирует своих коров.

На этот раз он делает фото с воздуха. Он хочет, чтоб все его коровы смотрели в одну сторону. Сейчас коровы организованы в решётку \(N \times N\), (\(2 \leq N \leq 1000\)) внутри квадратного пастбища, как показано ниже:

RLR
RRL
LLR

Здесь 'R' означает, что корова смотри вправо, 'L' означает, что корова смотрит влево. Поскольку коровы находятся в стаде, ФД не может говорить повернуться одной корове. Всё что он может - это повернуть целую строку или целый столбец повернув коров 'L' на 'R' или 'R' на 'L' внутри этой строки/столбца. ФД может поворачивать столбцы и строки сколько угодно раз, в том числе и поворачивать один тот же столбец или строку более чем один раз.

Как оказалось, ФД не может перевернуть всех коров в одном направлении, Но может всех коров кроме одной - определите эту корову.

Icy Perimeter

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

Конфигурация мороженого, которое производится машиной, может быть описано решёткой \(N \times N\) grid (\(1 \leq N \leq 1000\)):

##....
....#.
.#..#.
.#####
...###
....##

Каждый символ '.' представляет пустое место, а каждый символ '#' представляет \(1 \times 1\) квадратную ячейку мороженого.

К несчастью, сейчас машина работает не очень хорошо и может производить несколько несвязанных сгустков мороженого (на картинке сверху их два). Сгусток мороженого называется связным, если из любой ячейки сгустка можно добраться до любой другой ячейки, перемещаясь в соседнюю по одному из четырёх направлений (север, юг, запад, восток).

ФД хочет найти площадь и периметр сгустка, который имеет наибольшую площадь. Площадь сгустка равна количеству символов '#' в его картинке. Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и периметр 6, а больший сгусток имеет площадь 13 и периметр 22.

Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они рассматриваются как независимые сгустки. Например, ниже представлен сгусток площади 1 внутри сгустка площади 16:

#####
#...#
#.#.#
#...#
#####

Sleepy Cow Herding

Три лучшие коровы Фермера Джона Беси, Эльза и Милдред всегда уходят далеко от фермы. Помогите ФД "сгрудить их в стадо".

Главное поле фермы можно представить в виде числовой прямой, и каждая корова находится в целочисленной координате. Все три координаты различны. ФД хочет переместить их так, чтобы они заняли последовательные координаты (например, 6,7,8).

В любой момент времени ФД может заставить корову двигаться только, если она находится в "конечной" точке (минимальной или максимальной позиции среди всех коров). Когда он перемещает корову, он говорит ей двигаться на любую незанятую целую позицию, так чтобы она перестала быть в конечной точке. С течением времени такие передвижения обеспечивают сближение коров.

Определите минимальное и максимальное количество перемещений, которое возможно сделать прежде чем коровы расположатся в трёх последовательных позициях.

Cow Gymnastics

Чтобы улучшить свои фигуры коровы занялись гимнастикой. Фермер Джон назначил любимую корову Бесси тренером для \(N\) других коров. В каждом из \(K\) практических занятий (\(1 \leq K \leq 10\)), Бесси ранжирует \(N\) коров в соответствии с их результатами (\(1 \leq N \leq 20\)).

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

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

Lifeguards

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

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(t=1000\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

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

Taming the Herd

Однажды утром Фермер Джон проснулся от звуков дробления древесины. Это коровы ломали амбар.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако некоторые записи потерялись.

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

The Bucket List

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

У ФД \(N\) коров (\(1 \leq N \leq 100\)), последовательно пронумерованных \(1 \ldots N\). I-ую корову необходимо доить в интевале от времени \(s_i\) до времени \(t_i\), и для дойки требуется \(b_i\) бидонов. Процесс дойки нескольких коров может проходить в одно и то же время. Если так, то не могут использоваться одни и те же бидоны для дойки разных коров. То есть, бидон, назначенный корове \(i\) не может для дойки других коров во время от \(s_i\) до \(t_i\). Вне этого временного окна, этот бидон может быть использован для дойки других коров. Для того, чтобы упростить себе работу, ФД обеспечивает, что в любой момент времени не более одна корова начинает или заканчивает дойку. (то есть все \(s_i\) и \(t_i\) различны)

У ФД есть место, где храняться все бидоны, последовательно пронумерованные 1, 2, 3 ... В текущей стратегии дойки, когщда некоторая корова (например корова \(i\)) начинает дойку (в момент времени \(s_i\)) ФД идёт в комнату хранения, берёт \(b_i\) баллонов с наименьшими номерами и назначает их для дойки коровы \(i\).

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

The Bovine Shuffle

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

Он решил учить их танцу "Bovine Shuffle". Этот танец состоит из \(N\) коров (\(1 \leq N \leq 100\)) выстроенных в ряд в некотором порядке, после которого они снова будут выстроены в ряд, возможно в другом порядке. ФД отметил позиции \(1 \ldots N\), и первая корова становится на позицию 1, вторая - на позицию 2, ..., последняя на позицию \(N\).

Перестановка описывается N числами \(a_1 \ldots a_N\), где корова из позиции i перемещается на позицию \(a_i\) во время перестановки (и конечно каждое \(a_i\) есть число от 1 до N). Каждая корова двигается на свою новую позицию во время перестановки. К счастью, все \(a_i\) различны, поэтому никакие две коровы не пойдут в одну и ту же позицию во время перестановки.

Каждой из коров ФД назначен уникальный ID из 7 цифр. Вам даётся порядок коров после трёх перестановок, определите начальный порядок.

Bull in a China Shop

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

Форма этой коровы описывается решёткой из \(N \times N\) символов (\(3 \leq N \leq 8\)), пример показан ниже, где символы '#' представляют часть коровы, а символы '.' не части коровы.

...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............

К несчастью, ФД ещё не спел купить корову, как в магазинчик ворвался бык, который поломал всё вокруг, включая корову ФД. Корова разломалась на две части, которые затерялись среди других \(K\) (\(3 \leq K \leq 10\)) кусков стекла на полу. Каждый из этих \(K\) кусков описывается решёткой \(N \times N\) символов, как и исходная фигурка.

Помогите ФД определить, какие из этих \(K\) кусков являются двумя частями фигурки ФД. При падении на землю куски ФД не поворачивались и не переворачивались, поэтому для их сборки ФД должен только сдвигать куски горизонтально или вертикально. Куски не могут наезжать друг на друга и должны сформировать точно исходную фигуру.

ФД может двигать оба куска горизонтально и/или вертикально на любое количество позиций, но так, чтобы все символы '#' оставались внутри решётки \(N \times N\). Форма каждого из кусков необязательно состоит из связного региона символов '#'. Но при сдвиге все они сдвигаются на одинаковое количество позиций.

Building a Ski Course

Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:
RSRSSS RSRSSS RSRSSS
Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).
Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом. ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.
Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.
PROBLEM NAME: skicourse
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа M и N.
* Строки 2..M+1: M строк ровно по N символов (каждый R или S), описывающих желаемое финальное состояние поля.
Формат выходных данных
* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.

Airplane Boarding

Problem 3: Airplane Boarding [Travis Hance]
Коровы прибыли в в аэропорт и столкнулись с интересной проблемой.
В самолёте имеется N мест, которые мы моделируем как точки от x=1 до x=N на числовой прямой. Все N коров (1 <= N <= 200,000) стоят в ряд, ожидая занятия своего места. Корова N стоит на позиции x=0, корова N-1 на позиции x=-1 и т.д. Корове I назначено место S_i, где S₁, S₂, … - это перестановка чисел от 1 до N.
Каждую секунду каждая корова делает шаг вправо, если она может. Когда корова I достигает своего места S_i, она останавливается, чтобы положить багаж в верхний отсек салона, это занимает у неё T_i секунд, затем она садится. В течение этих T_i секунд, следующая за этой корова (если она есть) блокируется и не может двигаться вперёд. Если за ней вплотную стоят коровы, то они тоже все блокируются.
Сколько времени займёт посадка?
Сумма всех T_i будет меньше чем 1,000,000,000.
PROBLEM NAME: boarding
Формат входных данных
* Строка 1: Одно целое число, N.
* Lines 2..N+1: Два разделённых пробелом целых числа, S_i и T_i.
Формат выходных данных
* Строка 1: Одно целое число, задающее количество времени, которое потребуется, чтобы все коровы заняли свои места.
Примечание
После первой секунды, все сдвинутся на 1 вправо и корова 3 достигнет своего места:
123 123
Корове 3 потребуется 5 секунд, чтобы сесть, после чего она «исчезает».
12 123
Потребуется еще 3 секунды коровам 1 и 2 чтобы добраться до своих мест:
12 123
Корове 1 потребуется 5 секунд, чтобы сесть, корове 2 – 10, поэтому ВСЕ усядутся через 10 секунд.
Общее время посадки: 1 + 5 + 3 + 10 = 19 секунд

Bovine Ballet

Чтобы сломать стереотипное представление о коровах как о неловких созданиях, корова Беси пошла на балетные курсы. Ее финальное представление состоится на следующей неделе, и ФД хочет помочь ей, построив прямоугольную сцену, достаточную для всего ее представления.
Танец выполняется на прямоугольной сцене, состоящей из квадратных ячеек размером 1 х 1. Ноги Беси описываются следующим образом:
FR: передняя правая нога FL: передняя левая нога RR: задняя правая нога RL: задняя левая нога
В начале танца все 4 ноги находятся в соседних ячейках и формируют квадрат как показано ниже, причем Беси смотрит на север.
FL FR RL RR
Танец Беси - это последовательность из N инструкций (1 <= N <= 1000), где каждая инструкция предписывает либо переместить одну ногу на одну ячейку, или повернуться на 90 градусов по часовой стрелке.
Инструкции переместить ногу состоят из 3 символов, первые два описывают какую ногу перемещать, а последний символ указывает направление движения (F = вперед, B = назад, R = вправо, L = влево). Например, FRF означает переместить правую ногу вперед на одну ячейку, а RLR - означает переместить заднюю левую ногу вправо. Конечно направление движения относительно того направления, куда сориентирована Беси.
Инструкция на поворот также состоит из 3 символов, первые два указывают единственную ногу Беси, которая останется в той же клетке где была и вокруг которой она повернется на 90 градусов по часовой стрелке. В этом случае последний символ - P (поворот). Например, инструкция "FRP" означает, что Беси должна повернуться на 90 градусов по часовой стрелке вокруг своей стационарной передней правой ноги. Например, если Беси ориентирована на север, и ноги расположены так: .. .. .. .. .. FR .. FL .. .. RL RR
то после инструкции "FRP" ее ноги будут расположены так, а Беси будет ориентирована на восток:
RL FL .. RR .. FR .. .. .. .. .. ..
Вам даны N инструкций танца Беси, вычислите минимальную площадь сцены прямоугольной формы, необходимой для того чтобы ноги Беси находились на ней во время всего танца.
Если Беси шагнет в ту же ячейку, где сейчас находится другая нога, она упадет, и танец закончится, в этом случае выводите -1. Заметим, что это единственный случай, когда Беси упадет. Она хорошо напрактиковалась, и ее ноги могут находиться в самых разных, даже странных комбинациях, например, когда ее задние ноги находятся впереди передних.
PROBLEM NAME: ballet
Формат входных данных
* Строка 1: Цедое число N.
* Строки 2..1+N: Каждая строка содержит одну из 3-символьных инструкций.
Формат выходных данных
* Строка 1: Минимальная площадь прямоугольной сцены, содержащей ноги Беси во время всего танца, или -1, если Беси упадет.
Примечание
Беси нужна сцена 4 x 4, ее ноги будут располагаться так:
.. .. .. .. .. .. .. .. (смотрит на север) .. .. FL FR .. .. RL RR
After FRF:
.. .. .. .. .. .. .. FR (смотрит на север) .. .. FL .. .. .. RL RR
After FRP:
.. RL FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..
After RLB:
RL .. FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..

Cow Race

Чтобы окончательно решить вопрос кто быстрее, Беси и ее подруга Эльза решили провести гонки вокруг фермы.
Обе коровы стартуют в одном и том же месте, в одно и то же время и начинают бежать в одном направлении. Прогресс каждой коровы описывается серией отрезков, в течение которого данная корова имеет одинаковую скорость. Например, Бэси может бежать со скоростью 5 в течение 3 единиц времени, затем со скоростью 6 в течение 6 единиц времени. Обе бегут одинаковое общее количество времени.
Коровы попросили Вас посчитать количество раз, когда менялось лидерство в их гонке. Лидерство меняется в той точке времени, когда корова A обгоняет корову B или наоборот.
PROBLEM NAME: cowrace
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M. (1 <= N, M <= 1000)
* Строки 2..1+N: Каждая строка содержит один из N отрезков бега Беси, описанный двумя целыми числами: скорость и количество времени, которое она бежала с данной скоростью (оба числа в диапазоне от 1 до 1000).
* Строки 2+N..1+N+M: Каждая строка содержит один из M отрезков бега Эльзы, описанный двумя целыми числами: скорость и количество времени, которое она бежала с данной скоростью (оба числа в диапазоне от 1 до 1000).
Формат выходных данных
* Строка 1: Количество раз когда изменилось лидерство в забеге.
Примечание
Эльза была впереди до момента времени t=3, когда обе коровы пробежали 6 единиц расстояния, затем бежали вместе в течение одной единицы времени. Беси затем вырвалась вперед (первое изменение лидерства), затем ее обошла Беси (второе изменение лидерства), Беси так и осталась лидером до конца гонки.

The Bessie Shuffle

Беси тренируется делать карточные трюки. Она уже освоила уникальный
способ тасования M (2 <= M <= 100,000) карт так, чтобы i-ая карта сверху
становилась p[i] картой сверху.

Теперь она переходит в бОльшим колодам.
У Беси имеется колода из N карт (M<=N<=100,000), последовательно
пронумерованных 1..N. Она тасует её следующим образом: берёт первые M
карт и выполняет описанное выше тасование. И возвращает эти M карт
наверх колоды. Затем она забирает верхнюю карту из колоды и размещает
её значением вниз. Она продолжает этот процесс, выкладывая верхние
карты последовательно поверх друг друга, пока у неё не закончатся карты.
Когда у Беси становится карт меньше чем M, она больше не выполняет
тасование, но размещать верхнюю карту поверх ранее выложенных.

Беси знает, что изначально колода находится в отсортированном порядке с 1
наверху, потом 2 и т.д. N в конце. Вам задано описание тасования Беси.
Помогите Беси вычислить, какие карты окажутся на Q (1 <= Q <= N,
Q <= 5,000) указанных различных позициях в колоде.

PROBLEM NAME: shuffle

Формат входных данных

* Строка 1: Одна строка, содержащая N, M Q разделённые одиночными
пробелами

* Строки 2..1+M: Строка i+1 указывает позицию сверху P[i], i-ой карты в
тасовании Беси (1 <= P[i] <= M).

* Строки 2+M..1+M+Q: Строка i+1+M содержит одно целое число q_i
Описывающее i-ый запрос. Вы должны вычислить значение карты
неа позиции q_i сверху (1 <= q_i <= N).

Формат выходных данных

* Строки 1..Q: В i-ой строке, выведите одно целое число – значение карты
на позиции q_i сверху колоды по завершению процесса.

Примечание

Процесс протекает следующим образом

[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (выложить 2 значением вниз)
[3, 1, 4, 5] -> [1, 4, 3, 5] (выложить 1 значением вниз)
[4, 3, 5] -> [3, 5, 4] (выложить 3 значением вниз)
[5, 4] (выложить 5 значением вниз)
[4] (выложить 4 значением вниз)

Итого финальный порядок такой [4, 5, 3, 1, 2]

Wrong Directions

Фермер Джон купил программируемый трактор. Чтобы заставить трактор двигаться, он пишет строку длиной N (1 <= N <= 100,000), состоящую только из символов F, L, R. Символ 'F' заставляет трактор двигаться на единицу вперед, символы 'L' и 'R' заставляют трактор повернуться на 90 градусов влево или вправо, соответственно. Трактор начинает движение в точке (0,0) глядя на север.
ФД знает, что он ошибся ровно в одном символе. Например, он мог набрать 'F' или 'L' вместо 'R' в некотором месте. Но он не помнит точно в каком месте он ошибся.
Пожалуйста, вычислите количество различных точек на плоскости, в которых может оказаться трактор в результате выполнения этой программы (направление в конечной позиции не играет роли).
PROBLEM NAME: wrongdir
Формат входных данных
* Строка 1: Строка ФД

Формат выходных данных
* Строка 1: Количество позиций, в которых может оказаться трактор, если ФД ошибся в каком-то одном символе.
Примечание
Всего имеется 4 возможных ошибочных последовательности: FL, FR, LF, RF.
И при их выполнении трактор оказывается в точках (0,1), (0,1), (-1,0), (1,0) соответственно. Всего 3 различных точки.

Meet and Greet

Коровы очень вежливы, каждый раз при встрече они приветствуют коллегу дружеским 'moo'.
Бэси и Эльза ходят вдоль прямой вперед и назад. Начинают в точке 0 и двигаются с одинаковой скоростью. По описаниям движения каждой из коров определите количество 'moo', которыми они обменялись.
Беси и Эльза могут останавливать движение в различные точки времени, и никогда не гуляют более чем 1,000,000 единиц времени.
PROBLEM NAME: greetings
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, B (1 <= B <= 50,000) и E (1 <= E <= 50,000).
* Строки 2..1+B: Эти B строк описывают движение Беси. Каждая строка содержит положительное целое, за которым следует символ "L" или "R", обозначающий пройденное Беси расстояние влево или вправо.
* Строки 2+B..1+B+E: Эти E строк описывают движение Эльзы. Каждая строка содержит положительное целое, за которым следует символ "L" или "R", обозначающий пройденное Эльзой расстояние влево или вправо.
Формат выходных данных
* Строка 1: Одно целое число, указывающее количество 'moo', которыми обменялись две коровы. Их начальное совместное положение в точке 0, не вызывает 'moo'.
Примечание
Беси и Эльза встречаются в моменты времени 7, 9, 13

Светофор

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

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

66860

Компания “РудниК” хочет построить автономный рудодобывающий городок и ей необходимо рассчитать хватит ли её новому городу припасов на автономное существование в течении 100 месяцев. Для автономного существования городу необходимы: токарные изделия, электронные платы, бетон и еда. Изначально в городке находится по 30 единиц каждого ресурса. Каждые 10 месяцев в городок приходит по X единиц каждого ресурса. То есть при наступлении 10-го, 20-го, 30-го месяца и так далее. Чтобы автономно существовать без построек город потребляет по Y единицы каждого ресурса за месяц. Потребление ресурса происходит после поступления ресурсов с заводов и других источников. Если в какой-то месяц один из ресурсов кончится (станет равным 0 или меньше 0), то город закроют, а жителей вывезут. Рудодобывающий город начинает свой отсчёт с дня №1. Администрация города может строить здания, чтобы производить ресурсы самостоятельно:

• - завод по переработке отходов. Стоимость 8 токарных изделий, 3 электронные платы, 10 бетона. Время строительства 5 месяцев. Каждые 2 месяца завод будет выдавать 5 бетона и 2 токарных изделия. Потребляет 3 токарных изделия каждые 5 месяцев. ID завода - 1.
• - теплица. Стоимость 8 бетона и 5 токарных изделий. Время строительства 5 месяцев. Каждые 5 месяцев теплица будет приносить 7 еды. Потребляет 2 бетона каждые 10 месяцев. ID завода - 2.
• - завод по производству электроники. Стоимость 6 электронных плат, 10 токарных изделий, 10 бетона. Время строительства 10 месяцев. Каждые 10 месяцев будет выдавать по 6 электронных плат. Потребляет 2 токарных изделия каждые 18 месяцев. ID завода - 3.
• - завод по производству бетона. Стоимость 4 электронные платы, 8 токарных изделий, 8 бетона. Время строительства 8 месяцев. Каждые 8 месяцев будет выдавать по 8 бетона. Потребляет 1 токарное изделие и 1 электронную плату каждые 12 месяцев. ID завода - 4.

66402

Риэлторская фирма “КвартирКа” решила добавить в своё приложение кредитный калькулятор для своих клиентов. На время тестирования нового обновления калькулятор был сделан более простым.

Формат входных данных
На входе программа получает ряд натуральных целых чисел, разделённых переносом строки: сумма кредита (10000<=x<=999999999), процентная ставка (годовая) ( 1<=x<=100), планируемая сумма для ежемесячного погашения кредита (10000<=x<=999999999).
Формат выходных данных
На выходе программа должна выдать возможно ли выплатить кредит по представленным параметрам в виде: “True” - если возможно, “False” - если невозможно и на следующей строке количество месяцев необходимое для выплаты кредита, если кредит выплатить невозможно следует вывести ноль.

Правила расчёта кредита: процентная ставка начисляется каждые 12 (и в момент взятия кредита) месяцев на остаток по кредиту. Затем в первую очередь клиент ежемесячно гасит задолженность по процентам, а потом по самому кредиту. Если за год (12 месяцев) клиент не может погасить задолженность по процентам, то такой кредит невозможно выплатить или срок погашения кредита превышает 600 месяцев. Затем клиент начинает гасить задолженность по самому кредиту. Процент на остаток по кредиту будет начисляться каждый 12-ый месяц, выплата этих процентов будет начинаться со следующего за ним.

Пример: сумма кредита - 50.000, процентная ставка 50%, планируемая сумма погашения 10.000. В первый месяц будут начислены процента на долг, который составит 25.000. В первый месяц вся сумма пойдёт на погашения процентов 25.000-10.000. Во второй месяц, аналогично 15.000-10.000. В третий месяц 5.000 уйдёт на погашение долга по процентам и 5.000 на погашение задолженности, остаётся выплатить 45.000. В четвёртый месяц 45.000-10.000. В пятый 35.000-10.000. В шестой 25.000-10.000. В седьмой 15.000-10.000. На восьмой месяц кредит будет полностью погашен, так как не было набрано 12 месяцев проценты более не начислялись.

66149

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

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

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

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

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

65997

Город имеет форму прямоугольника с вершинами в точках (-W,-H), (-W,H), (W,H),(W,-H).
Плоскость разбита на кварталы. Квартал — это единичная клетка, вершины которой имеют целочисленные координаты. Назовем квартал городским, если все вершины квартала находятся внутри города (считается, что точка на границе принадлежит городу). Всего в городе будет 4·W·H кварталов.
Дорожная сеть состоит из N дорог (часть дорог или все проходят через город).
Дорога — это прямая линия, не параллельная осям координат.
Дорога задается двумя различными точками на ней (точки могут находиться вне города).
Для каждого квартала определим "значимость". Значимость квартала равна количеству дорог, проходящих через этот квартал. Считается, что дорога проходит через квартал, если имеет с кварталом не менее двух общих точек.
Найдите значение "значимости" для каждого квартала. Для каждой полученной "значимости" определите количество кварталов, имеющих эту значимость.

Формат входных данных
В первой строке заданы значения W, H, N (9<W,H<201, 0<N<1001)
В следующих N строках задано по четыре числа (координаты двух точек прямой, определяющих дорогу).

Формат выходных данных
В первой строке выведите число K - количество различных ненулевых значений "значимости".
В следующих K строках выведите по два числа - значение "значимости" и количество кварталов, имеющих такое значение "значимости".


Примечание к примеру

Город расположен в прямоугольнике со сторонами 8 и 6 клеток (всего 48 кварталов)
Через город проходят 4 дороги AB, CD, EF, GH
Значимость 1 будет у 24 кварталов (коричневый цвет на рисунке)
Значимость 2 будет у 5 кварталов (зеленый цвет на рисунке)
Значимость 4 будет у 1 кварталов (красный цвет на рисунке)
18 кварталов будут иметь значимость равную 0 (на печать не выводиться)

65982

Электронная схема состоит из элементов И и НЕ.
Элемент НЕ имеет один вход и один выход. Принцип его работы следующий: если на входе появится сигнал 0, то через 1 мс на выходе установится сигнал 1, а если на входе 1, то через 1 мс на выходе установится сигнал 0.
Элемент И имеет два входа и один выход. Если на обоих его входах появится сигнал 1, то через 1 мс на выходе установится сигнал 1. Если хотя бы на один из входов поступает 0, то через 1 мс на выходе устанавливается сигнал 0.
Все точки подсоединения элементов пронумерованы. Если в точку поступает сигнал с выходов нескольких элементов, то в этой точке сигнал равен 0 тогда, когда со всех выходов поступает сигнал 0. Если с одного или нескольких выходов, подсоединенных в одной точке, поступает сигнал 1, то в этой точке устанавливается сигнал 1. В последних двух случаях сигнал устанавливается мгновенно (без задержки).
Известно состояние (сигнал 0 или 1) каждой точки в момент включения схемы. Необходимо выдать состояние некоторой указанной точки К в течение первых T мс с момента включения схемы.
В точках, которые соединены только с входами элементов, сигнал остается неизменным с момента включения схемы до окончания ее работы.
Формат ввода
На вход программе в первой строке подаётся натуральное число N. Далее идет N строк, каждая из которых содержит несколько целых десятичных чисел, отделенных друг от друга одним или несколькими пробелами. Первое число в строке показывает, что именно описывают оставшиеся числа данной строки:
0 - описание точки соединения;
   0 m n - точка с номером m имеет в момент включения состояние n (0 или 1)
1 - описание элемента НЕ;
   1 x y - элемент НЕ, вход которого соединен с точкой под номером x, а выход - с точкой под номером y
2 - описание элемента И;
   2 x y z - элемент И, один вход которого соединен с точкой под номером x, второй вход соединен с точкой под номером y, а выход - с точкой под номером z
3 - описание задания.
   3 K T - необходимо выдать состояние точки K в течение первых T мс с момента включения схемы.
Формат вывода
T строк: первая строка - состояние точки K в первую мс, вторая строка - состояние точки K во вторую мс, и так далее до T мс.

Пример
Пусть имеется схема, приведенная на рисунке. Необходимо выдать состояние точки 3 в течение 5 мс с момента включения схемы.

65819

Находясь в агрессивной среде аппарат, снабженный целым комплексом датчиков, мониторит сразу несколько параметров. Необходимо написать программу анализа для параметра F. Этот параметр принимает целые значения. Задан диапазон допустимых значений [X; Y] (границы отрезка тоже являются допустимыми значениями). Каждую минут снимаются показания с датчика F. После выключения оборудования датчик показывает 0. Это значение в серию измерений уже не включается. Необходимо посчитать наибольшее отклонение от допустимых значений и сколько раз за время наблюдения оно было зафиксировано.

Формат входных данных
На первых двух строчках вводятся два целых числа X и Y (X < Y), которые задают диапазон допустимых значений.
На последующих строчках вводятся целые числа (по одному в каждой строке) – показания параметра F, передаваемые аппаратом. Последнее значение 0 – признак выключения аппарата – это значение в показания НЕ включается.
Все числа по модулю не превосходят 1 000.
Гарантируется, что хотя бы один выход из допустимого диапазона значений был.
Формат выходных данных
Два целых числа в одной строке через пробел: максимальное отклонение и количество отклонений на такое значение за время наблюдения.

Примечание
В данном примере 11 измерений. Максимальное отклонение 2 от заданного допустимого диапазона [-4; 11] будет достигнуто 3 раза на значениях -6, 13 и 13
|-6 – (-4)| = |13 – 11| = 2

65815

В школе №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), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.

Примечание:

2026

Новая татарская игра <<2026>> ведется на прямоугольной клетчатой доске, состоящей из \(m\) строк и \(n\) столбцов. Доска разбита на \(m \times n\) единичных клеток размером \(1 \times 1\). На некоторых клетках стоят квадратные фишки размером \(1 \times 1\), на каждой фишке написана одна из \(26\) английских букв.

С фишками производятся \(q\) операций. Каждая операция состоит в перемещении всех фишек до упора в одном из четырех направлений. Таким образом, последовательность операций задается строкой \(s\) длины \(q\), состоящей из символов, соответствующих направлениям: <<L>> — влево, <<R>> — вправо, <<U>> — вверх и <<D>> — вниз.

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

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

Формат входных данных

Каждый тест состоит из нескольких наборов входных данных. В первой строке теста задано целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 200\,000\)). Далее следуют описания наборов входных данных. Каждый набор входных данных описывается следующим образом:

В первой строке набора заданы целые числа \(m\) и \(n\) — размеры доски (\(1 \le m, n \le 10^6\), \(1 \le m\times n \le 10^6\)).

В следующих \(m\) строках задано изначальное расположение фишек на доске.

В \(i\)-й строке (\(1 \le i \le m\)) находится строка \(a_{i1}a_{i2}\ldots a_{in}\) длины \(n\), задающая \(i\)-ю строку доски. Каждый символ \(a_{ij}\) является либо строчной буквой английского алфавита от <<a>> до <<z>>, либо точкой <<.>>. Если \(a_{ij}=\mbox{<<.>>}\), то клетка в \(i\)-й строке и \(j\)-м столбце является пустой, иначе в ней находится фишка, на которой написана буква \(a_{ij}\).

В последней строке заданы \(q\) символов \(s_1s_2\ldots s_q\) без пробелов, задающие последовательность операций (\(1 \le q \le 10^6\)). Каждый символ \(s_i\) является одним из символов <<L>>, <<R>>, <<U>> или <<D>>.

Сумма значений \(m \times n\) по всем наборам входных данных не превышает \(2\cdot 10^6\). Сумма значений \(q\) по всем наборам входных данных не превышает \(2\cdot 10^6\).

Формат выходных данных
Для каждого набора входных данных выведите итоговое расположение фишек на доске после выполнения всех операций в том же формате, что и во входных данных.

Обозначим через \(\sum mnq\) сумму \(mnq\) по всем наборам входных данных.

Обозначим через \(\sum mq\) сумму \(mq\) по всем наборам входных данных.

Назовем расположение фишек лестницей, если \(m=n\), \(a_{ij}={<<\texttt{.}>>}\) для всех \(1 \le i \le j \le n\) и \(a_{ij}\ne{<<\texttt{.}>>}\) для всех \(1 \le j < i \le n\). Иными словами, все фишки находятся на клетках ниже главной диагонали доски, и на каждой клетке ниже главной диагонали есть фишка.

Пояснения к примерам
В первом наборе входных данных из примера доска изначально выглядит так:

Первая операция сдвигает все фишки влево, так как \(s_1={<<\texttt{L}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Вторая операция сдвигает все фишки вправо, так как \(s_2={<<\texttt{R}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Третья и последняя операция сдвигает все фишки наверх, так как \(s_3={<<\texttt{U}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Фестиваль чисел

В городе Летовецк  "Фестиваль Чисел" отмечается всегда в день с магической датой. Дата называется магической, если день, номер месяца и две последние цифры года совпадают. Например, 01.01.01 - магическая дата. 
По текущей дате, записанной в формате дд.мм.гг определите дату, когда будет отмечатся ближайший "Фестиваль чисел". То есть первую магическую дату, которая была бы не ранее текущей.

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

Дано дерево

Дано бесконечное бинарное дерево. У дерева есть корень и бесконечное число вершин, у каждой вершины есть левый и правый сын, у всех вершин кроме корня есть отец.

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат выходных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

Автоматические друзья

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

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

Требуется написать программу, которая по данным \(n\) тройкам \((a_i, b_i, c_i)\) значений характеристик каждого из пользователей определяет количество пар потенциальных друзей, то есть таких пар индексов \(i < j\), что из трёх равенств \(a_i = a_j\), \(b_i = b_j\), \(c_i = c_j\) выполняется ровно одно.

Входные данные
Первая строка входных данных содержит число \(n\) — количество пользователей (1 ≤ n ≤ 100 000). Каждая из последующих \(n\) строк содержит три целых положительных числа \(a_i\), \(b_i\) и \(c_i\) — значения характеристик \(i\)-го пользователя (1 ≤ a_i , b_i , c_i ≤ 100)

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

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

Поезда

В связи с увеличившимся количеством аварий на железной дороге, руководство дороги решило изменить график движения поездов. Анализ состояния полотна дороги показал, что оптимальным является следующий график движения: сначала T₁ минуту поезд идет со скоростью V₁ метр в минуту, потом T₂ минуты со скоростью V₂ метра в минуту, ..., наконец, T_N минут со скоростью V_N метрв в минуту. При этом на любом из этих участков поезд может стоять (V_i = 0).

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

Входные данные
Первые две строки входных данных содержат числа L и N (100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000). Далее идет N строк, задающих график движения поезда, каждая строка содержит пару чисел T_i и V_i (1 ≤ T_i ≤ 1000, 0 ≤ V_i ≤ 1000).

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

Д-44

При решении задач баллистики следует учитывать сопротивление воздуха. Пусть сила сопротивления воздуха пропорциональна квадрату модуля скорости движения снаряда и направлена противоположно скорости. Считая коэффициент пропорциональности силы сопротивления воздуха квадрату скорости постоянной величиной, рассчитать дальность полёта снаряда (с точностью до 10 м) при стрельбе из 85-миллиметровой пушки Д-44 под заданным углом к горизонту, если масса снаряда равна 9.6 кг, а начальная скорость - 800 м/с. Известно также, что при стрельбе под углом 45 градусов дальность стрельбы составляет 15 650 м. Ускорение свободного падения считать равным 9.8 м/с².

Ограничения: угол от 5 до 85 градусов.

Входные данные
В первой строке находится единственное вещественное число - угол в градусах.

Выходные данные
Вывести одно целое число - дальность в метрах.

Двойная решетка

Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x₁ y₁ и x₂ y₂. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет Dx по горизонтали и Dy по вертикали. В результате наложения образуется новая, "составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.

Ограничения: 1 <= x₁, y₁, x₂, y₂ <= 100, 0 <= D_x < x₁, 0 <= D_y < y₁, все числа целые.

Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, D_x, D_y, разделённые пробелами.

Выходные данные
В первой строке вывести N - количество получившихся площадей, в следующих N строках - сами площади.

Игра "черный ящик"

В игру «черный ящик» играют с помощью квадратного черного ящика, который располагается на плоском столе. На каждой из сторон ящика есть n отверстий (всего 4n отверстий), в которые можно вбрасывать шар. Вброшенный шар через некоторое время вылетит наружу через одно из 4n отверстий, возможно, через то же отверстие, в которое он был вброшен.



Содержимое черного ящика можно рассматривать в виде сетки размером n x n. Отверстия в сторонах ящика – это начала и концы строк и столбцов сетки. Каждая клетка сетки либо пустая, либо занята отражателем. Отражатель – это устройство, которое изменяет направление движения шара на 90 градусов. Рассмотрим пример ящика размером 5x 5.

Вброшенный шар движется по прямой, пока не попадает в отражатель или не вылетит наружу. Когда шар попадает в отражатель, шар меняет направление своего движения, а отражатель меняет свое положение (под словом «меняет» подразумевается поворот на 90 градусов). На примере показаны действия отражателя.



a) Первый шар вброшен через отверстие. Он попал в отражатель и изменил направление движения.

b) После попадания первого шара отражатель изменил свое положение. Новый шар вбросили в то же отверстие, он попал в тот же отражатель, и отразился в направлении, противоположном направлению первого шара после отражения.

c) Отражатель изменил свое положение. После каждого попадания положение отражателя изменяется.


Когда шар попадает в отражатель, раздается звуковой сигнал. Количество отражений шара можно узнать, посчитав количество сигналов. Можно доказать, что шар всегда вылетает из ящика. У ящика есть одна кнопка, которая приводит его в исходное положение, и другая кнопка, которая меняет положение всех отражателей на противоположное.

ЗАДАНИЕ
Вам будет предоставлен интерфейс к 15 черным ящикам с помощью библиотеки функций Pascal или C/C++. Вы должны определить содержимое каждого из ящиков как можно точнее и отправить на проверку файлы, описывающие каждый ящик. Интерфейс также предоставляет возможность создания собственных ящиков для тестирования.

ОГРАНИЧЕНИЯ
1 ≤ n ≤ 30

 

ВЫВОД