Задача 1. Дошкольная сортировка ≡

Условие

Когда юному программисту Васе было три года, он уже знал, что буквы бывают "маленькие" (a, b, c, ..., z) и "большие" (A, B, C, ... Z), но ещё не выучил порядок букв в алфавите.

Мама играла с Васей в игру: она выписывала последовательность маленьких и больших букв, и спрашивала, "в порядке ли они". Если в последовательности шли сначала только маленькие буквы, а потом только большие, Вася отвечал YES (как будущий программист, он уже начал учить английские слова). Если в последовательности маленькие и большие буквы были перемешаны, Вася отвечал NO.

Напишите программу, которая будет действовать как Вася.

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

Входной файл содержит строку из больших и маленьких латинских букв.

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

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

Ограничения

Длина входной строки от 1 до 10 символов.

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

maMA

YES

pRograMma

NO

zzzz

YES

AA

YES

Задача 2. Необычная сортировка ≡

Условие

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

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

Неровностью последовательности называется сумма модулей разности почти соседних элементов. Два элемента последовательности являются почти соседними, если их номера отличаются ровно на 2. Например, почти соседними элементами будут числа на позициях 1 и 3, 2 и 4, 3 и 5 и т.д.

Петя уже очень хорошо знает математику, поэтому он смог написать формулу для подсчета неровности: ∑N − 2i = 1|a_i − a_i + 2|. Теперь Петя хочет узнать минимальное значение неровности, которое можно получить для его коллекции после перестановки элементов. Вы должны ему с этим помочь.

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

Пояснение

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

Первая строка содержит одно целое число N — количество чисел в коллекции Пети.

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

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁶

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

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

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

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

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

Обратите внимание, что первый и второй примеры относятся к первой подзадаче, а третий — ко второй.

В первом примере можно расположить коллекцию вот так: 3 1 2. Тогда неровность будет равна |3 − 2| = 1.

Во втором примере нет ни одной пары почти соседних элементов.

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

3
1
2
3

1

2
1000000
1

0

5
8
2
1
9
4

4

Задача A1. Почтовый индекс ≡

Условие

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

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

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

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

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

В единственной строке через пробел записаны два неотрицательных целых числа a и b — количества прямых и наклонных линий в индексе.

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

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

Ограничения

0 ≤ a ≤ 10³

0 ≤ b ≤ 10²

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

10 1

28

5 4

Wrong

23 5

100236

Задача A5. Finite Field (Easy version) ≡

Условие

Вам необходимо написать .cpp файл с реализацией хедера num.h

В конструкторе Num необходимо сохранять значение value по модулю modulo. По умолчанию modulo равно нулю, в таком случае value сохраняется без взятия по модулю.

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

Материалы задачи

main.cpp

task.xml

num.h

Problem B. Bucket sort (LETTERS ONLY) ≡

Statement

Input file format

Output file format

Constraints

Sample tests

4
KVN
ACM
FSB
GGG

ACM
FSB
GGG
KVN

Задача C. Carriage inspectors ≡

Условие

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

В поезде N вагонов и M контролёров. На своё счастье, Вася уже давно ездит на одной и той же электричке и знает A_i — номера вагонов, где будут находиться контролёры на момент его захода в поезд. Также он знает направления движения каждого контролёра (к первому вагону или к последнему) и их скорости V_i — количество вагонов в час, которое проходит i-й контролёр. Таким образом, через каждые 1 / V_i часов контролёр переходит в следующий вагон в своём направлении. Контролёр останавливается если дальше в его направлении нет вагонов.

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

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

Первая строка входного файла содержит целые числа N и M — количество вагонов и количество контролёров соответственно.

Далее следует M строк, i-я строка содержит два целых числа A_i, V_i — вагон, в котором находится соответствующий контролёр в момент захода Васи в поезд и его скорость движения. V_i отрицательна, если контролёр движется в сторону вагона с меньшим номером, и положительна в обратном случае.

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

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

Ограничения

1 ≤ N, M ≤ 200000

1 ≤ A_i ≤ N

 − 10⁶ ≤ V_i ≤ 10⁶, V_i ≠ 0

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

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

Во втором примере вагоны 1 и 5 содержат контролёров в момент времени 0. Через 0.5 часа первый контролёр заходит в вагон 4. Через 1 час от начала поездки контролёр 1 заходит в вагон 2, а контролёр 2 заходит в вагон 3. Таким образом, как 2, так и 3 является правильным ответом.

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

3 1
2 1

1

5 2
5 -2
1 1

2

Problem C1. Heapsort ≡

Statement

A well known algorithm called heapsort is a deterministic sorting algorithm taking O(n log n) time and O(1) additional memory. Let us describe ascending sorting of an array of different integer numbers.

The algorithm consists of two phases. In the first phase, called heapification, the array of integers to be sorted is converted to a heap. An array a[1…n] of integers is called a heap if for all 1 ≤ i ≤ n the following heap conditions are satisfied:

- if 2i ≤ n then a[i] > a[2i];

- if 2i + 1 ≤ n then a[i] > a[2i + 1].

We can interpret an array as a binary tree, considering children of element a[i] to be a[2i] and a[2i + 1]. In this case the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2). In terms of trees the property of being a heap means that for each node its value is greater than the values of its children.

In the second phase the heap is turned into a sorted array. Because of the heap condition the greatest element in the heapified array is a[1]. Let us exchange it with a[n], now the greatest element of the array is at its correct position in the sorted array. This is called extract-max.

Now let us consider the part of the array a[1 ... n-1]. It may be not a heap because the heap condition may fail for i=1. If it is so (that is, either a[2] or a[3], or both are greater than a[1]) let us exchange the greatest child of a[1] with it, restoring the heap condition for i=1. Now it is possible that the heap condition fails for the position that now contains the former value of a[1]. Apply the same procedure to it, exchanging it with its greatest child. Proceeding so we convert the whole array a[1 ... n-1] to a heap. This procedure is called sifting down. After converting the part a[1 ... n-1] to a heap by sifting, we apply extract-max again, putting second greatest element of the array to a[n-1], and so on.

For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to a sorted array. Let us make the first extract-max. After that the array turns to (3, 4, 2, 1, 5). Heap condition fails for a[1] = 3 because its child a[2] = 4 is greater than it. Let us sift it down, exchanging a[1] and a[2]. Now the array is (4, 3, 2, 1, 5). The heap condition is satisfied for all elements, so sifting is over. Let us make extract-max again. Now the array turns to (1, 3, 2, 4, 5). Again the heap condition fails for a[1]; exchanging it with its greatest child we get the array (3, 1, 2, 4, 5) which is the correct heap. So we make extract-max and get (2, 1, 3, 4, 5). This time the heap condition is satisfied for all elements, so we make extract-max, getting (1, 2, 3, 4, 5). The leading part of the array is a heap, and the last extract-max finally gives (1, 2, 3, 4, 5).

It is known that heapification can be done in O(n) time. Therefore, the most time consuming operation in heapsort algorithm is sifting, which takes O(n * log (n)) time.

In this problem you have to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible. In the example above the number of exchanges is 1+1+0+0+0 = 2, which is not the maximum. (5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.

Input file format

Output file format

Constraints

Sample tests

6

6 5 3 2 4 1

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

Условие

Центральным элементом набора из 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

Задача C3. Discount season ≡

Условие

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

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

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

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

В начале входных данных указано общее количество товаров n, за которым следует n пар целых чисел: P_i — стоимость i-го товара, W_i — его вес.

Далее во входных данных следует максимальная допустимая стоимость P_max (в сумме за все заходы) и вес W_max, который может унести Вася за один заход.

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

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

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

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

Ограничения

0 < n ≤ 100, 0 < P_i ≤ P_max ≤ 100, 0 < W_i ≤ W_max ≤ 10

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

12

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

100 10

3
3 9 10 11
5 0 1 3 5 7
2 4 6

10

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

24 8

1
5 0 1 2 4 8

Задача C4. Jumps of grasshopper ≡

Условие

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

Требуется посчитать число всех различных способов, которыми сверчок может добраться из точки A в точку B, совершив при этом не более N скачков, суммарная длина которых не превосходила бы некоторое заданное L.

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

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

Во входных данных записаны четыре целых числа A, B, N и L.

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

Выходные данные должны содержать полученное число.

Ограничения

0 ≤ (B − A) ≤ 20, 1 ≤ N ≤ 40, (B − A) ≤ L ≤ 60

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

0 10 20 40

35498634

1 1 2 2

3

Problem D. Etintrof ≡

Statement

Young programmer Vasya created a two-dimensional game in Battle Royale genre. The game is played on a square field of N by N cells. Each cell is either empty (represented by '.') or occupied by wall (represented by '#').

The player is located in one of the empty cells. Every second the player can stay in place or move to an adjacent empty cell up, down, left or right. After player moves, all cells along the perimeter of the game field are removed (so field size is reduced by 2 along each axis). If the player was located on one of the removed cells, he dies.

Your program must, for each empty cell of the field, calculate maximum number of seconds the player can survive if he starts the game from that cell and plays optimally.

Input format

The first line of input contains a single integer N. The next N lines contain one string of N characters each — representation of the game field.

Output format

The output should contain N lines of N numbers, where the j-th number in the i-th line indicates the maximum survival time of a player when starting from a cell with coordinates (i, j). If the corresponding cell is not empty, output zero.

Constraints

1 ≤ N ≤ 500

Sample tests

5
.....
.....
.....
.....
.....

1 2 3 2 1 
2 3 3 3 2 
3 3 3 3 3 
2 3 3 3 2 
1 2 3 2 1 

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

1 1 3 1 1 
1 0 3 0 1 
3 3 3 3 3 
1 0 3 0 1 
1 1 3 1 1 

Problem F. Fast Dijkstra ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Задача G1. Разбиение на пары ≡

Условие

Космические археологи обнаружили на планете в соседней звездной системе n древних артефактов, которые они пронумеровали от 1 до n. Каждый артефакт имеет k различных параметров, каждый параметр характеризуется целым числом. Артефакт i имеет параметры a_i,1, a_i,2, …, a_i,k. Оказалось, что первые параметры у всех артефактов различны: для всех i ≠ j выполнено a_i,1 ≠ a_j,1, при этом другие параметры у артефактов могут совпадать.

Учёные также обнаружили текст, в соответствии с которым для активации артефактов их необходимо особым образом разбить на пары и совместить. Разбиение артефактов на пары является корректным, если для каждого t от 1 до k можно выбрать такое число b_t, что оно лежит на отрезке между значениями t-го параметра артефактов каждой пары. То есть, если артефакты i и j образуют пару, должно выполняться условие a_i,t ≤ b_t ≤ a_j,t или условие a_i,t ≥ b_t ≥ a_j,t.

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

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

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

В первой строке заданы целые числа n и k — количество артефактов и количество параметров.

В следующих n строках задано по k целых чисел a_i,1, a_i,2, …, a_i,k — параметры артефактов.

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

Выведите NO, если требуемого разбиения на пары не существует.

В противном случае выведите YES в первой строке. Далее выведите n / 2 строк, в каждой строке выведите по два числа — номера артефактов, из которых следует составить пару. Каждый артефакт должен быть выведен ровно один раз.

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

Ограничения

2 ≤ n ≤ 2 ⋅ 10⁵, n чётно, 1 ≤ k ≤ 7

 − 10⁹ ≤ a_i,j ≤ 10⁹, все значения a_i,1 различны

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

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

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

В первом примере пары имеют следующие параметры (8,6) − (3,1), (1,5) − (7,2), (6, 3) − (4,7). При указанном разбиении на пары подойдут, например, значения b₁ = 4, b₂ = 4,

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

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

YES
1 4
2 6
3 5

4 3
1 -1 -1
2 1 1
3 -1 1
4 1 -1

NO

Задача G2. Максимальный поток (несколько истоков и стоков) ≡

Условие

Требуется найти максимальный поток в сети с несколькими истоками и стоками.

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

В первой строке входного файла содержится число N  — количество вершин в сети. Далее следует N чисел a_i ∈ 0, 1, 2. Если a_i = 0, то i-ая вершина  — это обычный узел; если a_i = 1 то i-ая вершина  — это исток; если a_i = 2 то i-ая вершина  — это сток. Гарантируется, что в сети есть хотя бы один исток и хотя бы один сток.

Далее следует матрица целых чисел U размером N × N. 0 ≤ U_ij ≤ 10⁶  — вместимость ребра из i-ой вершины в j-ую. На диагонали матрицы находятся нули.

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

В выходной файл выведите единственное число  — объем максимального потока.

Ограничения

2 ≤ N ≤ 50

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

2
1 2
0 100
1000 0

100

4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0

3

10
0 0 1 0 1 2 2 0 2 0 
0 100 0 0 0 1 0 0 0 0
0 0 0 0 0 120 0 0 0 0
100 0 0 0 0 0 0 0 0 0
10 10 0 0 0 0 0 20 0 20
0 0 0 50 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 15 0 15 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 10 0 0

141

Задача G3. Полезные ископаемые ≡

Условие

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

Участок поверхности планеты, на котором планируется добывать полезные ископаемые, представляет собой клетчатый прямоугольник размером w на h, клетки участка имеют координаты от (1, 1) до (w, h). В некоторых клетках участка находятся базы специалистов, в которые могут быть доставлены партии роботов. Всего на участке размещено s баз, и i-я база находится в клетке с координатами (x_i, y_i).

Каждая партия роботов характеризуется тремя параметрами: j-я партия доставляется на базу b_j, содержит n_j роботов и каждый робот партии обладает мобильностью m_j.

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

Рис. 1. Возможные перемещения робота в восьми направлениях.

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

Руководством проекта получена информация о t партиях роботов, которые могут быть последовательно отправлены на планету. После доставки всех партий роботов, учитывая их ограниченную мобильность, возможна ситуация, что не удастся разместить роботов на участке так, чтобы в каждой клетке оказалось не больше q роботов. Поэтому руководство должно выбрать k первых партий роботов, где 0 ≤ k ≤ t, которые будут полностью доставлены на соответствующие базы. После этого, если k < t, следует дополнительно принять z из n_k + 1 роботов следующей, (k + 1)-й партии, 0 ≤ z < n_k + 1.

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

Требуется написать программу, которая по размерам участка, числу q, описанию расположения баз, а также количеству запланированных партий роботов и их описанию определяет максимальное число k — количество партий роботов, и затем – максимальное число z – дополнительное количество роботов из (k + 1)-й партии, чтобы, доставив роботов на планету, их можно было разместить на участке таким образом, чтобы в каждой клетке оказалось не более q роботов.

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

Первая строка входного файла содержит числа w, h, s и q. Последующие s строк содержат по два целых числа x_i, y_i и описывают базы специалистов (1 ≤ x_i ≤ w, 1 ≤ y_i ≤ h).

Следующая строка содержит число t — количество партий роботов. Последующие t строк описывают партии роботов и содержат по 3 целых числа: b_j, n_j и m_j (1 ≤ b_j ≤ s, 1 ≤ n_j ≤ w × h × q, 0 ≤ m_j < max(w, h)).

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

Требуется вывести два числа: k и z, 0 ≤ k ≤ t. Если k = t, то z должно быть равно 0, иначе должно выполняться условие 0 ≤ z < n_k + 1.

Ограничения

1 ≤ w, h ≤ 10⁵, 1 ≤ s ≤ 4, 1 ≤ q ≤ 100, 1 ≤ t ≤ 100,

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

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

Рис. 2. Возможное размещение роботов на участке в данном примере.

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

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

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

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

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

4 3 2 1
1 1
3 2
3
1 4 1
2 9 1
1 12 2

1 7

Задача G4. Минимальное контролирующее множество ≡

Условие

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

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

В первой строке файла даны два числа m и n (1 ≤ m, n ≤ 4 000) — размеры долей. Каждая из следующих m строк содержит список ребер, выходящих из соответствующей вершины первой доли. Этот список начинается с числа K_i (0 ≤ K_i ≤ n) — количества ребер, после которого записаны вершины второй доли, соединенные с данной вершиной первой доли, в произвольном порядке. Сумма всех K_i во входном файле не превосходит 500 000.

Последняя строка файла содержит некоторое максимальное паросочетание в этом графе — m чисел 0 ≤ L_i ≤ n — соответствующая i-й вершине первой доли вершина второй доли, или 0, если i-я вершина первой доли не входит в паросочетание.

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

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

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

Третья строка содержит описание вершин второй доли в аналогичном формате.

Ограничения

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

3 2
2 1 2
1 2
1 2
1 2 0

2
1 1
1 2

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

Условие

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

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача K. Ближайшее число ≡

Условие

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

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

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

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

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача L. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Задача M. Вася и Суперкомпьютер ≡

Условие

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

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

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

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

Первая строка входного файла содержит число N - количество записей в логе

Следующие N строк содержат число M_i - количество заданий, выполненное в какой-то день, и строку S_i длины M_i, состоящую из символов 0 и 1 - описание выполненных в этот день заданий

Записи лога идут не по хронологическому порядку. Некоторые записи могут оказаться лишними.

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

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

Ограничения

Суммарная длина S_i не превышает 5 ⋅ 10⁵

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

6
4 1111
3 100
5 00101
2 00
10 1001010110
2 01

26

6
3 100
5 10100
2 11
6 011101
3 110
2 10

16

Задача M2. Митинг (две характеристики) ≡

Условие

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

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно m_j > m_i, p_j > p_i.

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

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

Входной файл содержит натуральное число n  — количество персонажей. Далее следует n двоек натуральных чисел m_i p_i.

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

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i ≤ 10⁹

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

4
2 3 
1 1 
2 1 
3 2

1 4

Задача M3. Митинг ≡

Условие

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

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

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

Входной файл содержит натуральное число n  — количество персонажей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача N. Дерево ≡

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

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

Условие

На шашечной доске размером 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

Задача P. КПК ≡

Условие

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

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

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

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

Ограничения

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

3 1
2 3

1
2 3
1
1 2

Задача Q. Количество инверсий последовательнсти ≡

Условие

Пара элементов (A_i, A_j) последовательности A_N называется инверсией, если A_i > A_j и i < j.

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

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

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

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

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

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10⁹

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

7 1 2 5 9 13 16 20

0

9
1 1 2 3 8 6 1 9 9

5

Задача S. Конвертер графов ≡

Условие

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

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

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

Начиная со второй строки в файле содержится описание графа в одном из следующих форматов

• edges — список ребер. В этом случае первая строка описания графа должна содержать два целых числа N, M — количество вершин и количество ребер соответственно. Далее каждая следующая строка содержит два числа u и v — начало и конец очередного ребра.
• lists — списки смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее i-я строка (начиная со второй) содержит описание списка смежности (i − 1)-й вершины. Первое целое число в строке c_i — количество вершин, в которые выходят ребра из (i − 1)-й вершины. Далее через пробел следует c_i целых чисел — номера вершин, в которые выходят ребра из (i − 1)-й.
• mat — матрица смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее следует N строк по N чисел 0 или 1 — описание матрицы смежности. Если в i-й строке на j-й позиции находится единичка, значит в графе есть ребро из (i − 1)-й вершины в j-ю.

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

Выходной файл должен содержать описание графа в требуемом формате.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N²

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

edges mat
3 4
1 2
2 3
1 3
2 2

3
0 1 1
0 1 1
0 0 0

mat lists
4
1 0 1 1
0 0 0 0
1 1 0 0
0 1 1 0

4
3 1 3 4
0
2 1 2
2 2 3

Задача T. Максимум в скользящем окне ≡

Условие

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

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Задача U. Топологическая сортировка ≡

Условие

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

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

Ограничения

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

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

2 4 3 5 6 1