VIII Olimpiada Informatyczna 2000/2001
|
Zadanie: MAP
|
Autor: Tomasz Śmigielski
|
Zawody I stopnia |
Plik źródłowy: | MAP.??? (np. pas, c, cpp) |
Plik wykonywalny: | MAP.exe |
Plik wejściowy: | MAP.in |
Plik wyjściowy: | MAP.out |
Dane są:
Jeśli [i, j] i [i', j'] są dwoma miejscami w tabelce F, to odległością między nimi nazywamy liczbę max(|i - i'|, |j - j'|).
Należy obliczyć tabelkę W, n x n (do elementów tej tabelki odwołujemy się tak samo, jak do elementów tabelki F) taką, że W[i, j] jest sumą wszystkich liczb z tabelki F leżących w odległości co najwyżej r od [i, j].
Napisz program, który:
W pierwszym wierszu pliku tekstowego MAP.IN znajdują się dwie dodatnie liczby całkowite oddzielone pojedynczym odstępem: n i r, gdzie 0 <= r < n <= 250. W kolejnych n wierszach znajduje się opis tabelki F. Każdy z tych wierszy zawiera n liczb ze zbioru {0,1}, pooddzielanych pojedynczymi odstępami, i-ta liczba zapisana w j+1-szym wierszu to F[i, j].
Plik tekstowy MAP.OUT powinien zawierać dokładnie n wierszy, w j-tym wierszu powinny być zapisane kolejno wartości W[1, j]...W[n, j] pooddzielane pojedynczymi odstępami.
Dla pliku wejściowego MAP.IN:
5 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0
poprawną odpowiedzią jest plik wyjściowy MAP.OUT:
3 4 2 2 1 4 5 2 2 1 3 4 3 3 2 2 2 2 2 2 1 1 2 2 2