Magazyn
Limit pamięci: 32 MB
Ulice w Bajtomieście tworzą prostopadłą siatkę - prowadzą ze wschodu na
zachód lub z północy na południe.
Ulice północ-południe są ponumerowane od 1 do
w kolejności z zachodu na wschód.
Podobnie ulice wschód-zachód są ponumerowane od 1 do
w kolejności z południa na północ.
Każda ulica północ-południe przecina każdą ulicę wschód-zachód i odwrotnie,
każda ulica wschód-zachód przecina każdą północ-południe.
Odległość między dwiema sąsiednimi ulicami północ-południe, a także
sąsiednimi ulicami wschód-zachód jest równa jednemu kilometrowi.
W mieście znajduje się sklepów, a
każdy sklep jest położony przy skrzyżowaniu ulic.
Kupiec Bajtazar dostarcza towary do każdego z sklepów, przy czym
część sklepów odwiedza kilka razy dziennie.
Bajtazar postanowił wybudować magazyn, z którego dostarczałby towary do
sklepów.
Magazyn powinien być położony przy skrzyżowaniu ulic.
Ciężarówka dostarczająca towary w trakcie jednego kursu może odwiedzić
tylko jeden sklep - wyjeżdża z magazynu, dostarcza towar do sklepu
i wraca do magazynu.
Ciężarówka zawsze jedzie najkrótszą trasą z magazynu do sklepu
i z powrotem.
Odległość między punktami i jest równa
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis rozmieszczenia sklepów
oraz ile razy dziennie towary są dostarczane do poszczególnych
sklepów,
-
wyznaczy takie położenie magazynu, żeby łączna odległość pokonywana
przez ciężarówkę każdego dnia była jak najmniejsza,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę sklepów
w Bajtomieście.
Kolejne wierszy wejścia zawiera opisy sklepów.
Wiersz -wszy zawiera trzy liczby całkowite , i
(,
), oddzielone pojedynczymi odstępami.
Ten opis oznacza, że -ty sklep jest położony na skrzyżowaniu
-tej ulicy północ-południe i -tej ulicy wschód-zachód
i ciężarówka codziennie dojeżdża do tego sklepu razy.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać dwie liczby całkowite
oraz , oddzielone pojedynczym odstępem i opisujące położenie
magazynu jako skrzyżowanie -tej ulicy północ-południe
i -tej ulicy wschód-zachód.
Jeżeli istnieje wiele poprawnych wyników, Twój program powinien
wypisać dowolny z nich.
Przykład
Dla danych wejściowych:
3
2 2 1
6 2 1
4 6 1
poprawną odpowiedzią jest:
4 4
Poniższy rysunek przedstawia sytuację z przykładowego wejścia.
Ponumerowane punkty oznaczają odpowiednie sklepy.
Punkt S oznacza optymalne położenie magazynu.
Autor zadania: Zbigniew Czech.