Учебная практика. Часть 1 (Б8103б, лето 2018)

Задача F. Коррекция фотоснимков ≡

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

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

Условие

Матрица фотоаппарата представляет собой прямоугольную таблицу размерности [n × m], состоящую из светочувствительных элементов (ячеек). В момент съемки каждой ячейке такой таблицы ставится в соответствие вещественное значение X_{i j}, указывающее ее состояние (интенсивность).

Известно, что при считывании состояния отдельно взятой ячейки к нему добавляется взвешенная сумма состояний окружающих ее ячеек, которые формируют упорядоченный набор слоев (см. рисунок). При этом каждый последующий слой имеет в два раза меньшее влияние, чем предыдущий.

Коэффициент влияния каждой такой ячейки на полученное значение равен 1 / (2^l ⋅ N_l), где l — номер содержащего ее слоя, N_l — число ячеек в l-м слое.

Также для отдельно взятой модели фотоаппарата известно максимальное число слоев k, оказывающих влияние на результат измерения.

Для заданной матрицы Y, полученной в результате измерений, и радиуса воздействия k требуется восстановить исходные значения X_{i j}.

Значения фиктивных ячеек (лежащих за пределами матрицы) полагаются равными нулю.

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

В начале входного файла хранятся три натуральных числа: n, m и k.
Далее следует матрица результатов измерений Y, записанная в строчном формате.

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

Выходной файл должен содержать восстановленную матрицу X.
Все значения должны быть указаны с точностью до 5-го знака после запятой.

Ограничения

0 ≤ Y_{i j} ≤ 10, 0 < n ⋅ m ≤ 40 000, 0 < k ≤ 6

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

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`9 6 3 0.26620 1.51042 0.59606 2.85301 0.76968 3.75000 1.51042 0.67130 3.09027 1.05324 4.38657 0.90856 0.59606 3.09027 1.13426 4.57754 1.29629 5.21412 2.88194 1.08217 4.61805 1.42940 5.60763 0.91435 0.87384 4.51388 1.43518 5.72916 1.08796 1.78819 4.13773 1.31944 5.72916 1.18055 2.03704 0.58449 0.98958 5.53819 1.12847 2.10648 0.76389 2.69097 4.98842 0.92592 1.98495 0.76389 2.95717 0.61343 0.49190 1.63773 0.54398 2.69097 0.61343 3.59375`	`0.00000 1.11111 0.00000 2.22222 0.00000 3.33333 1.11111 0.00000 2.22222 0.00000 3.33333 0.00000 0.00000 2.22222 0.00000 3.33333 0.00000 4.44444 2.22222 0.00000 3.33333 0.00000 4.44444 0.00000 0.00000 3.33333 0.00000 4.44444 0.00000 1.11111 3.33333 0.00000 4.44444 0.00000 1.11111 0.00000 0.00000 4.44444 0.00000 1.11111 0.00000 2.22222 4.44444 0.00000 1.11111 0.00000 2.22222 0.00000 0.00000 1.11111 0.00000 2.22222 0.00000 3.33333`

9 6 3
0.26620 1.51042 0.59606 2.85301 0.76968 3.75000
1.51042 0.67130 3.09027 1.05324 4.38657 0.90856
0.59606 3.09027 1.13426 4.57754 1.29629 5.21412
2.88194 1.08217 4.61805 1.42940 5.60763 0.91435
0.87384 4.51388 1.43518 5.72916 1.08796 1.78819
4.13773 1.31944 5.72916 1.18055 2.03704 0.58449
0.98958 5.53819 1.12847 2.10648 0.76389 2.69097
4.98842 0.92592 1.98495 0.76389 2.95717 0.61343
0.49190 1.63773 0.54398 2.69097 0.61343 3.59375

0.00000 1.11111 0.00000 2.22222 0.00000 3.33333
1.11111 0.00000 2.22222 0.00000 3.33333 0.00000
0.00000 2.22222 0.00000 3.33333 0.00000 4.44444
2.22222 0.00000 3.33333 0.00000 4.44444 0.00000
0.00000 3.33333 0.00000 4.44444 0.00000 1.11111
3.33333 0.00000 4.44444 0.00000 1.11111 0.00000
0.00000 4.44444 0.00000 1.11111 0.00000 2.22222
4.44444 0.00000 1.11111 0.00000 2.22222 0.00000
0.00000 1.11111 0.00000 2.22222 0.00000 3.33333