Задача A. Ближайшее число - 1

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

Условие

Дан массив A, состоящий из N неотрицательных целых чисел.

Назовём правым (левым) соседом нулевого элемента ближайший к нему справа (слева) ненулевой элемент.

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

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

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

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

Выходной файл должен содержать N целых чисел — элементы массива B.

Ограничения

1 ≤ N ≤ 10000, 0 ≤ Ai ≤ 10000

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

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

Задача B. Обход матрицы: спиральный обход

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

Условие

По данному числу N требуется заполнить квадратную матрицу размером NxN целыми числами от 1 до N2; следующим образом:

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

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

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

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

Ограничения

1 <= N <= 100

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

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

Задача C. Три буквы

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

Условие

Дана текстовая строка, состоящая из заглавных латинских букв. Требуется найти подстроку из трёх букв, которая встречается в данной строке чаще всего. Например, в строке DEFDEFABCABCZABCDEFDEF чаще всего (4 раза) встречается подстрока DEF.

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

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

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

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

Ограничения

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

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

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

Задача D. k-я порядковая статистика

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ K ≤ N, 231 ≤ Ai ≤ 2311

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

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

Задача E. Куча максимумов

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

Условие

Из данных N чисел необходимо выбрать K наибольших и вывести их в порядке возрастания.

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

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

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ K ≤ min(N, 105), 231 ≤ Ai ≤ 231

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

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

Задача F. Модули

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

Условие

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

Когда все программисты сдали в отдел свою работу, выяснилось, что некоторым модулям для правильного функционирования требуются другие модули, при этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый. Вам, как одному из программистов отдела, поручено написать программу, которая по сведениям о связях между модулями определила бы, сколько минимальных программ можно из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.

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

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

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

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

Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 106

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

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

0.109s 0.004s 21