Contest problemset description

Nadchodzi lato! W przeciwieństwie do zimy, w kulturze krasnoludków lato to czas radości, spokoju i przede wszystkim… hucznych przyjęć! Gdy tylko zaczynają się pierwsze gorące dni, w całym królestwie krasnoludków rozpoczynają się przygotowania do Krasnalfestu, corocznego festiwalu tańca, śpiewu i oczywiście programowania.

Należy jeszcze wspomnieć, że krasnoludki to naród bardzo ambitny i pracowity. Z racji tego, że Krasnalfest jest najważniejszym wydarzeniem w całym roku, nawet najmniejszy szczegół festiwalu musi zostać dopracowany do perfekcji. Dlatego też krasnoludki Bernaś i Warchlaś mają nie lada zadanie – muszą zająć się dekoracjami.

Wszystko szło im wyśmienicie do momentu, aż dotarli do kwestii tradycyjnej wystawy czapek. Bernaś od razu zaproponował ustawienie czapek od najniższej do najwyższej. Warchlaś natomiast był odmiennego zdania – według niego dużo ciekawsze byłoby ułożenie od najwyższej do najniższej. Po kilku dniach debatowania postanowili zaniechać dalszych sporów i zdecydowali się na połączenie tych dwóch pomysłów.

Ustalona przez nich kolejność czapek miała spełniać następujący warunek: ciąg a₁, a₂, …, a_N, oznaczający wysokości kolejnych czapek, musi zawierać podciąg rosnący długości K i podciąg malejący długości L. Oczywiście ciąg a₁, a₂, …, a_N nazywamy rosnącym, gdy a₁ < a₂ < … < a_N. Analogicznie ciąg jest malejący, gdy a₁ > a₂ > … > a_N. Podciągiem nazywamy ciąg powstały w wyniku wykreślenia pewnych elementów (być może żadnego) oryginalnego ciągu.

Pozostało jedynie zlecić krasnoludzkim krawcom uszycie odpowiednich czapeczek. Pomóż Bernasiowi i Warchlasiowi złożyć zamówienie i napisz program, który dla danych liczb K i L wypisze długość najkrótszego możliwego ciągu wysokości czapek a₁, a₂, …, a_N, zawierającego podciąg rosnący długości K i podciąg malejący długości L.

Wejście

W pierwszym i jedynym wierszu standardowego wejścia znajdują się dwie liczby całkowite dodatnie K i L, oznaczające odpowiednio długość podciągu rosnącego i podciągu malejącego, który musi zawierać ciąg określony w zadaniu.

Wyjście

Na jedyny wiersz standardowego wyjścia powinieneś wypisać jedną liczbę całkowitą – długość najkrótszego ciągu, który zawiera podciąg rosnący długości K i podciąg malejący długości L.

Ograniczenia

1 ≤ K, L ≤ 1000.

Przykłady

3 5

7

1 1

1

10 10

19

1000 1000

1999

Krasnal Alpinek wybrał się na wycieczkę w góry. Tym razem jego trasa wiodła wzdłuż całej długości szlaku, który przechodził kolejno przez N szczytów. Na każdym z nich znajdował się punkt widokowy, a na nim tablica informacyjna dotycząca szczytu.

Niestety, podczas wyprawy Alpinka okazało się, że ktoś złośliwie zamazał wysokości wszystkich szczytów na tablicach, zastępując je wymyślonym przez siebie współczynnikiem atrakcyjności szczytu. Współczynnik ten oznaczał sumę wysokości trzech szczytów: szczytu na którym znajdowała się tabliczka, najwyższego szczytu na szlaku w kierunku jego początku oraz najwyższego szczytu na szlaku w kierunku jego końca.

Alpinek postanowił poszukać informacji na temat wysokości konkretnych szczytów u mieszkańców leżącej nieopodal wioski. Jednakże jedyną rzeczą, o której się dowiedział, było to, który ze szczytów jest najwyższy oraz jaka jest jego wysokość. Upewnił się on też, że najwyższy szczyt jest tylko jeden, więc wszystkie pozostałe szczyty są od niego ściśle niższe.

Alpinek próbuje teraz dociec na podstawie zebranych informacji jakie są wysokości kolejnych szczytów. Czy jesteś w stanie mu pomóc?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę szczytów na trasie Alpinka.

W drugim wierszu wejścia znajduje się N oddzielonych pojedynczymi odstępami liczb całkowitych s_i, gdzie s_i oznacza współczynnik atrakcyjności i-tego w kolejności szczytu. Formalniej, gdyby wysokości kolejnych szczytów wynosiły kolejno a₁, a₂, …, a_N, to zachodzi $s_i = \max\limits_{\ 1 \leq j \leq i-1} \{a_j\} + a_i + \max\limits_{\ i+1 \leq j \leq N} \{a_j\}$.

Możesz założyć, że wysokość każdego szczytu jest dodatnią liczbą całkowitą nie większą niż 10⁸. Przyjmujemy umownie, że wysokości najwyższych szczytów na szlaku przed pierwszym szczytem oraz za ostatnim szczytem wynoszą 0.

W trzecim i ostatnim wierszu wejścia znajdują się dwie oddzielone pojedynczym odstępem liczby całkowite k oraz a_k, oznaczające kolejno pozycję oraz wysokość najwyższego szczytu na trasie.

Wyjście

Na wyjściu wypisz N liczb a₁, a₂, …, a_N oznaczających wysokości kolejnych szczytów, spełniających wszystkie warunki podane w treści oraz na wejściu. Możesz założyć, że dla ciągu podanego na wejściu istnieje dokładnie jedna taka odpowiedź.

Ograniczenia

1 ≤ N ≤ 10⁶, 1 ≤ s_i ≤ 3 ⋅ 10⁸, 1 ≤ k ≤ N, 1 ≤ a_k ≤ 10⁸.

Przykłady

5
9 10 14 13 8
4 6

3 1 5 6 2 

4
12 15 19 16
4 10

2 3 6 10 

Krasnoludek Czyścioch nie cierpi bałaganu. Wszystko w jego domu musi mieć swoje miejsce, na półkach panuje ład i harmonia.

Ostatnio jego uwagę przykuł jeden regał, na którym trzyma książki o okładkach w kolorze czerwonym i niebieskim. Od ostatniego generalnego sprzątania domu jego kolekcja znacznie się zwiększyła, przez co w oczach Czyściocha kolejność książek na półce wygląda bardzo nieelegancko. Postanowił więc zająć się wreszcie tym tematem.

Czyścioch chciałby ustawić książki w taki sposób, aby żadne dwie z niebieską okładką nie stały bezpośrednio obok siebie. Aby tego dokonać, może on wyciągnąć wybraną z półki książkę i wstawić ją w dowolne inne miejsce. Chciałby wykonać minimalną liczbę takich przestawień książek – Czyścioch wolałby pozostawić siły na sprzątanie reszty swojego domu.

Napisz program, który znając kolory okładek książek na półce, wypisze ile co najmniej przestawień należy wykonać, żeby uzyskać interesujące Czyściocha ustawienie. Jeżeli nie istnieje ciąg przestawień po którym powyższy warunek byłby spełniony, należy wypisać  − 1.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N, oznaczająca liczbę książek na półce. W drugim wierszu wejścia znajduje się ciąg liczb całkowitych P₁, P₂, …, P_N, którego wyrazy oznaczają kolory kolejnych książek, gdzie 0 oznacza kolor czerwony, a 1 kolor niebieski.

Wyjście

W pierwszym wierszu wyjścia należy wypisać najmniejsza liczbę przestawień książek lub  − 1 jeżeli odpowiedź nie istnieje.

Ograniczenia

1 ≤ N ≤ 10⁶, 0 ≤ P_i ≤ 1.

Przykłady

5
1 0 1 0 1

0

8
1 0 1 1 1 0 0 0

2

3
1 1 1

-1

Krasnal Piastek uwielbia lody, jak i SMSowanie ze swoimi niskimi przyjaciółmi. Niestety, nie wziął on pod uwagę, że tych dwóch rzeczy nie należy robić jednocześnie. Chwila nieuwagi i BUM, nastąpiła katastrofa; cały telefon umazany w lodach! Na szczęście telefon wyszedł z tego niemal bez szwanku, poza jedną drobną usterką…

Został uszkodzony wskaźnik baterii w telefonie Piastka. Wskaźnik ten wyświetla dokładnie dwie cyfry, nawet jeśli poziom baterii jest poniżej 10%, przykładowo jeśli poziom baterii wynosi 7%, to wyświetla on 07. W wyniku wypadku z lodami, wskaźnik ten uległ niezwykle nietypowej awarii. Mianowicie w chwili, gdy wskazuje on N% baterii (oczywiście N > 0), to prawdziwy procent naładowania baterii to największa liczba M < N, taka że M różni się od N na dokładnie jednej cyfrze. Warto zauważyć, że dla N > 0, jest to dobrze zdefiniowane.

Krasnala Piastka przerosło obliczenie, ile procent baterii posiada obecnie jego telefon. Z tego względu zwrócił się do Ciebie z tym problemem. Twoim zadaniem jest odpowiedzenie na jego pytania.

Wejście

W pierwszym i jedynym wierszu standardowego wejścia znajduje się jedna liczba naturalna N oznaczająca wskaźnik baterii wyświetlany w telefonie (bez zer wiodących).

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się odpowiedź na pytanie Piastka – prawdziwy procent naładowania baterii.

Ograniczenia

1 ≤ N ≤ 99.

Przykłady

79

78

80

70

7

6

1

0

Podczas tegorocznego festynu czeka nas jeszcze jedna nie lada atrakcja – występ akrobatyczny nieustraszonego krasnala Latałka. Specjalnie na tę okazję przygotowanych zostało N trampolin, a każda z nich umieszczona jest na pewnej wysokości. Organizatorzy nie przewidzieli jednak jednej rzeczy – pomimo, że Latałek nie boi się niczego, to technicznie jest on w stanie przeskoczyć z jednej trampoliny na drugą tylko, jeśli wartość bezwzględna różnicy ich wysokości wynosi co najwyżej K (ale trampoliny te nie muszą sąsiadować ze sobą).

Wiadomo już, że występ Latałka rozpocznie się na trampolinie o numerze 1, po czym wykona on pewną sekwencję skoków pomiędzy trampolinami. Czy jesteś w stanie policzyć na ilu różnych trampolinach może się on zakończyć?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne N oraz K, oznaczające odpowiednio liczbę trampolin przygotowanych do występu oraz zasięg skoku Latałka.

W drugim wierszu standardowego wejścia znajduje się N liczb całkowitych a₁, a₂, …, a_N oznaczających wysokości kolejnych trampolin. Latałek rozpocznie swój występ na trampolinie o wysokości a₁.

Wyjście

W jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita będąca liczbą trampolin, na które jest w stanie dotrzeć Latałek, wykonując pewną sekwencję skoków.

Ograniczenia

1 ≤ N ≤ 5 ⋅ 10⁵, 1 ≤ K ≤ 10⁹, 1 ≤ a_i ≤ 10⁹.

Przykłady

5 2
3 1 8 4 5

4

7 1
4 2 4 8 8 4 5

4