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

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

Условие

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

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

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

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

63   18
9 1  9
  12 11132
   4832
 2 5 10
546122088 
Помогите Пете!

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

На первой строке входного файла находится число N. На второй строке находится N чисел — X1, …, XN. На третьей строке также находится N чисел - Y1, …, YN.

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

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

Ограничения

2 ≤ N ≤ 10, 1 ≤ Xi, Yi ≤ 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, с элементами, задающими высоту участков местности. Лыжник желает найти самый длинный спуск, т.е. такую строго убывающую последовательность соседних по вертикали или горизонтали элементов ai1,j1 > ai1,j1 > … > aiL,jL, что значение L (длина последовательности)  — максимально возможное.

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

Входной файл содержит число N, за которыми следует N2 чисел a1,1 a1,2 … a1,N a2,1 a2,2 … a2,N … aN,N. Все числа — целые.

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

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

Ограничения

1 ≤ N ≤ 1000, 0 ≤ ai,j ≤ 106.

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

№ Входной файл (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
0.022s 0.004s 9