training_2005_11_17 - условия

Задача A. Произведения ≡

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

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

Условие

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

Дана квадратная таблица $N \times N$ . Рядом с каждым столбцом и каждой строкой написано целое положительное число. Пусть около $i$ -го столбца написано число $X_i$ , а около $j$ -й строки - число $Y_j$ . Для победы в конкурсе необходимо в некоторых клетках таблицы расположить целые положительные числа так, чтобы выполнялись следующие условия:

Все эти числа должны быть различными. В каждом столбце и каждой строке должно быть ровно 2 числа. Произведение чисел $i$ -го столбца должно быть равно $X_i$ . Произведение чисел $j$ -й строки должно быть равно $Y_j$ .

Рисунок показывает пример решения такой задачи.

54	6	12	20	88
6	3				18
9		1			9
		12		11	132
			4	8	32
	2		5		10

Помогите Пете!

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

На первой строке входного файла находится число

$N$ . На второй строке находится

$N$ чисел —

$X_1, \dots,\,X_N$ . На третьей строке также находится

$N$ чисел -

$Y_1, \dots,\,Y_N$ .

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

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

$M$ чисел первой строки, затем

$N$ чисел второй строки, и т. д. Если в соответствующей клетке стоит число, следует вывести это число, если клетка осталась пустой, следует вывести 0. Все числа в выходном файле следует разделять пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если решений несколько, выведите любое из них. Гарантируется, что хотя бы одно решение будет существовать.

Ограничения

$2 \le N \le 10$ ,

$1 \le X_i,\,Y_i \le 10000$

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`2 2 12 3 8`	`1 3 2 4`
2	`3 5 8 18 2 30 12`	`1 2 0 5 0 6 0 4 3`
3	`5 54 6 12 20 88 18 9 132 32 10`	`6 3 0 0 0 9 0 1 0 0 0 0 12 0 11 0 0 0 4 8 0 2 0 5 0`

Задача B. Длинный спуск (45 баллов) ≡

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

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

Условие

Рельеф горного массива представлен матрицей размером NxN, с элементами, задающими высоту участков местности. Лыжник желает найти самый длинный спуск, т.е. такую строго убывающую последовательность соседних по вертикали или горизонтали элементов a_i1,j1 > a_i1,j1 > … > a_iL,jL, что значение L (длина последовательности) — максимально возможное.

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

Входной файл содержит число N, за которыми следует N² чисел a_1,1 a_1,2 … a_1,N a_2,1 a_2,2 … a_2,N … a_N,N. Все числа — целые.

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

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

Ограничения

1 ≤ N ≤ 1000, 0 ≤ a_i,j ≤ 10⁶.

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

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