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.
Bajtazar jest redaktorem nowego portalu internetowego poświęconego gastronomii w Bajtogrodzie. Wymyślił właśnie temat, który, jeśli zostanie rzetelnie opracowany, może znacząco zwiększyć popularność serwisu. Mianowicie, Bajtazar wpadł na pomysł stworzenia rankingu bajtogrodzkich barów serwujących këbaby.
W Bajtogrodzie jest skrzyżowań, ponumerowanych liczbami od do . Skrzyżowania połączone są dwukierunkowymi drogami o różnych długościach. Wiadomo, że między dowolnymi dwoma skrzyżowaniami można przejechać na dokładnie jeden sposób. Przy każdym skrzyżowaniu znajduje się dokładnie jeden bar z këbabami.
Ponieważ w każdym lokalu kucharze serwują równie smaczne i tanie këbaby, to rozstrzygającym kryterium w rankingu stał się koszt dowozu posiłku do klienta. Bajtazar zebrał dokładne informacje na temat barów i zanotował, że lokal przy -tym skrzyżowaniu dostarcza posiłki bezpłatnie tylko do skrzyżowań odległych od niego o nie więcej niż . Początkowo założył, że najwięcej punktów w kategorii "dostawa" otrzyma ten dostawca, który dojeżdża najdalej. Wkrótce zmienił jednak zdanie, gdyż słusznie zauważył, że znacznie lepiej oceniać lokale po liczbie skrzyżowań, do których këbab może być dostarczony z lokalu bezpłatnie. Twoim zadaniem jest znaleźć tę liczbę dla każdego lokalu.
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę skrzyżowań w Bajtogrodzie. W drugim wierszu znajduje się liczb całkowitych () oznaczających maksymalne odległości przy bezpłatnej dostawie dla kolejnych barów. W -tym z kolejnych wierszy znajdują się trzy liczby całkowite (), oznaczające, że skrzyżowania i są połączone drogą o długości .
W testach wartych punktów zachodzi warunek .
W testach wartych punktów istnieje co najwyżej jedno skrzyżowanie, z którego wychodzą więcej niż dwie ulice. Dodatkowo w tych testach zachodzi warunek .
Na wyjście należy wypisać wierszy; w -tym z nich powinna znaleźć się liczba skrzyżowań, do których -ty bar z këbabami dostarcza jedzenie bezpłatnie.
Dla danych wejściowych:
5 2 3 3 6 5 1 2 2 2 3 1 3 4 3 4 5 2
poprawną odpowiedzią jest:
2 3 4 5 3
Zadanie(utrudnione) zapożyczone z USACO DEC12.