Задача на реализацию

ID 38282. Сборная Юпитера

Каждый год в одном из уголков нашей вселенной проходят Интеллектуальные Олимпийские Игры. В этом году честь проводить это масштабное мероприятие выпала планете Юпитер. Вам предстоит отобрать две команды на Игры из имеющихся n кандидатов в сборную.

Все кандидаты являются школьниками, каждый кандидат учится в определенном классе. Как и на Земле, на Юпитере 11 классов, пронумерованных от 1 до 11. На Игры отбирается две команды по результатам отборочных соревнований. На соревнованиях проводится пять отборочных туров. По итогам каждого тура каждый школьник может набрать от 0 до 300 баллов, чем больше, тем лучше.

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

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

Входные данные
Первая строка входных данных содержит единственное число n — количество кандидатов в сборную Юпитера ( 8 ≤ n ≤ 500 ).

Следующие n строк содержат информацию о кандидатах. Каждая строка содержит 6 целых чисел — номер класса, в котором учится очередной кандидат, и его результаты на отборочных турах.

Номер класса является числом от 1 до 11, а результат на каждом туре — числом от 0 до 300.

Гарантируется, что все участники имеют различные суммарные баллы.

Гарантируется, что есть хотя бы 8 кандидатов, обучающихся не в 11 классе.

Выходные данные
Выведите две строки.

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

Вторая строка должна описывать вторую команду Юпитера в аналогичном формате.
 

Примеры

ID 38623. Набор для торта

Ушан с планеты Блук открыл пекарню. В его пекарне продается N видов тортов. Каждый вид торта имеет три параметра: «красота», «вкус» и «популярность». I-й вид торта имеет красоту xi, вкус yi и популярность zi. Эти значения могут быть нулевыми или отрицательными.
Громозека решил, что купит М кусочков торта. Он выбирает набор следующим образом:
- Нельзя использовать два и более куска одного и того же вида торта.
- При указанном выше условии выбирается набор тортов, который максимизирует (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности).
Найдите максимально возможное значение (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности) для набора тортов, который выберет Громозека.

Входные данные
В первой строке через пробел записаны два целых числа N (1<=N<=1000) и M (0<=M<=N). В следующих N строках записано по  три целых числа xi, yi и zi (-10⁹<=xi, yi, zi <=10⁹, 1<=i<=N).

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

Примеры

ID 38873. Комната

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

Входные данные
На вход подаётся три целых числа: w, l и h — длина, ширина и высота комнаты, каждое
на отдельной строке (1000 ≤ w, l, h ≤ 10 000).

Выходные данные
Если комната является хорошей, выведите «good», иначе выведите «bad».
 

Примеры

ID 39062. Сломанный принтер

Сломанный цветной принтер, печатая цифры, закрашивает все замкнутые области в красный цвет.  Например, в цифрах 0, 4, 6, 9 одна замкнутая область. В цифре 8 - 2 замкнутых области.  В других цифрах нет замкнутых областей, которые закрашиваются. В принтере красной краски осталось на покраску h замкнутых областей.  Найдите минимальное неотрицательное число, напечатав которое в принтере закончится красная краска. Число не должно содержать ведущих нулей.  Если в принтере отсутствует красная краска, то он не может напечатать цифру с замкнутой областью.

Примеры

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

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

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

Примеры

ID 39397. Громозека и Алиса - 2

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

Входные данные
В первой строке задан, момент времени, в который Громозека и Алиса вошли в первое кафе. Формат времени: часы (число от 00 до 23), далее идет двоеточие, затем минуты (число от 00 до 59). Строка времени записана без пробелов.
Во второй строке записано натуральное число N (2 <= N <= 1000) - количество посещенных кафе (включая кафе из которого они вышли в начальный момент времени и последнее кафе). В третьей строке записано N-1 число: первое показывает время в минутах от входа в первое кафе до входа во второе, второе - время от входа во второе кафе до входа в третье и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные
Выведите для каждого кафе время входа Алисы и Громозеки. Формат времени должен быть такой же, как и во входных данных.
 

Примеры

ID 27222. Where's Bessie?

ID 43349. Секретная последовательность

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

• первым числом слева записано число a1;
•  первым числом справа записано число a2;
• вторым числом слева (после a1) записано число a3;
• вторым числом справа (то есть перед числом a2) записано число a4;
• все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.

Примеры

ID 43351. Книги Томми

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге ai страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

Томми читает уже m дней подряд. Книги он читает строго по порядку, начиная с книги с номером 1.  Каждый день он записывает на доску общее число страниц, которые прочитал к текущему дню.

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= ak), на которой остановился Томми в текущий день.

Примеры

ID 43474. Громозека и валерьянка

Громозека очень любит валерьянку. На его родной планете Чумароза можно купить за k чумриков (местная валюта) первую упаковку валерьянки, за 2·k чумриков - вторую и так далее (иными словами, за i-ю упаковку надо заплатить i·k чумриков). Громозека хочет купить w упаковок валерьянки.  У него есть n чумриков. Сколько чумриков ему придется взять в кредит в чумарозском банке, чтобы купить w упаковок валерьянки?

В первой строке записано три положительных целых числа k, n, w (1  <=  k, w  <=  1000, 0 <= n <= 10⁹), стоимость первой упаковки, изначальное количество чумарозиков у Громозеки и количество упаковок валерьянки, которые он хочет купить.

Выведите единственное целое число - количество чумарозиков, которое Громозеке необходимо взять в кредит в банке. Если брать кредит не надо, выведите 0.

Примеры

ID 43532. Книжки с полки

Петя обладает обширной библиотекой книг. Сейчас он стоит возле полки с приключенческими рассказами. На ней расположены n книг. Все книги на полке у Пети всегда пронумерованы слева направо. Книга с номером i имеет ai страниц. На полке, возле которой сейчас стоит Петя, количество страниц в каждой книге различно.

Особенность полок в библиотеке Пети такова, что он может брать только крайнюю книгу с полки (то есть либо самую левую, либо самую правую).

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

Входные данные
В первой строке записано одно целое число n (2 <= n <= 100) - количество книг на полке. Во второй строке находится n целых различных чисел a1, a2, ..., an (1 <= ai <= 106) - количество страниц в книге.

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

Примеры

5
1 5 4 3 2

2

8
2 1 3 4 5 6 8 7

4

ID 43718. Мишины кубики

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.


Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры

ID 21821. Крестики-нолики

...
000
XXX
...
...

..0.
.XX0
.0X.
....

......
.XXX..
.0000.
..X...
......

ID 21889. Чемпионат по поиску в сети Меганет

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

Имя сервера представляет собой строку, содержащую от одной до пяти частей включительно. Каждая часть представляет собой непустую строку, состоящую из строчных букв латинского алфавита. Части разделены точкой. Примеры корректных имен сервера: «a», «ab.cd», «abacaba», «a.b.c.d.e».

Имя раздела представляет собой строку, которая может быть либо пустой, либо содержать от одной до пяти частей включительно. Каждая часть начинается с символа «/», после которого следует одна или несколько строчных латинских букв. Примеры корректных имен разделов: «», «/a», «/aba», «/a/b/c/d/e». Адрес формируется приписыванием имени раздела в конец имени сервера. Например, корректными адресами являются строки: «a», «aba/d/f/g/h», «a.b», «aba.caba/def/g», «c.d.e.f.g/a/b/c/d/e».

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

Фильтр сервера состоит из имени сервера, перед которым может также идти строка «*.». Если фильтр сервера представляет собой только имя сервера, то этому фильтру соответствует только сервер, имеющий точно такое же имя. Если фильтр сервера представляет собой строку «*.S », где S — имя сервера, то ему соответствуют сервера, удалением нуля или более начальных частей от имени которых можно получить строку S.

Аналогично, фильтр раздела представляет собой имя раздела, после которого может идти строка «/*». Фильтру раздела, который представляет собой просто имя раздела R, соответствуют только разделы, в точности совпадающие с R. Если фильтр раздела представляет собой строку «R/*», то ему соответствуют все разделы, удалением от имен которых нуля или более конечных частей можно получить строку R. Адрес соответствует фильтру, если его имя сервера соответствует фильтру сервера, а его имя раздела соответствует фильтру раздела.

Примеры фильтров и соответствующих им адресов приведены в таблице ниже.

ID 21903. Магические порталы

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

Из-за свойств магии, определяющей работу порталов, каждый портал можно использовать только в одну сторону. Для каждой пары городов A и B известно, можно ли воспользоваться порталом для перемещения напрямую из A в B или из B в A.

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

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

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

Для получения этой информации король планирует запросить в министерстве транспорта соответствующий отчет. Король может запросить либо частичный, либо полный отчет. Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1, для полного отчета L = 1.

Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B, для которых выполняются следующие условия:
- исходно магический портал позволяет перемещаться напрямую из города A в город B;
- если изменить направление перемещения этого магического портала на противоположное, чтобы он позволял напрямую перемещаться из города B в город A, то количество совершенных городов в королевстве станет равным m.

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

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n — количество городов в королевстве (2 ≤ n ≤ 2000) и p, равное либо 0, если требуется вывести частичный отчет, либо 1, если требуется вывести полный отчет. Последующие n строк содержат по n символов, каждый из которых может быть «+», «–» или «.», и i-я из этих строк описывает магические порталы, соединяющие i-й город с другими городами.
В i-й строке j-й символ равен «+», если магический портал позволяет напрямую перемещаться из i-го города в j-й, равен «–», если магический портал позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.
Формат выходного файла
Первая строка выходного файла должна содержать одно целое число k — количество совершенных городов в королевстве.
Если требуется частичный отчет (p = 0), то вторая строка выходного файла должна содержать (n – k) целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным (k + i). Если при этом k = n, то вторая строка может отсутствовать, либо быть пустой.
Если требуется полный отчет (p = 1), то вторая строка должна содержать n целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным i.

Пример:

ID 21954. Ремонт асфальта

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

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице М. А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до N и собрали информацию о типе асфальта на каждом из участков — числа t1, t2, . . . , tN (ti — номер типа асфальта на i-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна 3, потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную 1.

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

Формат входных данных
Первая строка входного файла содержит единственное натуральное число N — количество участ- ков дороги (1 <= N <= 100 000). Следующая строка содержит N целых чисел t1, t2, . . . , tN — исходные типы асфальта участков дороги (|ti | <= 109 ). Третья строка содержит единственное натуральное число Q — количество сообщений от жителей об обновлении дорожного покрытия (1 <= Q <= 100 000). Каждая из следующих Q строк содержит очередное сообщение. i-е сообщение представляет собой пару целых чисел pi , ci — номер ремонтируемого участка дороги и новый номер типа асфальта на этом участке (1 <= pi <= N, |ci | <= 109 ). Участки дороги нумеруются от 1 до N в порядке задания их исходного типа асфальта во второй строке входного файла.

Формат выходных данных
Выведите Q строк. i-я строка (1 <= i <= Q) должна содержать единственное целое число — величину непроходимости улицы после первых i обновлений дорожного покрытия.

Примеры

ID 27119. Kotlin Island

There is an urban myth that Peter the Great wanted to make a rectangular channel-grid engineering masterpiece not only from Vasilyevskiy island, but also from Kotlin island (where the town of Kronstadt is located nowadays).

The following mathematical model was (allegedly) presented to the tsar. The island is considered a rectangular grid h cells high and w cells wide. Each cell is dry land initially but can become water.

Technologies of those days allowed engineers to dig a channel across the entire island. In that case an entire row or an entire column of cells became water. If some of these cells already were water, their status did not change.
Your task is to propose a plan of the island which has exactly n connected components of dry land cells.

Input
The only line of the input contains three integers h, w, and n — grid’s height, width and the desired number of connected components (1 ≤ h, w ≤ 100; 1 ≤ n ≤ 10⁹ )

Output
If there is no valid plan containing n connected components, output a single word “Impossible”. Otherwise output h lines of length w depicting the plan. Dot (‘.’) represents a dry land cell, hash (‘#’) represents a water cell.
 

ID 27114. СКОБКИ

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

ID 27098. Шифрование

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

ID 27072. КОЛОНИЗАЦИЯ МАРСА

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

Формат входных данных
Задается одно число N ( 1<= N <= 10⁹ ) – необходимое количество воды.

Формат выходных данных
Одно целое число M – минимально необходимое количество суток.
 

ID 24760. Смех, да и только!

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

Лиса считает, что смех — это последовательность чередующихся букв «a» и «h». Так например, «ahahaha», «hah» и «a» являются смехом, а «abacaba» и «hh» — нет.

Колобок разговаривает очень быстро, поэтому все его слова сливаются в одно большое. Для исследования Лиса хочет понять, как долго он может смеяться. У неё есть строка — запись разговора Колобка. Лиса хочет узнать наибольшую длину смеха в этом разговоре.

Лиса просит вас помочь ей с этой задачей.

Формат входного файла
В первой строке входного файла находится одно натуральное число n (1 ≤ n ≤ 105 ) — длина строки с разговором колобка. Во второй строке находится строка из строчных латинских букв длины n — запись разговора колобка.

Формат выходного файла
В выходной файл выведите одно число — наибольшую длину смеха в разговоре Колобка
 

ID 23376. Британские ученые (В, А', А)

ID 23372. Прямоугольное поле чудес (В, А',A)

ID 23370. Опять двойка (В, В')

ID 23369. Овечка Толя (C, B')

ID 23368. Организация конференции (С, B')

ID 27217. COWBASIC

x = 1
10 MOO {
  x = ( x ) + ( x )
}
RETURN x

n = 1
nsq = 1
100000 MOO {
  100000 MOO {
    nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) )
    n = ( n ) + ( 1 )
  }
}
RETURN nsq

ID 27223. The Lost Cow

ID 29547. Circular Barn

ID 48046. Телефонный справочник

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

Формат входных данных
В единственной строке содержится одно слово, состоящее из строчных латинских букв от "a" до "z" (2 ≤ n ≤ 10⁶) 

Формат выходных данных
Выведите одно слово - новое название компании. Если название не~изменилось, выведите изначальное название.
 

ID 44509. Башни 2.0

В компьютерной игре есть n башен, высота i-й башни равна ai метров. Определим расстояние между двумя башнями с индексами i и j как |i−j|. Разрешается прыгнуть с i-й башни на j-ю башню тогда и только тогда, когда не существует такого индекса 1 <= k <= n, такого, что расстояние от i-й до j-й башни не меньше расстояния от i-й башни до k-й башни, и k-я башня имеет большую высоту, чем j-я. Башня j достижима из башни i если существует последовательность корректных прыжков, которая начинается в i-й башне и заканчивается в j-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.


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

Первая строка входных данных содержит одно целое число n (1 <= n <= 500000) - количество башен.

Вторая строка входных данных содержит n чисел a1, a2, ..., an (1 <= an <= 10⁹) - высоты башен.

В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.

Во втором примере из 1-й и из 2-й башни достижимы башни 1,2,3,4,5. Из 3-й башни достижимы башни 3,4,5. Из 4-й и 5-й башни достижимы башни 4,5. Из 6-й башни достижимы башни 4,5,6. Из 7-й башни достижимы башни 4,5,6,7.

Примеры

5
7 6 3 4 10

2 3 4 2 1 

7
1 1 1 2 2 1 1

5 5 3 2 2 3 4 

ID 48934. Пират Серёжа

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Головоломка представляет из себя таблицу из \(n\) строк и \(m\) столбцов, в ячейках которой записаны числа от \(1\) до \(n \cdot m\) по одному разу.

Чтобы собрать головоломку, нужно выбрать последовательность клеток таблицы, в которой любые две подряд идущие клетки соседние по стороне в таблице. Последовательность может иметь произвольную длину, и каждая клетка может встречаться в последовательности произвольное число раз. Для клетки со значением \(i\) рассмотрим позицию \(t_i\) — позицию первого вхождения клетки с таким значением в последовательность. Последовательность решит головоломку, если каждая клетка таблицы встречается в ней, и \(t_1 < t_2 < \dots < t_{nm}\). Другими словами, последовательность должна в первый раз посетить клетку со значением \(x\) до клетки со значением \(x + 1\) для всех \(x\).

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

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

За одно действие Сережа может выбрать две произвольных клетки (не обязательно соседние по стороне) и поменять числа, записанные в них. Он хотел бы знать минимальное число действий, которое потребуется, чтобы головоломка стала решаемой, но очень нетерпелив. Поэтому найдите, равняется ли минимальное число действий \(0\), \(1\), или же не менее \(2\). В случае, когда потребуется ровно \(1\) действие, найдите также количество подходящих пар клеток для обмена чисел.

Формат входных данных
В первой строке вводятся два целых положительных числа \(n, m\) (\(1 \leq n \cdot m \leq 400\,000\)) — длины сторон таблицы.

В каждой из следующих \(n\) строках вводятся \(m\) целых чисел \(a_{i1}, a_{i2}, \dots, a_{im}\) (\(1 \le a_{ij} \le n \cdot m\)).

Гарантируется, что каждое число от \(1\) до \(n \cdot m\) встречается ровно один раз.

Формат выходных данных
Пусть \(a\) — минимальное число действий, после которых головоломка станет решаемой.

Если \(a = 0\), выведите \(0\).

Если \(a = 1\), выведите \(1\), а также количество подходящих пар клеток.

Если \(a \ge 2\), выведите \(2\).

В первом примере из условия последовательность клеток \((1, 2), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)\), \((2, 3), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1)\) решает головоломку, поэтому ответ \(0\).

Головоломка во втором примере из условия не решается, но будет решаться после любого из трех обменов клеток со значениями \((1, 5), (1, 6), (2, 6)\).

В третьем примере из условия потребуется не менее двух обменов, поэтому ответ равен \(2\).

ID 48935. Вордл наоборот

Камила и Динара играют в <<Wordle>>. Камила загадала слово длины \(n\), состоящее из различных латинских букв. Динара сделала одну попытку угадать и назвала слово длины \(n\), также состоящее из различных латинских букв. Камила раскрасила буквы в догадке Динары в соответствии со следующими правилами:

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

• Буква, которая присутствует в загаданном слове, но стоит не своей позиции, красится в жёлтый цвет и обозначается Y.

• Буква, отсутствующая в загаданном слове, красится в белый цвет и обозначается W.

Например, если было загадано слово ALERT, а догадка была ALONE, то буквы будут раскрашены в цвета GGWWY. Первые две буквы в словах совпадают, поэтому они зеленые. Буква E есть в загаданном слове, но находится на другой позиции, поэтому она жёлтая. Остальные буквы белые, так как их нет в загаданном слове.

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

В первой строке вводится одно целое число \(n\) \((1 \le n \le 10)\) — длина загаданного слова.

Во второй строке вводится строка длины \(n\), состоящая из заглавных латинских букв — загаданное слово. Гарантируется, что все буквы в нем различны.

В третьей строке вводится строка длины \(n\), состоящая из букв G, Y, W — цвета, в которые были раскрашены буквы в слове Динары.

Если подходящих слов не существует, выведите No.

Если хотя бы одно подходящее слово существует, в первой строке выведите Yes, во второй  — любое подходящее слово.

Разберем первый пример из условия.

Буквы H и G не встречаются в загаданном слове, поэтому они белые.

Буквы E и B встречаются, но на других позициях, поэтому они жёлтые

Буквы C и D совпадают с буквами на соответствующих позициях в загаданном слове, поэтому они зелёные.

Есть и другие ответы, любой правильный ответ будет зачтен.

Обратите внимание, что строка HECDBH не является ответом, так как в ней есть совпадающие буквы.

ID 48933. Палиндромные числа

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Число называется палиндромом, если оно читается одинаково справа налево и слева направо. Например, числа \(121, 66, 98989\) являются палиндромами, а \(103, 239, 1241\) — нет.

После некоторых размышлений Алина поняла, что такое число всегда можно найти. Помогите Алине найти подходящее число!

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(2 \leq n \leq 100\,000\)) — длина числа, которое увидела Алина.

Во второй строке вводится одно положительное целое число длины \(n\). Гарантируется, что оно не содержит ведущих нулей.

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

Если таких чисел несколько, вы можете вывести любое из них.

В первом примере из условия \(99 + 32 = 131\) — палиндром. Число \(12\) также будет являться ответом, так как \(99 + 12 = 111\).

Во втором примере из условия \(1023 + 8646 = 9669\).

В третьем примере из условия \(385 + 604 = 989\).

ID 24911. Держать строй

ID 24910. Поймать Халка

ID 48965. Посадка в самолет

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

При онлайн-регистрации пассажир может выбрать любое место и не может его затем менять. Например, при \(n = 6\) рассадка в самолете после онлайн-регистрации может выглядеть так (крестиками отмечены занятые места):

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

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

Формат входных данных
В первой строке содержатся два целых числа \(n\) и \(m\) — количество рядов в самолете и количество пассажиров, которые придут на стойку регистрации (\(1 \le n \le 1000\), \(0 \le m \le 6000\)).

В следующих \(n\) строках задана изначальная рассадка в самолете после онлайн-регистрации. В каждой строке содержится по шесть символов, при этом \(i\)-й символ \(j\)-й строки равен <<X>> (заглавная английская X), если \(i\)-е место в \(j\)-м ряду уже занято и <<.>> (точка) иначе.

Формат выходных данных
Если искомой рассадки не существует, выведите <<Impossible>>.

Иначе выведите \(n\) строк по шесть символов — итоговую рассадку в самолете. При этом \(i\)-й символ \(j\)-й строки должен быть равен <<X>>, если место занято, и <<.>>, если свободно. Если существует несколько решений, разрешается вывести любое.

Ниже приведены пять примеров входных данных.

1. В первом примере \(m = 0\), а рассадка в самолете симметрична, поэтому итоговая рассадка совпадает с исходной.

2. Во втором примере есть только один способ рассадить пассажиров симметрично.

3. В третьем примере существовало бы решение, при \(m = 1\), но при \(m = 2\) не существует способа рассадить всех пассажиров симметрично.

4. В четвертом примере требуется рассадить больше пассажиров чем свободных мест в самолете.

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

ID 30714. Телефонные номера

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

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

При отображении телефонного номера на экране телефона, части этого номера принято отделять друг от друга различными символами так, чтобы номер было проще прочитать и запомнить. Так, перед кодом страны обычно ставится символ «+», код региона или оператора берется в скобки, номер абонента разделяется символами «-» на несколько частей. При этом, то, на сколько частей он разбивается, напрямую зависит от количества цифр в нем:
• если номер абонента состоит из трех цифр, то он представляет собой одну часть, состоящую из трех цифр;
• если номер абонента состоит из четырех цифр, то он разбивается на две части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из пяти цифр, то он разбивается на две части, первая из которых состоит из трех цифр, а вторая — из двух;
• если номер абонента состоит из шести цифр, то он разбивается на три части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из семи цифр, то он разбивается на три части, первая из которых состоит из трех цифр, а все остальные — из двух.

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

Формат входных данных
Первая строка файла содержит одно целое число n (1 ≤ n ≤ 100) — количество государств, информация про телефонные коды которых записана в память телефона. Далее следуют n описаний этих государств, разделенных переводами строк. Первая строка описания каждого государства содержит два целых числа c и k (1 ≤ c ≤ 999, 1 ≤ k ≤ 100) — телефонный код этого государства и количество операторов или регионов, существующих в этом государстве. Следующие k строк описания этого государства содержат целые числа, каждое из которых не меньше 100 и не больше 99999 — коды операторов или регионов, зарегистрированных в этом государстве.
Следующая строка входного файла содержит одно целое число m (1 ≤ m ≤ 10 000) — количество телефонных номеров, которые необходимо отформатировать. Следующие m строк содержат сами номера — строки, состоящие ровно из 11 цифр.
Гарантируется, что ни один данный вам номер невозможно разбить на код государства, код оператора или региона и номер абонента более, чем одним способом.

Формат выходных данных
Выведите номера, данные вам во входном файле, отформатированными по правилам, описанным в условии. Каждый номер необходимо вывести в отдельной строке. Номера необходимо выводить в том же порядке, в котором они были перечислены во входном файле. Вместо номеров, корректного разбиения которых на код государства, код оператора или региона и номер абонента не существует, необходимо вывести слово «Incorrect».
 

ID 30715. Вращающаяся пластина

Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.

Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.

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

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

Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 10⁶ по модулю.

Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа α_i и β_i , где α_i — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а β_i — максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите α_i = β_i = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10⁻⁶ .
 

ID 30717. Перетягивание каната

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

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по d сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы d сантиметров. Например, если d = 10, то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

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

Формат входных данных
В первой строке заданы числа n (1 ≤ n ≤ 100 000) и d (1 ≤ d ≤ 1000) — количество кусков каната и длина каната, уходящая на завязывание узла. Во второй строке заданы n чисел ai (1 ≤ a_i ≤ 1000) — длины имеющихся кусков каната.

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

ID 30718. Загранпаспорт

Осень 2243-го года. Государства в прошлом, главным территориальным образованием является автономия. В результате терраформирования территория бывшей Евразии теперь представляет собой прямоульник, он разбит на w × h квадратных автономий, которые организованы в виде сетки из w автономий по ширине и h по высоте. Некоторые автономии входят в содружество Крипто, они представляют собой криптоанархистские технократические общества и не признают бюрократии. Остальные автономии входят в конфедерацию Бюрро, бюрократия в них доведена до высшего совершенства.

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

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

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

Формат входных данных
В первой строке входного файла содержатся три целых числа: w, h и n (1 ≤ w, h ≤ 500, 1 ≤ n ≤ 1 000). В каждой из следующих h строк содержится по w символов, они задают карту Евразии. Символ «A» обозначает автономию содружества Крипто, а «T» — автономию конфедерации Бюрро. Автономия, в которой Вениамин начинает свое путешествие, обозначена символом «V». Карта дана с севера на юг по строкам и с запада на восток по столбцам, таким образом, первый символ второй строки входного файла описывает самую северо-западную автономию. Гарантируется, что в Евразии есть хотя бы одна автономия Бюрро.

Формат выходных данных
В выходной файл выведите одну строку из символов «N», «E», «S», «W» — план путешествия Вениамина. Эти символы означают, что Вениамину следует поехать на север, восток, юг или запад, соответственно. Число перемещений в плане необходимо минимизировать, в процессе путешествия Вениамин должен ровно n раз въехать в автономию Бюрро. Если возможных оптимальных планов путешествия несколько, можно вывести любой.
 

ID 30719. Вирус

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

Формат входных данных
В первой строке входного файла находятся целые числа n, m и t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — размеры таблицы и количество секунд. Каждая из следющих n строк содержит m символов. Символ «.» означает, что в изначальной конфигурации клетка не заражена, а символ «*» — что заражена. Количество «*» в таблице не превышает 8. Гарантируется, что незараженных клеток в исходной конфигурации не меньше t.

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

ID 34772. Римские числа

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

Например, если на пергаменте записана строка «XIIV», её можно разбить на римскиечисла разными способами, например, XI + IV = 11 + 4 = 15 или XII + V = 12 + 5 = 17, возможны и другие варианты разбиения.

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

Программа получает на вход строку, длина которой не превосходит 250 символов. Строка состоит только из заглавных латинских букв I, V, X, L, С, D, M.

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

Правила записи римских чисел
Римскими цифрами можно записать целые числа от 1 до 3999. Число представляется в виде суммы тысяч, сотен, десятков и единиц. Далее из следующей таблицы берётся по одному элементу, соответствующему тысячам, сотням, десяткам, единицам ровно в таком порядке.



Если число тысяч, сотен, десятков, единиц равно 0, то из соответствующего столбца ничего не берётся. Например, число 1990 записывается, как 1000 + 900 + 90 = MCMXС.

ID 34774. Тройка

У Олега есть карта «Тройка», на которой осталась одна поездка на наземном транспорте. От дома Олега до школы можно доехать на трамвае, троллейбусе или автобусе. Трамвай ходит через каждые 15 минут, троллейбус — через каждые 10 минут, автобус — через каждые 5 минут, при этом в 8:00 одновременно от остановки отправляются и трамвай, и троллейбус, и автобус (то есть трамвай отправляется в 8:00, 8:15, 8:30, 8:45, 9:00; троллейбус — в 8:00, 8:10, 8:20, 8:30, 8:40, 8:50, 9:00; автобус — в 8:00, 8:05, 8:10, 8:15 и т. д.). Трамвай едет до нужной остановки X минут, троллейбус — Y минут, автобус — Z минут.

Когда Олег пришёл на остановку, на часах было 8 часов M минут. Определите минимальное время, через которое Олег окажется на нужной ему остановке (считая время ожидания транспорта и время поездки на транспорте). Если какой-то транспорт отправляется в тот же момент, когда Олег пришёл на остановку, то Олег успевает на нём уехать.
Программа получает на вход сначала три целых положительных числа X, Y, Z, не превосходящие 100, записанные в отдельных строчках, — время поездки на трамвае, троллейбусе, автобусе соответственно. В четвёртой строке входных данных записано целое число M (0 ≤ M ≤ 59) — момент времени (в минутах), когда Олег пришёл на остановку.
Программа должна вывести одно натуральное число — минимально возможное суммарное время ожидания транспорта и поездки.
 

ID 34778. Турнир

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

ID 50973. Новое --- это хорошо забытое старое

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

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

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

Помогите Андрею найти первое следующее в алфавитном порядке слово, состоящее из тех же букв, что и заданное слово, и состоящее ровно из \(k\) букв. Гарантируется, что такое слово существует.

Формат входных данных
В первой строке задано целое число \(n\) (\(1 \leq n \leq 100\,000\)) — количество букв в первом слове.

Во второй строке задано слово, состоящее из \(n\) строчных букв английского алфавита.

В третьей строке задано целое число \(k\) (\(1 \leq k \leq 100\,000\)) — количество букв в искомом слове.

Формат выходных данных
Выведите искомое слово, состоящее из \(k\) букв, входящих в первое слово.

В первом тестовом примере требуемое слово должно состоять из букв a, b и c. Следующим после abc в алфавитном порядке будет слово abca, но оно состоит из 4 букв, а не из 3. Следующим после abc в алфавитном порядке состоящим из букв a, b и c и имеющим длину 3 будет слово aca.

В данной задаче \(50\) тестов, помимо тестов из условия. 

Не менее чем в 15 тестах первое слово будет состоять только из букв abc, причем каждая из трех букв будет встречаться. 

Решения, работающие при \(1 \leq n, k \leq 3\) будут набирать не менее \(10\) баллов.

Решения, работающие при \(1 \leq n, k \leq 10\) будут набирать не менее \(30\) баллов.

Решения, работающие при \(1 \leq n, k \leq 5\,000\) будут набирать не менее \(60\) баллов.

ID 50974. Умный обогреватель

Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему <<Умный дом>>. В соответствующую программу Максим заложил два целых числа \(t_{min} \leq t_{max}\) и следующий алгоритм использования обогревателя:

1. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был выключен, и в каждый из этих дней температура на улице была строго меньше \(t_{min}\), то надо включить обогреватель в этот день и считать, что он был включен весь день. Обогреватель остается включенным и в последующие дни до тех пор, пока программа его не выключит.

2. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше \(t_{max}\), то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.

Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения \(t_{min}\) и \(t_{max}\) Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из \(n\) дней использования системы.

Максим помнит, что \(t_{min}\) и \(t_{max}\) были целыми числами, по модулю не превосходящими \(10^9\) и \(t_{min} \leq t_{max}\), также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал \(t_{min}\) и \(t_{max}\) как можно более близкими друг к другу.

Помогите найти два подходящих значения \(t_{min}\) и \(t_{max}\), не превосходящих \(10^9\) по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из \(n\) дней, \(t_{min}\) не превосходит \(t_{max}\) и величина \(t_{max} - t_{min}\) минимальна.

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

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

Во второй строке входных данных задаются \(n\) целых чисел \(t_1, \dots, t_n\) (\(-10^9 \leq t_i \leq 10^9\)) — температуры на улице в каждый из \(n\) дней.

В третьей строке входных данных задается строка из \(n\) символов, состоящая из 0 и 1 — если в \(i\)-й позиции данной строки записан 0, то это значит, что в \(i\)-й день обогреватель был выключен, а если 1, — то включен.

Формат выходных данных
В единственной строке выведите два целых числа \(t_{min}\) и \(t_{max}\) (\(t_{min} \leq t_{max}\)), по модулю не превосходящих \(10^9\) — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение \(t_{max} - t_{min}\) минимально.

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

В первом тестовом примере первые пять дней температура строго меньше \(7\) градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию \(6 \leq t_{min} = t_{max} \leq 10^9\).

ID 50985. Проверка на списывание

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

Пусть есть две строки, описывающие решения. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После этого для рассматриваемого символа \(x\) определим другой символ \(p(x) \neq x\) и заменим некоторые вхождения \(x\) в первое решение на \(p(x)\). Если в ходе такого процесса из первого решения возможно получить второе, то скажем, что второе решение списано с первого.

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

Значения \(p(x)\) участником выбираются независимо для разных \(x\), поэтому они могут и совпасть.

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

Кроме платформы вы создали язык программирования S++ и, чтобы его популяризировать, вы решили разрешить сдавать задачи в своей системе только на нем. Одной из особенностью языка является то, что любая программа записывается в одну строку и может состоять только из строчных и заглавных букв английского алфавита (a-z, A-Z), цифр (0-9), скобок (‘(’, ‘)’, ‘{’, ‘}’ ‘[’, ‘]’), знаков сравнения (‘<’, ‘>’, ‘=’) и символов ‘+’, ‘-’, ‘*’, ‘/’, ‘;’.

Формат входных данных
В первой строке вам дано число  \(n\) \((1 \leqslant  n \leqslant 200\,000)\), равное длине каждой из программ.

Во второй строке вам дана программа первого участника на языке S++.

В третьей строке вам дана программа второго участника на языке S++.

Формат выходных данных
Если вторая программа списана с первой, выведите <<YES>> (без кавычек), на следующей строке выведите \(m\) – количество различных символов в первой программе, которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots, \ c_m\). После этого выведите \(m\) строк. На \(i\)-й строке  необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если вторая программа не списана с первой, то выведите <<NO>> (без кавычек).

Примечание
В первом примере списывающий заменил все вхождения ‘i’ на ‘j’ и вхождения ‘n’ на ‘m’.

Во втором примере участник заменял ‘a’ на ‘e’, ‘b’ на ‘f’, ‘с’ на g’ и ‘-’ на ‘+’.

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

В четвертом примере участник списал, заменив некоторые вхождения ‘a’ на ‘b’.

В пятом примере участник списал, заменив некоторые вхождения ‘a’ на ‘b’ и все вхождения ‘c’ на ‘a’.

ID 50990. Преобразование строки

Даны две строки \(S\) и \(T\) из строчных букв английского алфавита.

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

Например, пусть \(S =\) <<aabab>>, \(T =\) <<abbbc>>. Из \(S\) можно получить \(T\), если выбрать p(‘a’) = ‘b’, p(‘b’) = ‘c’ и заменить второе и третье вхождение ‘a’ на p(‘a’), второе вхождение ‘b’ на p(‘b’).

А если \(S =\) <<aabaс>>, \(T =\) <<bbbbb>>, то все вхождения ’a’ и ’c’ были заменены на ’b’.

Формат входных данных
В первой строке вам дано число \(n\) \((1 \leqslant n \leqslant 200\,000)\). Во второй строке задана \(S\). В третьей строке задана \(T\). Обе строки имеют длину \(n\) и состоят только из букв от ‘a’ до ‘z’.

Формат выходных данных
Если возможно осуществить описанный процесс так, чтобы из \(S\) получилась \(T\), выведите <<YES>>, на следующей строке выведите \(m\) – количество различных символов \(S\), которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots \ c_m\). После чего выведите \(m\) строк. На \(i\)-й строке необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если это сделать невозможно, выведите <<NO>>.

ID 51137. Дневник дождя

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

Сегодня Петя открыл дневник, чтобы сделать очередную запись, и обнаружил, что он сделал последнюю запись две недели назад, а в прошлое воскресенье забыл занести информацию в дневник. Петя помнит, что неделю назад шёл дождь, и он решил сделать две записи: за сегодняшний день и за прошлое воскресенье. Он знает номер текущего дня в месяце \(n\) и видит, каким числом \(m\) подписана запись две недели назад. Каким числом Петя должен подписать запись за прошлую неделю?

Формат входных данных
В первой строке вывода даны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 31\)) — номер текущего дня месяца и число, которым подписана запись две недели назад.

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

Выведите единственное число – каким числом должна быть подписана запись неделю назад.

ID 51138. Магнитные игры

У Вовы есть любимый магнит. Вове очень нравится играть с ним на большой поляне, которую можно представить в виде прямоугольника \(n\) на \(m\) клеток.

Однажды он пришел играть на поляну с магнитом и потерял его в одной из клеток. Вова очень расстроился, но нашел решение — в каждую клетку поляны он положил компас, стрелка которого может принимать 8 положений: вверх, вверх-вправо, вправо, вниз-вправо, вниз, вниз-влево, влево и вверх-влево. Каждому положению стрелки соответствует его номер:

Стрелки принимают направление, близкое к направлению на магнит: если магнит лежит строго по диагонали от компаса, то его стрелка примет диагональное положение, иначе — более близкое к направлению на магнит из вертикального и горизонтального. Стрелка компаса в клетке с магнитом может быть направлена куда угодно.

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

Теперь Вова не знает, как ему найти свой магнит, и просит помощи у вас.

Формат входных данных
В первой строке входных данных записаны два целых числа через пробел \(n\) и \(m\) — размеры поляны (\(2 \le n, m \le 1500, nm \ge 6\)).

В следующих \(n\) строках описываются компасы на поляне.

В \(i\)-й строке записаны \(m\) целых чисел \(a_{i,j}\) (\(1 \le a_{i,j} \le 8\)), \(j\)-е число в \(i\)-й строке обозначает направление стрелки компаса в \(j\)-й клетке \(i\)-й строки.

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

В первой строке выведите два числа \(x\) и \(y\) через пробел — номер строки и столбца клетки, в которой лежит магнит.

Во второй выведите два числа \(a\) и \(b\) через пробел  — номера горизонтали и вертикали, в которых действует аномалия.

В данном тесте магнит лежит в клетке \((2, 1)\), инвертируется горизонталь номер \(3\) и вертикаль номер \(3\).

ID 59830. Жидко-кристаллический дисплей

На жидкокристаллическом дисплее с разрешением \(h\times w\) используются пиксели трех цветов: красного, зеленого и синего. Будем обозначать их заглавными английскими буквами ‘R’, ‘G’ и ‘B’, соответственно.

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

В первой строке первый пиксель <<R>>, а каждая следующая строка сдвинута на один налево относительно предыдущей: во второй первый пиксель <<G>>, а второй <<B>>, в третьей первый пиксель <<B>>, в четвертой первый пиксель <<G>>, а второй <<R>>, и так далее.

Выведите, как расположены пиксели на экране.

Формат входных данных
На вход подаются целые числа \(h\) и \(w\), по одному на строке (\(1 \le h, w \le 100\)).

Формат выходных данных
Выведите \(h\) строк по \(w\) символов — цвета пикселей на дисплее.

ID 62568. Покраска холста

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

Робот выполняет команды пользователя, при этом перемещаясь по полю в соответствии с заданными настройками и ограничениями.

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из направления (вправо, вверх, влево, вниз) и цвета. Если \(S_{i,j} = (d, c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же смещается на одну клетку в направлении \(d\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на максимальное разрешенное число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

Пользователю доступны следующие команды для взаимодействия с роботом:

1. <<color \(i\) \(j\) \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

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

   • для очередной клетки \(S_{i',j'} = \varnothing\);

   • с очередной покраской перестанет выполняться какое-то из ограничений.

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<limit \(c\) \(x\)>> — выставить ограничение на максимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле уже больше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<block \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<settings \(i\) \(j\) \(d\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \((d, c)\), где \(d\) — направление перемещения, а \(c\) — цвет, в который затем будет раскрашена клетка, в которую робот переместится.

6. <<settings \(i\) \(j\) none>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = (\rightarrow, \mathtt{red})\), \(S_{1,2} = (\downarrow, \mathtt{blue})\), \(S_{2,2} = (\leftarrow, \mathtt{green})\) и \(S_{2,1} = (\uparrow, \mathtt{red})\), то при поступлении команды <<color \(1\) \(1\) blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Направления задаются строками <<right>> (вправо), <<up>> (вверх), <<left>> (влево), <<down>> (вниз). Цвета задаются заглавными буквами ‘R’ (красный), ‘G’ (зеленый), ‘B’ (синий) и ‘W’ (белый).

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

В первом примере из условия

1. Команда <<color 1 1 R>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = (\downarrow, \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = (\downarrow, \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<color 2 1 G>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \((\rightarrow, \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<limit B 0>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   RW
   GW
   RW

4. Затем <<color 2 2 R>> должен покрасить \((2, 2)\) в красный, но это бы привело к получению квадрата с цветами RWGR, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<color 2 2 B>> отрабатывает корректно, так как до этого было разрешено иметь на поле не больше \(1\) синей клетки. После чего, в соответствии с \(S_{2,2} = (\uparrow, \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   RG
   GB
   RW

ID 62569. Покраска холста - 2

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

Робот выполняет команды пользователя, при этом перемещаясь по полю в соответствии с заданными настройками и ограничениями.

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из координат клетки и цвета. Если \(S_{i,j} = ((i', j'), c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же перемещается в клетку \((i', j')\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на минимальное требуемое число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

Пользователю доступны следующие команды для взаимодействия с роботом:

1. <<fill \(i\) \(j\) with \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

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

   • для очередной клетки \(S_{i',j'} = \varnothing\);

   • с очередной покраской перестанет выполняться какое-то из ограничений.

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<at-least \(x\) \(c\)>> — выставить ограничение на минимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле меньше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<no-squares \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow-squares \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<move \(i\) \(j\) to \(i'\) \(j'\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \(((i', j'), c)\), где \((i', j')\) — клетка, в которую надо переместиться, а \(c\) — цвет, в который затем надо ее покрасить.

6. <<no-move \(i\) \(j\)>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = ((1, 2), \mathtt{red})\), \(S_{1,2} = ((2, 2), \mathtt{blue})\), \(S_{2,2} = ((2, 1), \mathtt{green})\) и \(S_{2,1} = ((1, 1), \mathtt{red})\), то при поступлении команды <<fill \(1\) \(1\) with blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Цвета задаются строками <<red>> (красный), <<green>> (зеленый), <<blue>> (синий) и <<white>> (белый).

Формат выходных данных
Для каждого набора входных данных выведите итоговую раскраску поля, полученную после обработки всех команд. Для обозначения красного, зеленого или синего цвета используйте первую букву его английской записи (‘r’, ‘g’ или ‘b’); для обозначения белого цвета используйте символ ‘.’.

В первом примере из условия

1. Команда <<fill 1 1 with red>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = ((2, 1), \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = ((3, 1), \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<fill 2 1 with green>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \(((2, 2), \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<at-least 3 white>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   r.
   g.
   r.

4. Затем <<fill 2 2 with R>> должен покрасить \((2, 2)\) в красный (ограничение на число белых уже снято), но это бы привело к получению квадрата с цветами r.gr, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<fill 2 2 with B>> выполняется. После чего, в соответствии с \(S_{2,2} = ((1, 2), \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   rg
   gb
   r.