training_2005_11_26 - условия

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

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10000, 0 ≤ A_i ≤ 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 до N²; следующим образом:

в левом верхнем углу находится число 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. Три буквы ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	А. Кленин	Ограничение времени:	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 ≤ 10⁶, 1 ≤ K ≤ N,  − 2³¹ ≤ A_i ≤ 2³¹ − 1

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

№	Входной файл (`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 ≤ 10⁶, 1 ≤ K ≤ min(N, 10⁵),  − 2³¹ ≤ A_i ≤ 2³¹

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

№	Входной файл (`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 пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

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

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

Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 10⁶

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

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