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

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
maMA
YES
2
pRograMma
NO
3
zzzz
YES
4
AA
YES

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

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Пояснение

Модулем числа называется его абсолютное значение. Например, модулем числа 2 является 2, а модулем числа  − 3 является число 3. Обозначается модуль как |x|.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ ai ≤ 106

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

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

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
N
1301 ≤ N ≤ 3
2251 ≤ N ≤ 101
3351 ≤ N ≤ 1031-2
4101 ≤ N ≤ 1051-3

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

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

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

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

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

Стандартный вход Стандартный выход
1
3
1
2
3
1
2
2
1000000
1
0
3
5
8
2
1
9
4
4

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

Автор:Антон Карабанов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

Ограничения

0 ≤ a ≤ 103

0 ≤ b ≤ 102

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

Стандартный вход Стандартный выход
1
10 1
28
2
5 4
Wrong
3
23 5
100236

Problem A5. Finite Field (Easy version)

Input file:Standard input   Time limit:5 sec
Output file:Standard output   Memory limit:512 Mb

Statement

You are to create .cpp file with implementation of num.h

Constructor of Num should store value modulo modulo. By default, modulo is equal to 0. In that case modulo operation should not be applied to value.

Copy constructor should only copy value value. modulo must be set to zero in copy constructor.

Materials

main.cpp

task.xml

num.h


Problem B. Bucket sort (LETTERS ONLY)

Author:StdAlg   Time limit:3 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of words and sorts it in lexicographical order. Linear order on characters is given by ASCII codes.

Input file format

First line of input file contains integer N — the sequence length. Following N lines contain one word per line. Each word is exactly three letters long.

Output file format

Output file must consist of N lines, each containing one word from sorted sequence.

Constraints

0 ≤ N ≤ 1000000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
KVN
ACM
FSB
GGG
ACM
FSB
GGG
KVN

Problem C. Carriage inspectors

Author:M. Sporyshev, I. Tuphanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Programmer Vasya commutes to work by train every day. Vasya came to the train station today as usual, but forgot his wallet! There is no time to get back. Vasya decided to take the train without buying a ticket. Obviously, he wouldn't be happy to meet an inspector now.

The train consists of N carriages served by M inspectors. Luckily, Vasya always takes this train and knows Ai — numbers of carriages where inspectors are located at the moment he enters the train. He also knows the direction (toward the first or toward the last carriage) of each inspector and his (or her) speed Vi — the number of carriages that the inspector passes per hour. Thus every 1 / Vi hours the inspector moves to the next carriage in his (or her) direction. The inspector stops if there is no next carriage in that direction.

The trip to work is long, so Vasya wants to pick a carriage where he could stay as long as possible until the moment when an inspector shows up in his carriage. Help Vasya with this.

Input file format

First string of the input contains integers N and M — the number of carriages and the number of inspectors accordingly.

Then M lines follow, i-th line contains integers Ai, Vi — carriage number where the inspector i is located when Vasya gets on the train, and his (or her) speed. Vi is negative if the inspector is moving toward the first carriage, and positive otherwise.

Output file format

Output the number of carriage which Vasya should get in to. Carriages are numbered from 1. If there are multiple solutions, output any of them.

Constraints

1 ≤ N, M ≤ 200000

1 ≤ Ai ≤ N

 − 106 ≤ Vi ≤ 106, Vi ≠ 0

Note on samples

In the first sample input Vasya can stay in the carriage number 1 as long as he wants.

In the seconds sample input there are inspectors in carriages 1 and 5 at time 0. After 0.5 hours inspector 1 enters carriage 4. After 1 hour from the beginning of the ride, inspector 1 enters carriage 2, while inspector 2 enters carriage 3. Thus, both 2 and 3 are correct answers.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 1
2 1
1
2
5 2
5 -2
1 1
2

Problem C1. Heapsort

Author:Andrew Stankevich (original idea, text, solution)   Time limit:2 sec
Input file:heapsort.in   Memory limit:64 Mb
Output file:heapsort.out  

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

Input file contains n.

Output file format

Output the array containing n different integer numbers from 1 to n, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible. Separate numbers by spaces.

Constraints

1 ≤ n ≤ 50000

Sample tests

No. Input file (heapsort.in) Output file (heapsort.out)
1
6
6 5 3 2 4 1

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

Автор:И. Бураго   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 106,  − 109 ≤ ai ≤ 109.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 3 4
5 3 4
2
5
1 2 3 2 4
1 1 2 2 2

Problem C3. Discount season

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Vasya has heard that the discount season has started in a shop nearby.

For a single visit to the shop buyer tries to purchase as many items as possible with total weight not greater than Wmax, to be able to carry them out with him. There is just one item of every type in the shop. According to discount rules, one client is allowed no more than 3 visits.

You must write a program to calculate optimal sequence of purchases allowing to buy maximum number of items. Total cost of all items must not exceed Pmax — the amount of money Vasya has. If several variants with maximum number of items exist, choose one with minimal number of visits.

Input format

Input starts with total number of items n, followed by n pairs of integers: Pi — price of i-th item, Wi — its weight.

Next in the input data are maximum allowed amount of money Pmax (total for all visits) and Wmax — maximum weight Vasya is able to carry in each visit.

Output format

Output must contain optimal sequence of purchases, described as follows.

First, a total number of visits Vasya has no make. Then for each visit: count of items purchased, followed by item numbers in any order. Items are numbered starting from zero.

If there are several optimal solutions, output any of them.

Constraints

0 < n ≤ 100, 0 < Pi ≤ Pmax ≤ 100, 0 < Wi ≤ Wmax ≤ 10

Sample tests

No. Standard input Standard output
1
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
2
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

Problem C4. Jumps of grasshopper

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Grasshopper moves along number line by jumps of integer length. It can jump both to positive and negative directions. Length of each jump can't equal zero.

It is required to calculate count of all different ways that grasshopper can get from point A to point B making at most N jumps,
whose total length shouldn't exceed some given L.

Since obtained count may be very great, remainder of its division by 109 expected as answer.

Input format

Input data contains four integer numbers A, B, N и L.

Output format

Output data must contain obtained number.

Constraints

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

Sample tests

No. Standard input Standard output
1
0 10 20 40
35498634
2
1 1 2 2
3

Problem D. Etintrof

Author:A. Klenin, I. Blinov   Time limit:3 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

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

No. Standard input Standard output
1
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 
2
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

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted directed graph and finds all distances from fixed vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its arcs.

Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be &minus;1.

Constraints

1 &le; N, M &le; 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

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

Автор:Центральная предметно-методическая комиссия   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

 − 109 ≤ ai,j ≤ 109, все значения ai,1 различны

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1102 ≤ n ≤ 10полная
272 ≤ n ≤ 2 ⋅ 105, k = 1первая ошибка
3152 ≤ n ≤ 2 ⋅ 105,
для всех t все ai, t различны
2первая ошибка
4152 ≤ n ≤ 2 ⋅ 105, 1 ≤ k ≤ 22первая ошибка
5262 ≤ n ≤ 400, 1 ≤ k ≤ 71первая ошибка
6272 ≤ n ≤ 2 ⋅ 105, 1 ≤ k ≤ 71, 2, 3, 4, 5первая ошибка

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

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

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

Стандартный вход Стандартный выход
1
6 2
8 6
1 5
6 3
3 1
4 7
7 2
YES
1 4
2 6
3 5
2
4 3
1 -1 -1
2 1 1
3 -1 1
4 1 -1
NO

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

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 50

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
0 100
1000 0
100
2
4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0
3
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. Полезные ископаемые

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:mining.in   Ограничение памяти:256 Мб
Выходной файл:mining.out  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ w, h ≤ 105, 1 ≤ s ≤ 4, 1 ≤ q ≤ 100, 1 ≤ t ≤ 100,

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

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

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

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

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
w, hsq
1181 ≤ w, h ≤ 20s = 1q = 1
2121 ≤ w, h ≤ 201 ≤ s ≤ 2q = 11
3 91 ≤ w, h ≤ 201 ≤ s ≤ 3q = 11, 2
4101 ≤ w, h ≤ 201 ≤ s ≤ 31 ≤ q ≤ 1001, 2, 3
5151 ≤ w, h ≤ 105s = 11 ≤ q ≤ 1001
6361 ≤ w, h ≤ 1051 ≤ s ≤ 41 ≤ q ≤ 1001, 2, 3, 4, 5

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

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

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

Входной файл (mining.in) Выходной файл (mining.out)
1
4 3 2 1
1 1
3 2
3
1 4 1
2 9 1
1 12 2
1 7

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

Автор:std.alg   Ограничение времени:2 сек
Входной файл:minimal.in   Ограничение памяти:256 Мб
Выходной файл:minimal.out  

Условие

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

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

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

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

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

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

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

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

Ограничения

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

Входной файл (minimal.in) Выходной файл (minimal.out)
1
3 2
2 1 2
1 2
1 2
1 2 0
2
1 1
1 2

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

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1 3 0
1 2 3
2
5 -1 6 -5 5 0
5 6

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

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

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

Автор:А. Шавлюгин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Входной файл содержит целые числа N M, за которыми следуют N чисел ai — жажда i-го ученика.

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

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

Ограничения

1 ≤ N, M ≤ 105

0 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
9 30
0
2
4 3
0 101 5 12
7

Problem M. Вася и Суперкомпьютер

Author:Ю. Михалев   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Programmer Vasya decided to become a man, who solved most problems. To make his wish come true he invented a Supercomputer, which could do next tasks: generate a random problem (0) and solve a random problem (1) instead of Vasya (the problem may not be generated by the first task - Vasya already had an unlimited list of problems to solve).

Unfortunately, implementation features didn't allow to keep the Supercomputer on all day long: every day it could do limited number of tasks. Furthermore, every day the supercomputer must start with the task of the same type, which he ended previous day (first day could be started with any task).

So, Supercomputer worked several days and then broke down. In Supercomputer's log Vasya found that all records are shuffled and there are extra records, which don't belong to this log. You should help Vasya to count maximum count of completed tasks that Supercomputer could do before crash.

Input format

The first line of the input file contains one number N - number of records in the log

Following N lines contains number Mi - number of tasks, completed in some day, and a string Si of Mi characters 0 and 1 - description of tasks, completed in that day.

Log records are not chronologically ordered. Some records could be excess.

Output format

The output file must contain one number - maximum number of tasks, which Supercomputer could do before the crash.

Constraints

Total length of all Si does not exceed 5 ⋅ 105

Sample tests

No. Standard input Standard output
1
6
4 1111
3 100
5 00101
2 00
10 1001010110
2 01
26
2
6
3 100
5 10100
2 11
6 011101
3 110
2 10
16

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

Автор:mesenev   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно mj > mi, pj > pi.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 
1 1 
2 1 
3 2
1 4

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

Автор:Виртуальная реальность   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно mj > mi, pj > pi, tj > ti.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi, ti ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 4
1 1 3
2 1 8
3 2 10
1 4

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

0 ≤ m ≤ 105

1 ≤ ui, vi ≤ n

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
1 3
YES
2
3 3
1 2
2 3
3 1
NO

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

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

В первой строке входного файла содержится число N. В следующих N строках — описание позиции, состоящее из символов '.' (точка), 'O' (заглавная латинская О),'X' (заглавная латинская X). Они определяют пустую клетку, белую шашку и черную шашку соответственно.

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

В выходном файле должна содержаться единственная строка вида L1 N1 − L2 N2 − … − LK NK, где K ≥ 1, или Impossible если взятие невозможно.

Ограничения

1 ≤ N ≤ 12

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
.....
.O.O.
....X
.O.O.
X....  
e3-c1-a3-c5-e3  
2
4
X...
....
....
...O  
Impossible

Задача P. КПК

Автор:И. Олейников, Т. Чистяков   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за которыми следуют M пар чисел ai aj, означающие, что i-ая и j-ая микросхемы соединены проводом. Ток по проводу может течь в любом направлении.

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

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

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
1
2 3
1
1 2

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

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 105

0 ≤ Ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 1 2 5 9 13 16 20
0
2
9
1 1 2 3 8 6 1 9 9
5

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

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
edges mat
3 4
1 2
2 3
1 3
2 2
3
0 1 1
0 1 1
0 0 0
2
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. Максимум в скользящем окне

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

|ai| ≤ 109

0 ≤ m ≤ 2n − 2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
-3 -2 -1 0
6
RRRLLL
-2 -1 0 0 0 0
2
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. Топологическая сортировка

Автор:Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков   Ограничение времени:7 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

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

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

Сначала указывается количество вершин V и количество ребер E. Далее перечисляется E пар вершин (vi, vj), задающих ребра. Никакая пара вершин не встречается дважды.

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

Необходимо перечислить V вершин в описанном порядке.

Ограничения

1 <= V <= 1000000, 0 <= E <= 1000000
1 <= vi <= V

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 5
2 3
4 6
3 1
5 1
2 5
2 4 3 5 6 1

1.367s 0.012s 83