26702번 - Areny 다국어

Bajtek dostał od rodziców na święta najnowszą grę komputerową Byte Defence 4. Jako zapalony gracz, od razu włożył płytę do napędu CD i rozpoczął rozgrywkę. Odkrył, że w grze steruje się postacią zwaną Bajtonatorem, którą należy zdobywać doświadczenie, wypełniać zadania i zdobywać coraz lepszy ekwipunek. Bajtek odkrył też, że na mapie gry rozlokowanych jest n specjalnych aren, na których może zdobyć bardzo wartościowe przedmioty. Niestety, aby wejść na arenę, należy dysponować specjalną, dedykowaną tej arenie przepustką. Bajtek postanowił zatem dokładniej przyjrzeć się systemowi aren i przepustek.

Arena to miejsce walk. Jeśli gracz posiada na nią przepustkę, to może się na nią udać i zmierzyć się z czekającym tam potworem. Wejście na arenę nie powoduje utraty przepustki. Potwór na arenie odradza się, gdy gracz ją opuszcza; zatem na każdą arenę można udać się wielokrotnie, używając za każdym razem tej samej przepustki. Gdy gracz pokona potwora znajdującego się na arenie, otrzymuje – oprócz rzadko spotykanych przedmiotów – nową przepustkę.

Nowa przepustka jest losowana ze specjalnej puli przepustek tej areny. Pula przepustek każdej areny jest jawna i znana Bajtkowi. Po zwycięstwie na arenie losowana jest przepustka z jej puli, po czym jej kopia zostaje wręczona graczowi. Żadna pula przepustek nigdy się nie zmienia, ani nic z niej nie ubywa. Zatem możliwe jest, że po pewnej liczbie zwycięstw gracz będzie posiadał wiele kopii jednej przepustki.

Niestety, sama walka z potworami również do łatwych nie należy. Bajtek po przejrzeniu poradników w internecie dowiedział się, że wraz z rosnącymi numerami aren rośnie ich trudność. Stwierdził zatem, że na pewno istnieje taka stała k, że jest w stanie bez problemu zwyciężyć na arenach o numerach mniejszych bądź równych k, zaś na pewno nie jest w stanie zwyciężyć na arenach o numerach większych od k.

Bajtek, zachęcony możliwością zdobycia ekskluzywnych przedmiotów, postanowił zacząć walczyć na arenach. Zorientował się jednak, że nie posiada żadnej przepustki – musi więc kupić przepustkę za prawdziwe pieniądze. Nieco rozczarowany systemem zawartym w grze postanowił się jednak nie poddawać i kupić jedną przepustkę. Nie wiedział jednak którą – w końcu chciałby dzięki niej odblokować dostęp do innych aren.

– Jeśli kupię tylko przepustkę na arenę A i dzięki niej będę absolutnie pewien, że w końcu będę mógł odnieść zwycięstwo na arenie B, to nie jest to wcale taki zły zakup. – pomyślał chłopiec.

Naszło go zatem pytanie: dla ustalonej wartości k, ile istnieje takich uporządkowanych par aren (A, B), gdzie A 6= B, że, kupując przepustkę na arenę A, Bajtek może być absolutnie pewny, że przy swojej optymalnej strategii będzie kiedyś mógł wejść na arenę B i odnieść tam zwycięstwo, niezależnie od tego, jakie przepustki będzie dostawał za zwycięstwa? Formalniej, dla ustalonej pary aren (A, B) musi istnieć taka strategia wybierania aren do walki^∗ oraz taka skończona stała M, że gracz, wybierając areny zgodnie ze strategią, jest w stanie wymusić zwycięstwo na arenie B po maksymalnie M wygranych walkach.

Ustalenie liczby par aren okazało się jednak dla niego zbyt trudne, dlatego zwrócił się o pomoc do Ciebie. Pomóż mu i wyznacz tę liczbę dla każdej możliwej wartości k.

^∗Strategia jest formalnie funkcją ze stanu gry w ruch, ale można o niej myśleć również jak o drzewie decyzyjnym mówiącym, na której arenie powinniśmy teraz zagrać, w zależności od tego, które przepustki obecnie posiadamy.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (2 ≤ n ≤ 2 · 10⁵), oznaczająca liczbę aren (i zarazem liczbę rodzajów przepustek).

Kolejnych n wierszy zawiera opisy pul przepustek; i-ty z nich zaczyna się jedną liczbą całkowitą ℓ_i (1 ≤ ℓ_i), oznaczającą liczbę przepustek w i-tej puli. Następnie, w tym samym wierszu, znajduje się ciąg ℓ_i liczb całkowitych, oznaczających numery aren, na dostęp do których pozwalają przepustki z puli i-tej areny. Areny indeksujemy liczbami całkowitymi od 1 do n.

Suma po wartościach ℓi w jednym pliku nie przekroczy 5 · 10⁵.

W jedynym wierszu wyjścia powinno znaleźć się n liczb całkowitych – k-ta z nich powinna oznaczać liczbę uporządkowanych par aren (A, B) takich, że A 6= B oraz po kupieniu przepustki na arenę A gracz może być pewny, że w końcu będzie mógł odnieść zwycięstwo na arenie B, zakładając, że jest w stanie on wygrywać walki jedynie na arenach o indeksach nieprzekraczających k.

Wyjaśnienie przykładu: Jeśli k = 9 (czyli chłopiec jest w stanie zwyciężyć na każdej arenie) oraz Bajtek kupi przepustkę na pierwszą arenę (A = 1) i zwycięży na niej, to otrzyma za to przepustkę na arenę drugą lub trzecią. Jeśli otrzyma przepustkę na trzecią arenę, to może tam zmierzyć się z przeciwnikami i być pewnym, że otrzyma w nagrodę przepustkę na drugą arenę. Para aren (1, 2) jest zatem poprawna i powinna być liczona w wyniku.

Jeśli zaś k = 2, to po kupieniu przepustki na pierwszą arenę (A = 1) Bajtek może otrzymać przepustkę na trzecią arenę, gdzie niestety nie da sobie rady. Z tego względu żadna para aren w której (A = 1) nie powinna być liczona w wyniku dla k = 2.

Jeśli k ≥ 7 i Bajtek kupi przepustkę na siódmą arenę (A = 7), to niezależnie od tego, ile razy na niej zwycięży, może cały czas otrzymywać tylko przepustki na czwartą arenę lub tylko na szóstą arenę. W związku z tym ani para (7, 4), ani para (7, 6) nie powinny być uwzględnione w wyniku dla żadnej wartości k. Jednakże, niezależnie od tego, czy będzie dysponował przepustką na czwartą, czy szóstą arenę, Bajtek może udać się na tę arenę i tam zdobyć przepustkę na piątą arenę. Para (7, 5) powinna zatem być uwzględniona w wyniku.

Jeśli zaś k < 7 i Bajtek kupi przepustkę na siódmą arenę, to niestety od razu utknie, gdyż czekający tam potwór będzie dla niego stanowczo za silny.

Wszystkie poprawne pary aren dla k = 9 to: (1, 2), (2, 1), (3, 1), (3, 2), (4, 5), (6, 5) i (7, 5).