Polish version    English version  
  Historia OI -> XIII OI 2005/2006


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

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.

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.




Wersja do druku