selection_2004_10_26

Problem A. Nearest number - 2 ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	5 sec
Input file:	input.txt	Memory limit:	200 Mb
Output file:	output.txt

Statement

Input is the matrix A of N by N non-negative integers.

A distance between two elements A_i j and A_p q is defined as |i − p| + |j − q|.

Your program must replace each zero element in the matrix with the nearest non-zero one. If there are two or more nearest non-zeroes, the zero must be left in place.

Input file format

Input file contains the number N followed by N² integers, representing the matrix row-by-row.

Output file format

Output file must contain N² integers, representing the modified matrix row-by-row.

Constraints

1 ≤ N ≤ 200, 0 ≤ A_i ≤ 1000000

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`3 0 0 0 1 0 2 0 3 0`	`1 0 2 1 0 2 0 3 0`

Задача B. Неточные подстроки ≡

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

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

Условие

Будем говорить, что строки a и b имеют k различий, если длины этих строк одинаковы, а символы в позициях с одинаковыми номерами совпадают все, кроме k штук. Например, строки ABABAC и BBABAB имеют 2 различия.

По данной строке S длиной N символов и числу k требуется найти две подстроки одинаковой длины, начинающиеся с различных позиций, и имеющие не более k различий.

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

Входной файл содержит в первой строке целое число k, в во второй — строку S.

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

Выходной файл должен содержать целое число — длину самой длинной найденной подстроки, либо 0 (ноль), если решения не существует.

Ограничения

Строка S состоит из заглавных латинских букв.

0 ≤ k ≤ N ≤ 1000

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

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