Mapka w kratkę
Limit pamięci: 32 MB
Mapa Bajtocji, wraz z naniesionymi południkami i równoleżnikami, tworzy prostokąt
o wymiarach ( to jego wysokość, a - szerokość).
Równoleżniki są oznaczone na mapie poziomymi liniami, ponumerowanymi od do , zaś pionowe południki mają numery od do
(patrz obrazek na drugiej stronie treści zadania).
Prognozowanie pogody w Bajtocji jest zadaniem niełatwym. Dla każdego obszaru jednostkowego
(tj. leżącego pomiędzy sąsiednimi południkami i równoleżnikami) wiemy, jak długo bajtocki
komputer meteorologiczny będzie obliczał prognozę. Uwarunkowania topograficzne powodują, że czas ten może być różny dla różnych obszarów.
Dotychczas prognoza pogody przygotowywana była w najprostszy możliwy sposób: jeden komputer obliczał prognozę kolejno
dla wszystkich obszarów jednostkowych. Obliczenie prognozy pogody dla całej Bajtocji zajmowało więc tyle
czasu, ile wynosi suma wszystkich czasów obliczeń dla poszczególnych obszarów.
Zostałeś poproszony o opracowanie nowego systemu przeznaczonego na komputer wieloprocesorowy.
Aby rozdzielić obliczenia pomiędzy procesory, teren Bajtocji należy podzielić, poprzez
wybór równoleżników i południków, na mniejszych obszarów.
Każdy z procesorów będzie obliczał pogodę dla jednego prostokąta z tego podziału, przetwarzając
kolejno obszary jednostkowe.
Wszystkie procesory pracować będą jednocześnie.
Cała prognoza pogody będzie gotowa, gdy tylko ostatni procesor zakończy swoją pracę.
Twoim zadaniem jest wyznaczenie minimalnego możliwego czasu obliczenia całej
prognozy pogody, odpowiadającego jakiemuś wyborowi równoleżników
i południków.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia rozmiary mapy Bajtocji, liczbę południków i równoleżników oraz czasy liczenia prognozy
pogody dla poszczególnych obszarów jednostkowych,
- wyznaczy minimalny czas potrzebny na obliczenie prognozy pogody,
- wypisze znaleziony wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera cztery liczby całkowite , , i , pooddzielane pojedynczymi
odstępami (, ).
Kolejne wierszy zawiera czasy liczenia prognozy pogody dla poszczególnych obszarów jednostkowych.
-ta liczba w -szym wierszu reprezentuje - czas potrzebny do obliczenia
prognozy pogody dla obszaru pomiędzy -szym a -tym równoleżnikiem oraz pomiędzy
-szym a -tym południkiem
(, , ).
Dodatkowo, w testach wartych sumarycznie 40% punktów, i nie przekroczą .
Wyjście
Twój program powinien wypisać dokładnie jeden wiersz zawierający jedną liczbą całkowitą - optymalny
czas obliczenia prognozy pogody.
Przykład
Dla danych wejściowych:
7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0
poprawną odpowiedzią jest:
31
Drugi i czwarty równoleżnik oraz czwarty południk dzielą Bajtocję na 6 obszarów, dla których
czasy liczenia prognozy pogody to: 21, 13, 27, 27, 17, 31.
Czas liczenia całej prognozy to 31.
Autor zadania: Zbigniew Czech.