Contest problemset description

W domu Marka w dzień wigilii wiesza się skarpety na kominku dla każdego z gości. Oprócz tego, że można je potem założyć i cieszyć się z ogrzanych stóp to na dodatek po kolacji wigilijnej każda osoba znajduje w swojej skarpecie prezent.

Zebrani goście podchodzą w pewnej kolejności do kominka, zabierają swoją skarpetę i odchodzą. Marek usiadł przy stole tak, że widzi jedynie pierwszą jeszcze wiszącą skarpetę od lewej strony kominka.

Z racji tego, że nawet podczas świąt nie robi sobie odpoczynku od intensywnego myślenia, to postanowił wyznaczyć najmniejszą leksykograficznie kolejność zabierania skarpet, która zgadza się z tym, co widział, jeżeli skarpety są ponumerowane od lewej do prawej strony kominka od 1 do N + 1.

Wejście

W pierwszym wierszu wejścia znajduje się liczba naturalna N określająca liczbę zabranych skarpet.

W drugim wierszu wejścia znajduje się N liczb naturalnych A_i określających numer pierwszej skarpety, którą widzi Marek po i-tym zabraniu.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinien znaleźć się ciąg N liczb naturalnych określających najmniejszą leksykograficznie kolejność zabierania skarpet z kominka.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ A_i ≤ N + 1.

Przykład

5
1 1 3 3 4

2 5 1 6 3 

Kalendarz adwentowy zawiera 24 czekoladki i każdego dnia od 1. do 24. grudnia należy zjeść jedną czekoladkę z kalendarza.

Rodzice Marka chcąc utrudnić mu życie, wręczyli mu kalendarz adwentowy dopiero N-tego dnia Grudnia. Aby Marek mógł poczuć magię świąt, musi zjeść wszystkie czekoladki z kalendarza, ale każdego dnia od N-tego do 24. grudnia musi zjeść taką samą ilość czekoladek.

Jako że Marek jest bardzo zajęty łapaniem Świętego Mikołaja, to poprosił Cię o napisanie programu, który powie mu czy będzie on w stanie każdego dnia jeść tyle samo czekoladek i zjeść wszystkie 24.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba całkowita N - numer dnia miesiąca, którego Marek dostał kalendarz adwentowy.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno znaleźć się słowo TAK, jeśli Marek jest w stanie zjeść wszystkie czekoladki lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 24.

Przykład

1

TAK

Paulina ma zegar, który składa się z N wyświetlaczy siedmiosegmentowych. Każdy segment, który pokazuje zegar, możemy przedstawić jako odcinek długości 1. Odległości między kolejnymi wyświetlaczami zegara to także 1.

Poniżej znajduje się przykładowy zegar dla N = 10, który wyświetla liczbę 0123456789 (Paulina nie ma nic przeciwko zerom wiodącym).

Paulina ustawiła swój zegar tak, żeby wyświetlał czas pozostały do świąt, ale zdenerwowało ją, jak duża jest ta liczba. Z tego powodu postanowiła ona zemścić się na zegarze i przeciąć go jednym prostym cięciem. Po takim cięciu niektóre cyfry mogły zostać przecięte i rozpaść się na kilka fragmentów.

Na przykład dla poniższego cięcia, cyfra 7 rozpadnie się na 3 fragmenty, cyfra 1 na 2 fragmenty, a cyfra 5 pozostanie w jednym fragmencie.

Jak wiadomo, Paulina chce zostać programistką, więc nie posiada rąk chirurga. Dlatego, cięcie przez nią wykonane na pewno nie będzie przechodziło przez żaden z końców segmentów wyświetlaczy, ani nie będzie równoległe do żadnego z segmentów.

Wartością cięcia Paulina nazywa sumaryczną liczbę fragmentów, na jakie rozpadną się cyfry wyświetlane przez zegar. Paulina chciałaby się dowiedzieć, jaka jest największa możliwa wartość cięcia, które może wykonać. Musi ona jeszcze jednak spakować prezenty, więc poprosiła Cię o pomoc w rozwiązaniu tego problemu.

Wejście

W pierwszym wierszu wyjścia znajduje się jedna liczba całkowita N - ilość cyfr, które wyświetla zegar.

W drugim wierszu znajduje się N cyfr reprezentujących liczbę aktualnie wyświetlaną przez zegar. Dopuszczalne są zera wiodące.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita - maksymalna liczba fragmentów, na którą można przeciąć liczbę wyświetlaną przez zegar.

Ograniczenia

1 ≤ N ≤ 500 000.

Przykład

3
715

9

Paulina zdała ostatnio egzamin na prawo jazdy, a już jest zmuszona do jeżdżenia po autostradzie. Jej zadaniem jest przewiezienie paczek z prezentami świątecznymi z miasta A do miasta B. Zgodnie z prawem, może przejechać maksymalnie K kilometrów bez przerwy. Po osiągnięciu tego limitu musi zrobić postój trwający co najmniej P minut, zanim będzie mogła kontynuować jazdę. Z racji tego, że pojazd, którym się porusza, nie jest pierwszej młodości, może poruszać się z maksymalną prędkością jednego kilometra na minutę.

Święta już za rogiem, więc Paulina chciałaby przejechać trasę jak najszybciej. Jako jej kolega programista odpowiedz na jej pytanie, po ilu minutach najszybciej może dojechać z miasta A do miasta B, wiedząc, że postoje może robić jedynie w miastach oraz znając długości dróg łączących pary miast.

Wejście

W pierwszym wierszu wejścia znajdują się liczby naturalne N, M, A, B, K i P oznaczające odpowiednio liczbę miast, liczbę dróg, miasto, z którego chce wyruszyć Paulina oraz miasto, do którego chce dojechać, maksymalną liczbę kilometrów, którą można przejechać bez postoju oraz minimalną długość postoju w minutach.

W każdym z kolejnych M wierszy znajdują się trzy liczby X_i, Y_i oraz Z_i oznaczające drogę z miasta X_i do miasta Y_i o długości Z_i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinien znaleźć się najkrótszy czas przejechania z miasta A do miasta B bez łamania prawa lub NIE jeżeli się nie da.

Ograniczenia

1 ≤ N, M ≤ 500 000, 1 ≤ A, B, X_i, Y_i ≤ N, 1 ≤ K, P, Z_i ≤ 1 000 000.

Przykład

6 6 4 6 4 5
5 3 6
4 3 5
4 1 2
5 1 3
6 5 4
1 3 3

19

Zostało parę dni do świąt, a Marek dalej nie kupił prezentów. Na całe szczęście jutro jest niedziela handlowa, więc wystarczy, że pojedzie do najbliższej galerii. Zna on swoich bliskich bardzo dobrze i wie, że są oni wyjątkowo zazdrośni o prezenty, które dostają. W szczególności, jeżeli ktoś dostanie prezent, który kosztował ponad dwa razy mniej niż czyjkolwiek inny, to obrazi się na wszystkich i zepsuje świąteczną atmosferę.

Chodząc po sklepach, Markowi zaczynają się podobać niektóre prezenty oraz rozmyśla się nad innymi. Będzie informował Cię o każdej takiej zmianie w upodobaniach, podając cenę prezentu. Musisz odpowiedzieć na każde jego pytanie o maksymalną liczbę prezentów, które może kupić spośród aktualnie przez niego rozważanych.

Wejście

W pierwszym wierszu wejścia znajduje się liczba naturalna M oznaczająca liczbę zapytań. Każdy z następnych M wierszy wygląda na jeden z następujących sposobów:

• + X_i : Markowi spodobał się prezent, który kosztuje X_i
• − X_i : Markowi przestał podobać się prezent, który kosztuje X_i, gwarantowane jest, że wcześniej podobała mu się co najmniej jedna rzecz, która tyle kosztuje.
• ? : Marek zadaje pytanie, ile maksymalnie może kupić prezentów, z tych które mu się aktualnie podobają, by nikt nie był zazdrosny.

Wyjście

Na wyjściu powinna znaleźć się odpowiedź na każde zapytanie Marka. Gwarantowane jest, że zapyta się on co najmniej raz.

Ograniczenia

1 ≤ M ≤ 1 000 000, 1 ≤ X_i ≤ 10⁹.

Przykład

7
+ 4
+ 6
+ 6
+ 2
?
- 6
?

3
2

Paulina i Marek zmęczyli się przygotowywaniami do świąt (i robieniem turnieju), więc postanowili zagrać w grę.

Na choince w domu Pauliny znajduje się N bombek, ponumerowanych od 1 do N. Na bombce numer 1 znajduje się wstążka. W jednym ruchu:

• Marek wybiera bombkę i zdejmuje ją z choinki.
• Paulina zdejmuje wstążkę z bombki, na której aktualnie się znajduje, wiąże ją na bombce, która jest z nią połączona lampkami i zdejmuje poprzednią bombkę z choinki.

Te dwie czynności powtarzają się tak długo, aż Paulina nie może zmienić położenia wstążki. Z racji tego, że Marek nie zawsze odróżnia wstążki od innej ozdoby, to nie zna jej dokładnego położenia oprócz początkowego. Wie za to, które bombki są jeszcze na choince.

Chce wiedzieć, czy może zdejmować bombki z choinki w taki sposób, że Paulina zmieni położenie wstążki maksymalnie K razy. Pomóż mu odpowiedzieć na to pytanie.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne, N i K. W każdym z następnych N − 1 znajdują się dwie liczby naturalne X i Y oznaczające lampki łączące bombki X i Y. Gwarantowane jest, że połączenia te tworzą drzewo.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno znaleźć się TAK, jeżeli Marek potrafi zapewnić, by gra skończyła się w maksymalnie K ruchach, lub NIE jeżeli nie może.

Ograniczenia

1 ≤ K ≤ N ≤ 400, 1 ≤ X, Y ≤ N − 1.

Przykład

8 2
1 2
2 3
2 4
5 6
6 8
1 5
7 1

TAK

Paulina dostała nową zabawkę złożoną z N zębatek, które możemy przedstawić jako koła na płaszczyźnie. Wszystkie zębatki mają ten sam promień R.

Każda zębatka ma swoje zęby rozmieszczone na zewnętrznym pierścieniu o szerokości 1 jednostki, znajdującym się w zakresie od odległości R − 1 (wewnętrzny brzeg pierścienia) do R (zewnętrzny brzeg pierścienia) od środka zębatki. Zębatki zazębiają się, jeśli stykają się lub nachodzą na siebie tym pierścieniem - dokładniej jeśli odległość między ich środkami jest nie większa niż 2R. Dodatkowo żadne dwie zębatki nie nachodzą na siebie poza tym pierścieniem, czyli odległość środków dowolnych dwóch zębatek jest nie mniejsza niż 2(R−1).

Paulina będzie się bawiła swoją zabawką poprzez kręcenie zębatkami. Jeśli zębatki się zazębiają i pierwsza z nich kręci się w kierunku przeciwnym do ruchu wskazówek zegara, to druga musi się kręcić zgodnie z ruchem wskazówek zegara. Podobnie, jeśli pierwsza kręci się zgodnie z ruchem wskazówek zegara, to druga musi kręcić się przeciwnie. Niestety zabawka Pauliny została złożona poza granicami Laponii, więc jej jakość nie jest wybitna. Może się zdarzyć, że będzie istnieć zębatka, którą nie da się zakręcić, dokładniej jej zakręcenie spowoduje, że jakaś zębatka będzie się musiała jednocześnie kręcić w dwa różne kierunki.

Zabawka Pauliny jest dość duża jak na jej wiek i nie jest ona w stanie przetestować czy może zakręcić dowolną zębatką. Dlatego Paulina poprosiła Cię o napisanie programu, który powie jej czy może zakręcić dowolną zębatką.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby N i R - liczba zębatek i ich promień.

W każdym z kolejnych N wierszy znajdują się dwie liczby całkowite x_i i y_i - współrzędne środków kolejnych zębatek.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinno się znaleźć słowo TAK, jeśli Paulina może zakręcić dowolną zębatką i NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 200 000

1 ≤ R ≤ 10⁹

0 ≤ x_i, y_i ≤ 10⁹

Przykład

5 2
0 0
0 4
3 0
3 4
7 2

TAK

3 3
1 1
1 7
5 4

NIE