Задача A. Ближайшее число - 1
Условие
Дан массив 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. Обход матрицы: спиральный обход
Условие
По данному числу
N требуется заполнить квадратную матрицу размером
Nx
N
целыми числами от 1 до N
2; следующим образом:
- в левом верхнем углу находится число 1
- далее числа располагаются по спирали, закрученной вправо и внутрь
Формат входного файла
Входной файл содержит целое число
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. Три буквы
Условие
Дана текстовая строка, состоящая из заглавных латинских букв.
Требуется найти подстроку из трёх букв, которая встречается в данной
строке чаще всего. Например, в строке DEFDEFABCABCZABCDEFDEF
чаще всего (4 раза) встречается подстрока DEF.
Формат входного файла
Входной файл содержит текстовую строку.
Формат выходного файла
Выходной файл должен содержать единственное число —
количество вхождений самой часто встречающейся подстроки из трёх букв.
Ограничения
Длина исходной строки от
3 до
1000000 символов.
Примеры тестов
№ |
Входной файл (input.txt ) |
Выходной файл (output.txt ) |
1 |
DEFDEFABCABCZABCDEFDEF
|
4
|
Задача D. k-я порядковая статистика
Условие
K-й порядковой статистикой N-элементного массива называется число Аk,
которое будет стоять на K-м месте после сортировки этого массива
по возрастанию.
Формат входного файла
Входной файл содержит числа
N K, за которыми следуют
N чисел — массив для которого следует подсчитать
K-ю порядковую
статистику.
Формат выходного файла
Выходной файл должен содержать
K-ю порядковую статистику исходного
массива.
Ограничения
1 ≤ N ≤ 106,
1 ≤ K ≤ N,
−231 ≤ Ai ≤ 231−1
Примеры тестов
№ |
Входной файл (input.txt ) |
Выходной файл (output.txt ) |
1 |
3 2
2 3 1
|
2
|
Задача E. Куча максимумов
Условие
Из данных
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. Модули
Условие
Отдел инновационных технологий фирмы "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
|