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.
Król Bajtocji wydał niedawno dekret o modernizacji części autostrad. Inżynierowie królestwa obliczyli koszt modernizacji każdej autostrady. Znane są również długości wszystkich autostrad. Każda autostrada jest dwukierunkowa i łączy dwa miasta. Pozostaje problem wyboru, które autostrady modernizować. Główny Inżynier zwrócił się z tym pytaniem do króla. Król pomyślał chwilę i przedstawił swoje wymagania:
W pierwszym wierszu znajdują się dwie liczby całkowite oddzielone pojedynczym odstępem, liczba miast i liczba autostrad (). Miasta ponumerowane są od 1 do . Stolica ma numer 1, targi odbywają się w mieście numer 2. Każdy z kolejnych wierszy zawiera opis jednej autostrady w postaci czterech liczb oddzielonych odstępami , , , (). Opisują one autostrady łączące miasta i , z kosztem modernizacji bajtodolarów i o długości .
Jeśli nie da się spełnić warunków króla, należy w jedynym wierszu wypisać jedno słowo NIE. W przeciwnym razie należy wypisać minimalny średni koszt modernizacji kilometra autostrady w optymalnym rozwiązaniu. Innymi słowy, jest to suma kosztów modernizacji wybranych autostrad podzielona na sumę długości wybranych autostrad. Wynik należy wypisać w postaci ułamka w najprostszej postaci (nieskracalnego), czyli dwóch liczb całkowitych oddzielonych znakiem dzielenia (liczby całkowite wypisujemy w postaci ).
Dla danych wejściowych:
3 3 2 1 10 3 2 1 15 10 2 3 1 4
poprawną odpowiedzią jest:
8/7
Autor zadania: Tomasz Czajka (odgrzewane).