In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.