Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP5_1E - Tort |
Mistrzostwa Warszawskiej Wyższej Szkoły Informatyki w Programowaniu mają już całkiem dużą tradycję. Jakby nie patrzeć właśnie rozpoczyna się ich piąta edycja! Tak, to już 5 lat jak staramy się zachęcać studentów do zainteresowania się algorytmami i 5 lat jak borykamy się z pewnym problemem... Otóż co roku po finale, jaki odbywa się w siedzibie uczelni, na ceremonii zakończenia zawodów tradycyjnie konsumowany jest tort. Tort ma wymiary a × b i każdy z c finalistów ma prawo podejść do tortu i przekroić go wzdłuż lub wszerz w dowolnie wybranym przez siebie miejscu. Niepisanym punktem regulaminu zawodów jest to, że zwycięzca powinien otrzymać największy kawałek - tu tkwi cały haczyk! Skąd mamy wiedzieć który kawałek jest największy? Tort jest na ogół bardzo duży a finaliści praktycznie zawsze krojenie go traktują jak dobrą zabawę i zdarza się że wykonują nawet 105 cięć!
W tym roku postanowiliśmy porzucić mierzenie wszystkich kawałków linijką a zamiast tego zapisać wysokość albo szerokość na jakiej wykonywane było każde z cięć (cięcia zawsze wykonywane są równolegle do boku a albo b i przechodzą przez cały tort). Jako, że przygotowanie zadań na rundę finałową wymaga od nas mnóstwa czasu zmuszeni jesteśmy poprosić Cię o pomoc - pomóż nam i napisz program, który na podstawie zapisanych przez nas danych obliczy pole największego kawałka oraz określi liczbę takich kawałków (głęboko wierzymy w to, iż wiedza dotycząca pola powierzchni takiego kawałka zdecydowanie ułatwi nam jego znalezienie)..
Wejście
W pierwszej linii wejścia znajdują się trzy liczby całkowite a określająca wysokość,b określająca szerokość oraz c określająca liczbę cięć (1 < a, b < 109; 0 ≤ c ≤ 105). W kolejnych c liniach znajdują się współrzędne poszczególnych cięć q, minusem oznaczone zostały cięcia wykonane w poziomie (liczba q określa wtedy wysokość na jakiej wykonano cięcie), liczby dodatnie określają zaś cięcia wykonane w pionie (q określa wtedy szerokość na jakiej wykonane zostało cięcie). Współrzędne cięć i położenie tortu traktować można zatem tak jakby lewy dolny róg tortu znajdował się w punkcie 0,0 natomiast -q i q określały punkty przecięcia prostych równoległych do osi współrzędnych z odpowiednio x i y.
Wyjście
Dla każdego zestawu danych należy w osobnej linii wypisać dwie liczby oddzielone od siebie pojedynczą spacją - pole powierzchni największego kawałka i liczbę kawałków tej wielkości.
Przykład
Wejście:
9 14 3 -2 -7 7
Wyjście:
35 2
Dodane przez: | Maciej Boniecki |
Data dodania: | 2013-03-02 |
Limit czasu wykonania programu: | 0.5s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 SCM qobi |
Pochodzenie: | V Mistrzostwa WWSI w Programowaniu |