Contest problemset description

Jasio kupił sobie w sklepie drzewo. Wygląda dość typowo, jak każde drzewo ze sklepu z drzewami, czyli jakoś mniej więcej tak:

Otrzymujesz od Jasia opis jego drzewa, składającego się z N wierzchołków. Korzeń drzewa ma numer 1, zaś pozostałe wierzchołki numerowane są kolejnymi liczbami naturalnymi od 2 do N włącznie. Dla każdego wierzchołka i, który nie jest korzeniem drzewa, znasz numer P_i jego bezpośredniego rodzica w drzewie.

Wypisz drzewo poziomami, tzn. w kolejnych wierszach należy wypisać wierzchołki, na coraz większych głębokościach (coraz większych odległościach od korzenia).

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę wierzchołków drzewa. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N − 1 liczb naturalnych P₂, P₃, …, P_N, pooddzielanych pojedynczymi odstępami.

Wyjście

Twój program powinien wypisać na wyjście opis drzewa z wejścia. W (d+1)-tym wierszu powinien się znaleźć rosnący ciąg numerów wierzchołków znajdujących się w odległości d od korzenia.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ P_i + 1 ≤ i.

Przykład

8
1 2 2 1 5 6 6

1 
2 5 
3 4 6 
7 8 

Jaś spał pod kamieniem przez ostatnie dziesięciolecia i dopiero dzisiaj odkrył jeden z najbardziej popularnych automatów komórkowych, nazywanych po polsku Gra w życie.

Idąc za Wikipedią, gra toczy się na nieskończonej planszy podzielonej na kwadratowe komórki. Każda komórka ma ośmiu sąsiadów (komórki przylegające do niej bokami lub rogami). Komórki mogą być żywe lub martwe. Stan komórek z momentu T jest używany do obliczenia stanu komórek w momencie T + 1. Martwa komórka, która ma dokładnie trzech żywych sąsiadów, staje się żywa w następnej jednostce czasu. Żywa komórka z dwoma lub trzema żywymi sąsiadami pozostaje w następnej jednostce czasu żywa. Przy innej liczbie sąsiadów żywa komórka umiera (a martwa pozostaje martwa).

Okazuje się, że tak proste reguły pozwalają na uzyskiwanie bardzo ciekawych struktur (polecamy po turnieju przejrzeć podlinkowany artykuł z Wikipedii).

Jasio nie ma nieskończonej pamięci w komputerze, żeby symulować grę w życie. Dlatego symuluje ją na skończonej planszy o wymiarach 15 × 15. Zastanawia się czy symulacja ewolucji z jego początkowego układu ma sens na tak małej planszy: być może w którymś momencie struktura wyewoluuje poza zakres planszy. A być może nie? Jaś chciałby to wiedzieć. Pomożesz mu?

Wejście

Wejście składa się z piętnastu wierszy po piętnaście znaków. Każdy znak to . lub O (duża litera o), oznaczające odpowiednio martwą lub żywą komórkę.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna T, określającą pierwszy moment, w którym struktura przekroczy ramy początkowej planszy.

Jeżeli T > 100 lub struktura nigdy nie przekroczy ramy początkowej planszy, to zamiast tego należy wypisać tylko jedno słowo NIE.

Zadanie bonusowe

Po turnieju spróbuj wygenerować test, dla którego odpowiedź T jest skończona, ale większa niż 100.

Przykład

...............
.OO............
.OO............
...............
.OO............
.O.O...........
..O............
...............
.......OOO.....
.......O.......
........O......
...............
...............
.OOO...........
...............

21

Jasio postanowił zrobić straszną rzecz… postanowił zorganizować porwanie dla okupu. Wszyscy w klasie próbowali mu to wybić z głowy, ale bezskutecznie. Postanowił przygotować kartkę z odpowiednim napisem, by wysłać ją osobom, które mają mu zapłacić pieniądze. Ponieważ Jasio naoglądał się filmów akcji, kartka ma powstać z wycinków gazet i literek tam umieszczonych. Niestety, Jasio nie ma zbyt wielu gazet (a więc i dostępnych literek) i może się okazać, że nie każdy napis daje się przygotować z dostępnych znaków. Postanowił więc, że jeżeli zabraknie mu jakichś literek to w ostateczności dopisze je długopisem. Ponieważ z pisaniem również u Jasia krucho, chciałby dopisać jak najmniej literek. Ile to będzie? Pomóż Jasiowi, to może Ciebie nie porwie.

Wejście

W pierwszym wierszu wejścia znajduje się ciąg małych liter alfabetu angielskiego – treść kartki, którą chce przygotować Jasio. W drugim (ostatnim) wierszu wejścia znajduje się ciąg małych liter alfabetu angielskiego – sklejona treść wszystkich gazet posiadanych przez Jasia.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – minimalna liczba liter, które Jasio będzie musiał dopisać długopisem, żeby uzyskać treść swojej kartki (oprócz tych liter, które przyklei z gazet).

Ograniczenia

Długość każdego z napisów na wejściu nie przekracza 1 000 000 znaków.

Przykład

dawajkase
jasiojestgupi

5

Liczbę nazywamy rosnącą, jeżeli jej cyfry, czytane od najbardziej znaczącej do najmniej znaczącej, tworzą ciąg (ściśle) rosnący.

Przykładowo: liczba 123 jest rosnąca, podobnie jak 6, 28 oraz 45 789, zaś liczby 72, 555 oraz 45 719 nie są rosnące.

Napisz program, który: wczyta liczbę naturalną N, wyznaczy najmniejszą liczbę rosnącą, która jest większa niż N i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się liczba naturalna N.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć najmniejsza możliwa liczba rosnąca M, spełniająca warunek M > N.

Jeżeli taka liczba nie istnieje, zamiast tego należy wypisać tylko jedno słowo NIE.

Ograniczenia

1 ≤ N ≤ 10⁹.

Przykład

214

234

Ludzie tym różnią się od komputerów, że wielu rzeczy potrafią się domyślić. Ciekawe, czy potrafisz rozwiązać zadanie, w którym nie ma treści?

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno się znaleźć jedno ze słów: czerwony, rozowy, pomaranczowy, zolty, zielony, niebieski, fioletowy, brazowy, bialy, szary, czarny (bez polskich znaków).

Gwarantowane jest, że dane wejściowe zostały zaprojektowane w taki sposób, że nikt (poza daltonistami) nie będzie miał wątpliwości co do poprawności odpowiedzi.

Uwaga

Inne kolory, w szczególności morski, amarantowy, bordowy, granatowy nie istnieją. Każdy nie-daltonista patrząc na testy, wiedziałby jaka jest poprawna odpowiedź dla każdego z nich (przy tym zbiorze możliwych odpowiedzi jaki jest w zadaniu).

Przykład

#ff69b4

rozowy

#9400d3

fioletowy

#080808

czarny

Jasio, zgłębiając tajniki informatyki, przeczytał ostatnio o morfizmach na słowach i ich zastosowaniach do tworzenia zbiorów słów takich jak słowa Thuego-Morse’a lub słowa Fibonacciego.

Jasio postanowił wymyślić swój własny morfizm. Zdefiniował go następująco: J₀ = S dla ustalonego, ulubionego słowa Jasia S składającego się jedynie ze znaków a oraz b. Następnie Jasio zdefiniował regułę podstawiania, która pozwala ze słowa J_i uzyskać słowo J_i + 1: każde wystąpienie litery a zamienia na słowo bab, zaś każde wystąpienie litery b zamienia na aaa.

Jeśli przykładowo S to słowo baba, to słowo J₁ jest równe aaababaaabab. W podobny sposób ze słowa J₁ można uzyskać słowo J₂: zaczynałoby się od babbabbabaaabab.... Jaś zastanawia się nad tym jak wygląda słowo J_N. Dokładniej, chciałby poznać wycinek J_N[L…R] czyli fragment słowa J_N od L-tego do R-tego znaku. Pomożesz mu?

Wejście

W pierwszym wierszu wejścia znajduje się niepusty ciąg znaków a i b – słowo S. W drugim (ostatnim) wierszu wejścia znajdują się trzy liczby naturalne N, L oraz R, oddzielone pojedynczymi odstępami.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinien się znaleźć ciąg znaków o długości R − L + 1 – fragment słowa J_N od L-tego do R-tego znaku włącznie.

Znaki słowa numerujemy kolejnymi liczbami naturalnymi, zaczynając od 1.

Ograniczenia

Długość słowa S nie przekracza 100.

1 ≤ N ≤ 30, 1 ≤ L ≤ R ≤ |J_N|, R − L + 1 ≤ 100 000.

Przykład

baba
2 4 15

babbabaaabab

Jasio chce wystartować w Bajtockich Mistrzostwach Szkół Średnich w Programowaniu Zespołowym. Zastanawia się teraz nad nazwą drużyny. A że ma w sobie żyłkę hakiera, postanowił dobrać ją tak, żeby zajmowała jak największą szerokość ekranu. Jasio ma nadzieję, że wtedy, za każdym razem, gdy system konkursowy wyświetli listę rankingową, tabelka z wynikami się “rozjedzie” (szerokość kolumny z nazwą drużyny będzie zbyt duża, powodując poszerzenie tabelki) i wszyscy zobaczą jego geniusz hackingu.

Jasio pieczołowicie sprawdził, która literka alfabetu daje przy wybranej czcionce największą szerokość (w pikselach), wysłał zapytanie do systemu i okazało się, że system konkursowy odrzucił nazwę drużyny, wykrywając, że jej wypisanie na ekranie przekroczyłoby limit szerokości kolumny w tabeli rankingowej.

Jasio zasmucił się, że jego niecny plan nie zadziałał i dlatego postanowił utrzeć nosa autorom systemu konkursowego. Wysyłając wiele zapytań do systemu, ustalił wartość graniczną P. System odrzuca wszystkie nazwy drużyny, których szerokość przy wyświetleniu przekracza szerokość P pikseli.

Jasio postanowił wysłać do systemu taką nazwę drużyny, która zmieści się w limicie pikseli, a jednocześnie będzie się składała z jak największej liczby znaków. Być może uda mu się zapchać bazę danych wysyłając dużo zapytań i każdy zobaczy, że jest elitarnym hakierem? Pomóż mu!

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna P, określająca limit na szerokość nazwy drużyny (w pikselach).

W drugim wierszu wejścia znajduje się jedna liczba naturalna |Σ|, określająca liczbę różnych znaków w alfabecie, których pozwala użyć system (wartość ta może być większa niż 26 lub nawet 256, ponieważ system, zależnie od konfiguracji, może pozwalać na używanie znaków z UTF-8).

W trzecim (ostatnim) wierszu wejścia znajduje się |Σ| liczb naturalnych W_i pooddzielanych pojedynczymi odstępami. Są to szerokości kolejnych znaków alfabetu podane w pikselach według czcionki, której używa system konkursowy.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – największa możliwa liczba znaków, z których może składać się akceptowana przez system nazwa drużyny.

Ograniczenia

1 ≤ P ≤ 10⁹, 1 ≤ |Σ| ≤ 100 000, 1 ≤ W_i ≤ 10⁹.

Przykład

110
3
19 30 22

5