Инопланетяне с планеты Пандора продолжают изучать жителей Земли. В этот раз они хотят проверить, влияет ли цвет глаз землянина на его зрение. Запланированное исследование состоит из серии экспериментов, для каждого из которых требуется двое землян с глазами одинакового цвета.
В поисках материала для исследования пандорианцы на своей летающей научной базе прибыли на обыкновенный курортный пляж, до отказа забитый греющимися на солнце туристами. Туристы занимают все доступное место на пляже, образуя, таким образом, прямоугольник размером N × M человек. По пляжу они не перемещаются. То есть, каждый турист однозначно задается своими координатами в этом прямоугольнике: номером ряда, в котором он лежит, и номером в этом ряду.
Научная база пандорианцев оборудована двумя специальными антигравитационными лучами, предназначенными для подъема грузов на базу и для их спуска на поверхность близлежащей планеты. Чтобы база не потеряла равновесия, оба луча следует использовать одновременно. Таким образом, пандорианцы могут либо поднять двух произвольных туристов с пляжа на базу, либо опустить двух туристов обратно на пляж. Исследование должно проходить следующим образом. Оператор антигравитационного луча выбирает на пляже двоих туристов и поднимает их на базу. После этого специальная аппаратура определяет цвет глаз каждого из них. Если полученные цвета совпадают, ученые уводят эту пару туристов для проведения очередного эксперимента, и на пляж они больше не возвращаются. Если же они не совпадают, оператор опускает этих туристов обратно на их места на пляже, после чего процесс повторяется.
Обычно такие исследования не вызывали никаких трудностей, но в этот раз ученые заявили оператору, что после завершения исследования на пляже не должно остаться ни одного землянина. Помогите оператору выбирать туристов в таком порядке, чтобы это требование оказалось выполненным. Гарантируется, что это возможно, то есть туристов можно разбить на пары так, чтобы цвет глаз в каждой паре совпадал.
Это интерактивная задача. В процессе тестирования программа-решение будет взаимодействовать с использованием стандартных потоков ввода/вывода с программой-интерактором, сообщающей в ответ на координаты двух очередных выбранных туристов цвета их глаз.
В первой строке заданы два числа: N и M — размеры прямоугольника, который туристы образуют своими телами, где N — это количество рядов, а M — количество человек в одном ряду пляжа. Гарантируется, что туристов на пляже четное число.
Затем программа-решение начинает взаимодействие с программой-интерактором в соответствии со следующим протоколом:
Тесты к этой задаче состоят из пяти групп.
Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
Правильный пример на картинке.
После своего первого контакта с землянами обитатели планеты Пандора решили всё-таки перенять часть земных технологий. В частности, они предприняли попытку приспособить к особенностям своей планеты систему железнодорожного сообщения.
Построенная пандорианцами железная дорога представляет собой прямой отрезок, проходящий в непосредственной близости от N красивейших водопадов. Паровозик, который планируется запустить по этой дороге, будет без остановок проезжать весь маршрут, преодолевая участки между водопадами за строго определённое время.
Так как жители Пандоры очень трепетно относятся к красотам своей природы, они не хотят упускать ни малейшей возможности полюбоваться водопадами, искрящимися в дневном свете. Грамотно составлять расписания пандорианцы ещё не научились, и теперь они обратились за помощью к вам, участникам олимпиады по программированию.
Помогите обитателям Пандоры определить, в какое время дня паровозик должен проехать рядом с первым водопадом, чтобы пассажиры смогли увидеть все водопады на пути в дневное время, при этом не обязательно в один и тот же день. Водопад виден лишь в момент проезда паровозика мимо него, но, как известно, пандорианские водопады настолько впечатляющие, что и за мгновение можно сполна насладиться любым из них.
В первой строке через пробел вводятся два натуральных числа: количество часов в одних сутках ( H ) и минут в одном часу ( M ) на Пандоре ( 1 ≤ H , M ≤ 500 ).
Следующая строка содержит четыре целых числа, описывающих время начала ( H s , M s ) и конца ( H f , M f ) светового дня ( 0 ≤ H s , H f < H ; 0 ≤ M s , M f < M ). При этом либо H s < H f , либо H s = H f и M s < M f (гарантируется, что день начинается раньше, чем заканчивается). Если паровозик проезжает мимо водопада ровно в H s часов M s минут или ровно в H f часов M f минут, то считается, что он проехал мимо водопада днём.
Третья строка содержит одно натуральное число N — количество водопадов, рядом с которыми проезжает паровозик ( 1 ≤ N ≤ 100 000 ).
В следующих N - 1 строках вводятся по 2 целых числа H i и M i , описывающих продолжительность временных интервалов для проезда между соседними водопадами: H 1 , M 1 — время в пути между первым и вторым водопадами, H 2 , M 2 — между вторым и третьим и так далее. Гарантируется, что время, затрачиваемое на дорогу между любыми двумя соседними водопадами, строго положительно, не превосходит одних пандорианских суток и записано корректно: 0 ≤ H i ≤ H , 0 ≤ M i < M .
Если составить подходящее расписание невозможно, то в качестве ответа выведите одно слово « Impossible » (без кавычек). Иначе выведите два числа H 0 и M 0 , разделённые пробелом, описывающие любое подходящее время проезда паровозика рядом с первым водопадом.
Тесты к этой задаче состоят из четырех групп.
Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
24 60 8 0 22 0 6 6 0 21 0 19 0 12 0 10 0
12 0
24 60 8 17 20 10 2 11 59
Impossible
Петя и Вася — одноклассники и лучшие друзья, поэтому они во всём помогают друг другу. Завтра у них контрольная по математике, и учитель подготовил целых K вариантов заданий.
В классе стоит один ряд парт, за каждой из них (кроме, возможно, последней) на контрольной будут сидеть ровно два ученика. Ученики знают, что варианты будут раздаваться строго по порядку: правый относительно учителя ученик первой парты получит вариант 1, левый — вариант 2, правый ученик второй парты получит вариант 3 (если число вариантов больше двух) и т.д. Так как K может быть меньше чем число учеников N, то после варианта K снова выдаётся вариант 1. На последней парте в случае нечётного числа учеников используется только место 1.
Петя самым первым вошёл в класс и сел на своё любимое место. Вася вошёл следом и хочет получить такой же вариант, что и Петя, при этом сидя к нему как можно ближе. То есть между ними должно оказаться как можно меньше парт, а при наличии двух таких мест с равным расстоянием от Пети Вася сядет позади Пети, а не перед ним. Напишите программу, которая подскажет Васе, какой ряд и какое место (справа или слева от учителя) ему следует выбрать. Если же один и тот же вариант Вася с Петей писать не смогут, то выдайте одно число - 1.
В первой строке входных данных находится количество учеников в классе 2 ≤ N ≤ 109. Во второй строке — количество подготовленных для контрольной вариантов заданий 2 ≤ K ≤ N. В третьей строке — номер ряда, на который уже сел Петя, в четвёртой — цифра 1, если он сел на правое место, и 2, если на левое.
Если Вася никак не сможет писать тот же вариант, что и Петя, то выведите - 1. Если решение существует, то выведите два числа — номер ряда, на который следует сесть Васе, и 1, если ему надо сесть на правое место, или 2, если на левое. Разрешается использовать только первые N мест в порядке раздачи вариантов.
25
2
1
2
2 2
25
13
7
1
-1
В первом примере вариантов 2, поэтому наилучшее место для Васи находится сразу за Петей. Во втором примере Петя будет единственным, кто получит вариант 13.
Каждый тест в задаче оценивается отдельно. Программа, выдающая правильный ответ только на тесты из условия и тесты с ответом - 1, не оценивается. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. N ≤ 100. Оценивается из 52 баллов.
Подзадача 2. N ≤ 109. Оценивается из 48 баллов.
На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое.
Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "abcdefghijklmnopqrstuvwxyz" равна 25, а строки "abdc" — только 1.
Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и поможете ему с ней справиться.
Первая строка ввода содержит единственное целое число N — количество различных букв в наборе (1 ≤ N ≤ 26). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита.
Следующие N строк содержат целые положительные числа ci — количество букв соответствующего типа (1 ≤ ci ≤ 109). Таким образом, первое число означает количество букв "a", второе число задаёт количество букв "b" и так далее.
Выведите единственное целое число — максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек.
3
1
1
1
2
2
3
4
3
В первом тесте имеется по одной дощечке с каждой из 3 различных букв. Ответ 2 достигается на строке "abc"
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. Во всех тестах данной группы ci ≤ 100. Данная подзадача оценивается из 40 баллов.
Подзадача 2. Во всех тестах данной группы ci ≤ 1 000 000. Данная подзадача оценивается из 30 баллов.
Подзадача 3. Во всех тестах данной группы ci ≤ 109. Данная подзадача оценивается из 30 баллов.
Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых.
Изначально в шляпу помещают некоторое количество бумажек с написанными на них словами. После этого команды из двух человек по очереди и в случайном порядке начинают отгадывать слова - один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то бумажка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы.
Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M, и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд.
В первой строке дано количество команд N и количество попыток отгадать слова M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000). В следующих M строках сначала указывается номер ni команды, пытавшейся отгадать слово, а через пробел дано слово wi, написанное на бумажке. Номера команд лежат в диапазоне от 1 до N. Все слова wi состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв.
Выведите в одну строку N чисел, i-ое число должно равняться количеству слов, отгаданному i-ой командой.
2 3
1 hat
1 shirt
2 hat
1 1
3 2
1 mom
3 dad
1 0 1
В первом примере первая команда отгадала слово shirt, а вторая слово hat.
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Каждое слово встречается только один раз. Оценивается из 20 баллов.
Подзадача 2. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Оценивается из 30 баллов.
Подзадача 3. 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000. Оценивается из 50 баллов.