Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP7_1A - Przepustowosc |
Z okazji zbliżających się wyborów samorządowych, burmistrz Bajtocji stara się prowadzić jak najwięcej inwestycji w swoim mieście. Chce on pokazać wyborcom, że jest jest najlepszym kandydatem na to stanowisko.
Jedną z bolączek miasta, jest mało wydajna kanalizacja, przypominająca w kształcie prostokąt. Rury kanalizacyjne zostały wymienione jakiś czas temu, jednak trzeba jeszcze wymienić łączniki. Łącznik charakteryzuje się tym, że musi mieć minimalną przepustowość, równą sumie przepustowości rur kanalizacyjnych, przechodzących przez niego.
W związku z tym, że miasto ma ograniczone fundusze, należy określić jaką minimalną przepustowość powinien mieć każdy łącznik. Jako, że jesteś doradcą burmistrza Bajtocji ds. technicznych zadanie to powierzono Tobie.
Wejście
W pierwszej linii wejścia znajdują się trzy liczby całkowite w ∈ [2;1000], h ∈ [2;1000] oraz r ∈ [2;1000], oznaczające odpowiednio liczbę łączników w poziomie, liczbę łączników w pionie oraz liczbę rur kanalizacyjnych. Następnie mamy r opisów rur kanalizacyjnych.
W pierwszej linii opisu każdej rury znajdują się dwie liczby całkowite c ∈ [2;1000] oraz n ∈ [2;2000], oznaczające przepustowość danej rury kanalizacyjnej oraz liczbę łączników, w których zmienia ona swój bieg, zaczyna się i kończy. W kolejnych n liniach mamy dwie liczby całkowite x ∈ [1;w] oraz y ∈ [1;h], określające współrzędne danego łącznika. Współrzędne x1 y1 określąją początek rury kanalizacyjnej, zaś xn yn jej koniec.
Wyjście
Na wyjściu należy wypisać h wierszy. W każdym z nich powinno znaleźć się w liczb. Liczba i-ta w j-tym rzędzie powinna odpowiadać minimalnej przepustowości łącznika o współrzędnych i,j.
Przykład
Wejście
5 5 2 2 6 1 1 1 5 3 5 3 1 5 1 5 5 3 4 1 3 5 3 5 5 1 5
Wyjście
2 0 2 2 2 2 0 2 0 2 5 3 5 3 5 2 0 2 0 5 5 5 5 3 5
Dodane przez: | Grzegorz Speranza |
Data dodania: | 2015-03-21 |
Limit czasu wykonania programu: | 0.5s-1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 JS-MONKEY SCM qobi |
Pochodzenie: | VII Mistrzostwa WWSI w Programowaniu |