Problem A1. Bucket sort (LETTERS ONLY) ≡

Statement

Input file format

Output file format

Constraints

Sample tests

4
KVN
ACM
FSB
GGG

ACM
FSB
GGG
KVN

Задача A2. Быстрая помощь ≡

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности a_i минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

Требуется определить минимальное время в минутах, требуемое на перелёт и разгрузку всех самолётов.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 10
8 5

25

Problem A3. ACM Rank Table ≡

Statement

ACM contests, like the one you are participating in, are hosted by the special software. That software, among other functions, preforms a job of accepting and evaluating teams' solutions (runs), and displaying results in a rank table. The scoring rules are as follows:

1. Each run is either accepted or rejected.
2. The problem is considered solved by the team, if one of the runs submitted for it is accepted.
3. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first accepted run for this problem (in minutes) plus 20 minutes for every other run for this problem before the accepted one. For an unsolved problem consumed time is not computed.
4. The total time is the sum of the time consumed for each problem solved.
5. Teams are ranked according to the number of solved problems. Teams that solve the same number of problems are ranked by the least total time.
6. While the time shown is in minutes, the actual time is measured to the precision of 1 second, and the the seconds are taken into account when ranking teams.
7. Teams with equal rank according to the above rules must be sorted by increasing team number.

Your task is, given the list of N runs with submission time and result of each run, compute the rank table for C teams.

Input file format

Output file format

Constraints

Sample tests

2 3
1 1 5000 0
1 1 500 1
2 1 10000 1

1 2

3 3
1 2 3000 0
1 2 3100 1
2 1 4200 1

2 1 3

Задача A4. K-ая порядковая статистика ≡

Условие

K-ой порядковой статистикой N-элементной последовательности A_N называется число A_K, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.

Последовательность A_N задаётся следующим образом. A₁ = P, A_i = (A_i − 1 ⋅ Q) mod V.

Формат входного файла

Во входном файле содержатся целые числа Q V P N K

Формат выходного файла

В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной последовательности.

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 2³¹ − 1

1 ≤ K ≤ N ≤ 4 ⋅ 10⁷

Примеры тестов

343 32767 3 10 7

16478

Задача A5. Сортировка подсчетом ≡

Условие

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4
2 1
3 2 
2 3
3 4

1 3 2 4

Задача B0. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел a_i.

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

Примеры тестов

3
1 1 2

1 2 3

2
2 5

-1

Задача B1. Чемпионат по боксу ≡

Условие

В чемпионате по боксу соревнуется две команды по N боксёров в каждой. Все боксёры разбиты на M весовых категорий. Каждый боксёр характеризуется уровнем мастерства p_i (при этом не существует двух боксёров с равным уровнем мастерства) и номером весовой категории в которой он выступает c_i. Чемпиона проходит по следующим правилам: все участники разбиваются по весовым категориям и в рамках одной весовой категории каждый боксёр одной команды выходит на ринг против каждого боксёра другой команды, за победу в бое начисляется одно очко. Боксёр точно победит если его уровень мастерства выше уровня мастерства соперника.

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

Формат входного файла

Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел p_i, с_i  — описание боксёров из команды Пахома. Далее N пар чисел p_i, с_i  — описание команды соперников.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 300, 1 ≤ с_i ≤ M; 1 ≤ p_i ≤ 10⁹.

Описание подзадач и системы оценивания

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

Примеры тестов

3 1
1 1
2 1 
3 1
4 1
5 1
6 1

-9

4 2
60 1
100 2
110 2
120 2
200 1
50 2
40 2
30 2

12

3 3
5 1
10 2
15 3
6 1
11 2
16 3

-1

Задача B2. Золотая середина ≡

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы).

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

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать n целых чисел — значения центрального элемента после каждого добавления.

Ограничения

1 ≤ n ≤ 10⁶,  − 10⁹ ≤ a_i ≤ 10⁹.

Примеры тестов

3
5 3 4

5 3 4

5
1 2 3 2 4

1 1 2 2 2

Задача C1. Сбалансированное дерево ≡

Условие

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача C3. Сравнения подстрок ≡

Условие

Дана строка. Нужно уметь отвечать на запросы вида: равны ли подстроки [a… b] и [c… d].

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

Сперва строка S из строчных латинских букв. Далее число M — количество запросов.

В следующих M строках по четыре целых числа — запросы a, b, c, d.

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

Выведите M строк, по одному ответу для каждого запроса. Ответ должен быть Yes, если подстроки совпадают, и No в противном случае.

Ограничения

0 ≤ M ≤ 10⁵, 1 ≤ a ≤ b ≤ |S|, 1 ≤ c ≤ d ≤ |S|, 1 ≤ |S| ≤ 10⁵.

Примеры тестов

trololo
3
1 7 1 7
3 5 5 7
1 1 1 5

Yes
Yes
No

Задача C4. Синхронизация ≡

Условие

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

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

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

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

Формат входного файла

Входной файл содержит целое число N. Далее следует N целых чисел a₁, a₂, …, a_N — времена событий, зафиксированных коллайдером. Затем записано целое число M. Далее следует M чисел b₁, b₂, …, b_M — времена событий, зафиксированных Колей.

Формат выходного файла

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

Ограничения

2 ≤ M ≤ N ≤ 10⁵;

0 ≤ a₁ ≤ a₂ ≤ …  ≤ a_N ≤ 10⁹;

0 = b₁ ≤ b₂ ≤ …  ≤ b_M ≤ 10⁹;

Примеры тестов

5
10 15 17 19 20
2
0 2 

2

Задача D0. Двоичные последовательности ≡

Условие

Здравствуй, юный падаван!

Прошу тебя вывести все двоичные последовательности длины N.

Реши задачу двумя способами:

• рекурсивным перебором
• прибавлением 1 к числу в двоичной системе счисления

Да пребудет с тобой произведение массы на ускорение!

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 15

Примеры тестов

2

00
01
10
11

Задача D1. Перестановки с подстрокой ≡

Условие

Даны строки S и P, состоящие из малых латинских букв. Требуется определить сколько различных слов, составленных из букв строки S, содержат в себе подстроку P.

Например, если S = dcba, P = bc, то получится 11 строк: bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

dbca
bc

11

xyz
xx

0

Задача D3. Сумма с перестановкой ≡

Условие

Заданы три числа: a, b, c. Необходимо выяснить, существуют ли такие числа x и y, что:

1. x получается перестановкой цифр числа a;
2. y получается перестановкой цифр числа b;
3. x и y не содержат лидирующих нулей;
4. x + y = c.

Формат входного файла

Входной файл содержит целые числа a b c.

Формат выходного файла

Если искомые числа существуют, вывести в первую строку выходного файла слово YES, а во вторую — числа x y, разделённые пробелом. В противном случае вывести слово NO.

Ограничения

1 < a, b, c < 10⁹

Примеры тестов

12 31 25

YES
12 13

12 31 26

NO

Задача D4. Восстановить IP ≡

Условие

Корректная запись IP-адреса — это строка, состоящая из четырёх десятичных чисел в диапазоне от 0 до 255 каждое, разделённых символом "точка" (ASCII 46). Компоненты записи IP-адреса не должны содержать лидирующих нулей.

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

Помогите Пете восстановить IP-адрес.

Формат входного файла

Формат выходного файла

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

Примеры тестов

7.2
102.
47
84.1

102.84.17.247

.0.
00
1
2.0

100.0.2.0
2.0.0.100

Задача D5. Слишком много способов ≡

Условие

Однажды школьник Вася пришел в недавно построенное новое здание университета на мастер-класс по информатике. Здание имеет форму куба, составленного из одинаковых аудиторий также кубической формы. Каждой аудитории присвоены три номера x, y, z — порядковые номера по ширине, длине и высоте соответственно. Самая первая аудитория имеет номера 1, 1, 1. Из каждой аудитории можно перейти в любую соседних, имеющих с ней общую стену.

Вася находится в аудитории (x_B, y_B, z_B). Мастер-класс пройдет в аудитории (x_M, y_M, z_M). Вася решил посчитать, сколькими способами можно попасть из текущей аудитории в ту, где проходит мастер-класс, за наименьшее число переходов между аудиториями.

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

Формат входного файла

Входной файл содержит 6 целых чисел x_M y_M z_M x_B y_B z_B.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество способов. Так как ответ на вопрос Васи может быть слишком большим, выведите в его остаток от деления на 10⁹ + 7.

Ограничения

1 ≤ x_M, y_M, z_M, x_B, y_B, z_B ≤ 1000.

Примеры тестов

1 1 1 2 2 2

6

1 1 1 3 3 3

90

Задача D6. Длинное взятие ≡

Условие

На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек. Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.) Вертикали обозначены буквами a, b, c, … слева направо. Клетка, таким образом, задается комбинацией из буквы и числа, например d12. Ход шашки задается перечислением всех клеток, которые она посетила за этот ход, включая начальную и конечную. Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5
.....
.O.O.
....X
.O.O.
X....  

e3-c1-a3-c5-e3  

4
X...
....
....
...O  

Impossible

Задача D7. Домино ≡

Условие

Костяшка домино описывается парой цифр от 0 до 6, например 06 или 33. Цепочка - это последовательность костяшек, скложенных таким образом, чтобы соседние цифры на них совпадали. При этом костяшки можно переворачивать. Например, 15-54-44-46-60 — цепочка.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1234

NO

453335

45-53-33

Задача D8. Судьба математика ≡

Условие

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

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1<2
3=1
3>4

12000

Задача E0. Антон и магазин радиодеталей ≡

Условие

Инженер Антон зашёл в магазин радиодеталей. В магазине ровно N стеллажей. На i-м стеллаже лежат радиодетали типа a_i (на двух различных стеллажах тип радиодеталей может повторяться). Антон обходит с тележкой стеллажи в порядке от первого до N-го.

Когда Антон подходит к очередному стеллажу, он смотрит в тележку. Если в тележке нет радиодеталей такого типа, как на стеллаже, Антон берёт деталь со стеллажа и складывает в тележку. Если радиодеталь такого типа в тележке уже лежит, Антон просто идет дальше.

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

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

Примечание

Рекомендуется рассмотреть частичные решения для N ≤ 1000, a_i ≤ 10⁵.

Формат входного файла

Входной файл содержит целое число два целых числа N и K, вторая строка содержит N чисел a_i.

Формат выходного файла

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

Ограничения

1 ≤ N, K ≤ 10⁵

0 ≤ a_i ≤ 10⁹

Примеры тестов

3 3 
1 2 3

3

5 2
1 1 1 2 2

2

7 3
8 2 3 1 1 2 2

4

Задача E1. Блинчики ≡

Условие

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

За какое минимальное число таких действий Петя может перевернуть все блины светлой стороной вверх?

Формат входного файла

В первой строке входного файла дано число N (1 ≤ N ≤ 100 000) — количество блинчиков. Далее в N строках описываются блинчики, сверху вниз. Если в i-й строке стоит символ W, то i-й блинчик лежит недожаренной стороной вверх, а если B, то подгоревшей стороной вверх.

Формат выходного файла

В выходной файл выведите единственное число — количество переворачиваний, которое должен сделать Петя, чтобы положить все блинчики недожаренной стороной вверх.

Примеры тестов

6
W
B
B
B
W
B

4

Задача E2. Арифметическая прогрессия ≡

Условие

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

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

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

Формат входного файла

Входной файл содержит целое число N — количество чисел, за которым следуют N целых чисел a_i.

Формат выходного файла

Выходной файл должен содержать целое число M — количество чисел, которые останутся после вычёркивания (при этом количество вычеркнутых чисел должно быть минимальным).

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 10⁶

Примеры тестов

7
1 3 4 2 7 8 10

4
1 3 5 7

Задача F1. Сбалансированное дерево revisited ≡

Условие

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

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача J1. WK ≡

Условие

В рамках социального проекта ЦПД в кампусе ДВФУ была организована социальная сеть WK, чтобы студенты могли обмениваться через неё учебными материалами и решать все насущные вопросы.

У каждого пользователя этой сети есть список контактов. Однажды в сеть WK поступил вброс о том, что студентам стали снижать оценки за лайки не(у)годным преподавателям.

Однажды утром на департамент мемов матфака поступило видео из серии "Капоэйра в неожиданных местах", в котором сотрудник кафедры информатики, математического и компьютерного моделирования ШЕН рассказал о произошедшем языком танца. Затем из этого видео выбрали понравившийся фрагмент и стали распространять в сети WK как мем.

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

Затем информация распространялась по сети WK следующим образом.

1. Сообщения отправляются только утром, а получаются только вечером.
2. Если пользователь B получил информацию от пользователя A, то утром следующего дня пользователь B разошлёт эту информацию всем своим контактам, от которых он не получал эту информацию и которым он не отправлял эту информацию.

Социальная сеть WK устроена таким образом, что если пользователь B находится в списке контактов пользователя A, то и пользователь A находится в списке контактов пользователя B. Никакой пользователь не может находиться в своём же списке контактов.

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество пользователей социальной сети WK.

Далее для каждого пользователя во входном файле записана следующая информация. Сначала идёт целое число k_i — количество пользователей в списке контактов пользователя i, за которым следуют k_i различных целых чисел от 1 до N — номера пользователей из списка контактов i-го пользователя.

Админ группы "Учеба каждый день, какой ужас", он же админ группы "Стримы от Малявина" — это пользователь с номером 1.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100.

0 ≤ k_i < N.

Примеры тестов

3
2  2 3
1  1
1  1

0 1 1

3
2  2 3
2  3 1
2  1 2

0 2 2

6
1  2
3  1 3 4
2  5 2
2  2 5
2  4 3
0

0 1 1 1 2 0

Problem J2. Hype spreading ≡

Statement

One famous car race takes place on a stadium with a racetrack. Spectators watching the race sit on a stand consisting of H rows with W seats each. During the race, some seats are occupied by spectators, and others are empty.

Marketing research demonstrated that if one spectator will loudly shout out a nicely rhymed slogan, spectators on seats located immediately to the left, right, above and below him will repeat it. Their neighbors, in turn, will catch up, and the slogan will spread throughout the stand.

An advertisement company invented a new slogan and wants it to spread among as many spectators as possible. To simulate "spontaneous" appearance of the slogan the company hired an agent who will move to one of the unoccupied seats and shout the slogan from there.

You program must determine the position of the agent which will result in maximum slogan penetration.

Input file format

Input file contains integers W H in the first line, followed by H lines of W characters each.

Each character is either a '.' (ASCII 46) or '#' (ASCII 35), denoting free and occupied seat correspondingly.

There is at least one free seat.

Output file format

Output file must contain two integers — x y, denoting seat number and row number for the agent to take. Rows are numbered starting from 1, top to bottom. Seats are numbered starting from 1, left to right. If there are several optimal solutions, output any of them.

Constraints

2 ≤ W, H ≤ 2000

Sample tests

2 2
#.
.#

2 1

5 5
..#.#
..###
#..##
#.##.
#....

2 4

6 4
######
.....#
..##.#
...#.#

3 2

Задача K1. Любители SMS ≡

Условие

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

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

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

Расположение клавиш и координаты их центров показаны на приведённой схеме:

  1 2 3   (1; 1) (1; 2) (1; 3)
  4 5 6   (2; 1) (2; 2) (2; 3)
  7 8 9   (3; 1) (3; 2) (3; 3)
    0            (4; 2)
  

Одному члену жюри требуется набрать сообщение, состоящее из N символов. Помогите ему оценить минимальное время, которое для этого потребуется. Клавиша, которую нужно нажать, чтобы ввести i-й символ сообщения, задаётся изображённой на ней цифрой a_i. В начальный момент времени палец левой руки находится на клавише 4, а палец правой руки — на клавише 6.

Рекомендуется рассмотреть частичные решения

• Минимизация расстояния на каждом шаге ведёт к минимизации ответа (жадный алгоритм)
• 1 ≤ N ≤ 20

Формат входного файла

Входной файл содержит целое число N, за которым следуют N цифр a_i.

Формат выходного файла

Выходной файл должен содержать единственное вещественное число t — минимальное время набора сообщения. Абсолютная ошибка ответа не должна превышать 10^− 3.

Ограничения

1 ≤ N ≤ 10⁵, 0 ≤ a_i ≤ 9

Примеры тестов

4
1 3 2 7

5

6
5 2 9 0 0 3

6.650281540

Задача K2. Унисон ≡

Условие

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

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

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

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

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

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

В первой строке входных данных содержатся целые числа N M: количество строк в первой и второй песне соответственно. Далее следуют N + M строк, содержащих текст первой и затем второй песни. Каждая строка может состоять только из печатных ASCII символов.

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

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

Ограничения

1 ≤ N, M ≤ 10⁶

N * M ≤ 10⁷

Длина каждой строки не превосходит 50.

Описание подзадач и системы оценивания

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

Примеры тестов

3 4
It's funny how the war goes on
Without John, without our John
La la la la la, la la!
We're so young and so gone
Let's chase the dragon from our home
Ah ah from our home!
From our home

17

Задача K3. Марфа Геннадьевна в столовой ≡

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит c_i рублей. Для каждого блюда известен также коэффициент сытости блюда — a_i.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

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

Формат входного файла

Входной файл содержит целые числа N A.

Далее следуют N пар целых чисел c_i a_i.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

Примеры тестов

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

Задача K4. В чужом пиру - похмелье ≡

Условие

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

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

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

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

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

Выведите титул победителя — "King" или "Queen" (без кавычек).

Ограничения

1 ≤ k, q, n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при k = q, получат не менее 20 баллов.

Пояснение к примеру

На пиру 13 рыцарей. Любимое число короля — 6, королевы — 4. Первым ходом король хвалит 6 рыцарей. После любых ответных ходов королевы ему нужно хвалить по одному рыцарю. Если же король первым ходом восславит одного рыцаря, то он проиграет.

Примеры тестов

13 6 4

King

Задача K5. Новогодняя ёлка-3 ≡

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

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

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 2 1
1 2
2 2

4

Задача K6. Импортозамещение ≡

Условие

Страна Битландия производит множество товаров. Соседняя страна Байтландия постоянно закупалась у Битландии.

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

Из-за этого Байтландия запустила тендер на закупку импортозамещающих товаров. Было определено k различных категорий товаров, которые пользуются спросом в стране. Каждая категория имеет свой код от 1 до k включительно. Свои товары предложили n различных компаний. Они заявили, какой тип товара предоставят, в каком количестве они его поставят и суммарную цену за всю поставку. По условиям тендера каждый товар может быть закуплен только у одной компании.

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

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

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

В следующих n строках записано по три натуральных числа t_i, a_i и c_i — код товара, количество товара и суммарную стоимость соответственно.

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

Выведите одно целое число — минимальную сумма, которую надо потратить на закупку. Если не закупку совершить невозможно, выведите -1.

Ограничения

1 ≤ n ≤ 10⁴

1 ≤ t_i ≤ k ≤ 100

1 ≤ a_i ≤ s ≤ 1000

1 ≤ c ≤ 100

Пояснение к примеру

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

Примеры тестов

7 5 8
3 2 9
4 2 4
4 4 7
3 2 2
2 4 2
1 4 10
4 3 7

8

Задача K7. Воздушный замок ≡

Условие

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

Помогите Деду Морозу постоить наибольший по объему замок.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 1
1 1 2

4

3 0

27

Задача N0. Дифтонги ≡

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

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

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

Примеры тестов

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

Problem N1. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

Задача N2. Длинный текст и много слов ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

Longlongstring
2
short
string

0 1

Задача R0. Комментарии ≡

Условие

Джон, хотя и пишет на языке С, дает файлам расширение CPP, чтобы использовать в своих программах комментарии в С++-стиле (от // до конца строки). Обычный С-комментарий, который начинается с символов "/*" и заканчивается символами "*/", Джон также иногда использует, обычно для многострочных комментариев. Для участия в конкурсе программ необходимо, чтобы программа соответствовала стандартам языка ANSI С, и Джону нужно заменить все C++-комментарии на стандартные. Для этого в C++-комментарии можно заменить "//" на "/*" и добавить "*/" в конце строки. Иногда в C++-комментарии может встретиться последовательность символов "*/", в этом случае нужно вставить пробел между двумя этими символами: "* /". К счастью внутри строковых констант в программе Джона не встречаются последовательностей "//", "/*" и "*/".

Напишите программу, которая преобразует в программе Джона C++-комментарии в C-комментарии.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( //Печать
      "Hello, world");
  return 0; //*/*
}

#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( /*Печать*/
      "Hello, world");
  return 0; /** /**/
}

Задача R1. Правильная запись номера ≡

Условие

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

Российский телефонный номер в международном формате выглядит следующим образом: +7␣код_региона␣локальный_номер. В зависимости от длины кода региона существует 4 допустимых варианта записи:

• +7␣123␣123-45-67
• +7␣1234␣12-34-56
• +7␣12345␣1-23-45
• +7␣123456␣12-34

Сотрудник отдела кадров НИИ АСМ просит Вас написать программу, конвертирующую телефонный номер в международный формат.

Формат входного файла

Входной файл содержит единственную строчку с телефонным номером.

Формат выходного файла

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

Ограничения

Каждый телефонный номер работника начинается с подстроки +7 после которой следует код региона и локальный номер. Код региона — первый блок подряд идущих цифр после +7. В качестве символов разделителя могут быть использованы пробелы (ASCII 32) и тире (ASCII 45). Код региона может быть также обрамлён круглыми скобками (ASСII 40 и ASСII 41), в этом случае символы разделителя вокруг скобок могут быть опущены.

Суммарное количество цифр в коде региона и локальном номере равно 10. Длина входной строки не превышает 25 символов.

Примеры тестов

+7 (123)456-7-890

+7 123 456-78-90

+7(9876)543 210

+7 9876 54-32-10

+7-31415 92 - 65-3

+7 31415 9-26-53