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

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

0 < n ⋅ m ≤ 40000, 0 < k ≤ 6

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 6 3
5.37440 1.87298 5.08681 5.09439 3.57315 3.55082
4.84972 5.78076 5.88345 5.75286 2.34798 2.47103
3.86090 6.57539 3.56487 6.79445 2.32794 1.16099
2.87753 3.34932 6.59350 5.05354 3.07699 2.10780
5.02344 5.31951 6.03288 2.75002 2.86035 3.99470
5.33926 2.95632 5.48640 4.94406 6.01522 1.82400
1.96623 4.91699 6.77083 6.70678 3.62880 1.38931
2.07507 5.79116 6.66805 4.14477 5.60571 1.57956
2.96721 1.63348 2.82736 3.08427 4.54261 3.77225
4.54131 0.26822 3.63874 3.75977 2.43927 2.94755
3.49550 3.85922 3.75414 3.92569 0.66599 1.63885
2.38207 4.58287 1.01207 4.86523 0.65718 0.26808
1.29046 1.08997 4.35343 3.08341 1.48435 1.14364
3.72711 3.21447 3.97145 0.44224 1.13006 2.95406
4.03403 0.67137 3.22229 2.67277 4.43113 0.66156
0.62032 2.92664 4.52078 4.37446 1.85234 0.18678
1.01331 4.23441 4.76965 2.02538 4.09963 0.42683
2.29344 0.39009 1.51680 1.64687 3.47349 3.00115

0.145s 0.023s 17