W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Władze zrzeszenia Holypolygons z okazji dziesiątej rocznicy pamiętnego pierwszego zlotu swoich członków na błoniach w Mudstock, postanowiły zorganizować wielki festiwal Mudstock bis.
Członkowie zrzeszenia mieszkają w wielu małych osadach Holypolylandii położonych wzdłuż linii kolejowych (gdzie ) ponumerowanych kolejnymi liczbami naturalnymi od do . Długość żadnej linii nie przekracza 500 km. Wszystkie linie mają początek w stolicy i biegną promieniście od stolicy ku obrzeżom kraju. Linie te nie krzyżują się. Każda osada nie będąca stolicą leży na dokładnie jednej linii. Na każdej linii liczba osad jest dodatnia i nie większa niż 100. Liczba członków zrzeszenia w jednej miejscowości również nie przekracza 100.
Każdą osadę, która nie jest stolicą identyfikujemy w jednoznaczny sposób za pomocą dwóch współrzędnych , gdzie to numer linii, na której leży osada, a to numer osady na linii. Osady na każdej z linii numerujemy kolejno od stolicy. Przyjmujemy, że stolica (która jest początkiem każdej linii) ma współrzędne .
Władze zrzeszenia fundują każdemu członkowi bilet kolejowy na powrót z festiwalu do miejsca zamieszkania. Cena biletu jest równa liczbie przejechanych kilometrów. Powstał więc problem, gdzie zorganizować festiwal, aby łączny koszt przejazdu koleją wszystkich członków zrzeszenia z festiwalu do domu był minimalny.
Ułóż program, który:
Jeżeli dla wielu miejscowości łączny koszt przejazdu koleją wszystkich członków stowarzyszenia z danej miejscowości do domu jest minimalny, to Twój program powinien znajdować jedną z nich.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite: liczba linii kolejowych () oraz liczba członków zrzeszenia mieszkających w stolicy kraju ().
W kolejnych wierszach znajdują się opisy linii o kolejnych numerach od do . Każdy opis ma postać ciągu liczb całkowitych pooddzielanych pojedynczymi odstępami.
Najpierw jest podana dodatnia liczba miejscowości, które leżą na danej linii (nie licząc stolicy). Każda kolejna para liczb to: dodatnia odległość kolejnej osady na danej linii od najbliższej osady w kierunku stolicy oraz nieujemna liczba członków zrzeszenia mieszkających w tej osadzie. Bezpośrednio po ostatniej liczbie każdego opisu następuje koniec wiersza.
Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego sprawdzać.
W pierwszym wierszu standardowego wyjścia należy zapisać minimalny łączny koszt przejazdu koleją wszystkich członków stowarzyszenia z festiwalu do miejsca zamieszkania, a w drugim wierszu współrzędne osady, w której należy zorganizować festiwal.
Dla danych wejściowych:
3 12 2 2 3 2 3 3 3 2 2 0 2 3 3 3 4 1 3 2 3
poprawną odpowiedzią jest:
87 0 0
Poniższy rysunek jest ilustracją testu przykładowego.
Autor zadania: Andrzej Walat.