Contest problemset description

Za wiele, wiele lat, w odległej Ameryce, odbędzie się start pierwszego udanego załogowego lotu na Marsa. Zgodnie z obietnicami, wszystkim N astrofizykom pracującym w korporacji odpowiedzialnej za kolonizację Czerwonej Planety należą się za to premie o łącznej wysokości K złotych monet (na trzy lata przed kolonizacją Marsa ludzkość przejdzie na rozliczanie się fizycznym złotem). Mimo iż złote monety są niepodzielne, do rozliczeń na papierze używa się groszy (jedna moneta to G groszy).

Dla każdego pracownika Prezes dowolnie ustali nieujemną wysokość premii, a następnie wypłaci kwotę zaokrągloną do pełnych złotych monet (od $\lceil\frac{G}{2}\rceil$ groszy zaokrąglamy w górę), różnicę dopłacając lub chowając do własnej kieszeni.

Jako że Prezes ostatnio miał duże wydatki, chciałby ustalić wysokości premii dla poszczególnych astrofizyków w taki sposób, żeby na papierze ich łączna wysokość wynosiła K złotych monet oraz żeby zmaksymalizować łączną różnicę na jego korzyść wynikającą z zaokrąglenia.

Ile najwięcej pieniędzy Prezes może w ten sposób wyciągnąć z korporacji?

Wejście

W pierwszym i jedynym wierszu wejścia znajdują się trzy liczby całkowite N, K oraz G, pooddzielane pojedynczymi odstępami. Oznaczają one odpowiednio liczbę astrofizyków, łączną wysokość premii w złotych monetach i liczbę groszy odpowiadającą jednej złotej monecie.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą maksymalną łączną liczbę groszy, którą Prezes może wyciągnąć z korporacji.

Ograniczenia

1 ≤ N ≤ 10⁶, 0 ≤ K ≤ 10⁶, 2 ≤ G ≤ 1000.

Przykłady

3 3 100

100

2 1 14

0

12 12 100

500

123 0 2

0

W ramach programu eksploracji kosmosu, NASA zdecydowała się wysłać doktora Bitstronga, wraz z jego ekipą wytresowanych małp w skafandrach, na specjalną misję na nieznanej planecie. Niestety, pech chciał, że planeta ta nie dość, że jest pełna niebezpieczeństw, to jeszcze rosną na niej kosmiczne banany!

Wystarczyła tylko chwila nieuwagi, a cała małpia załoga rozproszyła się po okolicy w poszukiwaniu jedzenia i całkowicie zniknęła z pola widzenia doktora. Bitstrong chciałby sprowadzić zwierzęta z powrotem, więc poprosił centralę o udostępnienie zdjęć satelitarnych obszarów z małpami, aby móc poprawnie pokierować towarzyszy z powrotem do siebie.

Centrala NASA przesłała mu sześć zdjęć satelitarnych, każde przedstawiające jeden z obszarów, na którym znalazły się małpy. Ze względu na to, że komunikacja między kosmosem i Ziemią jest bardzo utrudniona, każdy obraz to tablica znaków ASCII. Niestety, do doktora nie dotarła informacja co one oznaczają, ale Bitstrong wie, że zostały one wybrane przez ekspertów tak, aby to co reprezentują było jak najbardziej intuicyjne (spokojnie, zawsze te same obiekty oznaczone są tym samym znakiem). Każdy znak przedstawia jeden metr kwadratowy powierzchni. Wiadomo też, że na wszystkich zdjęciach każdy metr kwadratowy zawiera w sobie maksymalnie jeden obiekt. No i oczywiście na każdym obszarze jest też co najmniej jedna małpa oraz punkt zbiórki.

Małpy są bardzo dobrze wytresowane i zawsze słuchają się poleceń. Trudność polega na tym, że wszystkie małpy na tym samym obszarze korzystają ze wspólnego kanału łączności, więc każde polecenie wydawane jest do wszystkich jednocześnie. Małpy znają tylko cztery bardzo proste komendy – POLNOC, POLUDNIE, ZACHOD i WSCHOD. Każda z nich, jak pewnie łatwo się domyślić, powoduje przesunięcie się małp w danym kierunku o jeden metr, o ile jest taka możliwość (jeśli małpa nie może z różnych przyczyn wykonać tego polecenia, stoi w miejscu).

Zaproponuj dla doktora ciąg komend, który pozwoli pokierować zwierzaki tak, aby każde z nich bezpiecznie dotarło do punktu zbiórki. Pamiętaj, żeby małpy zebrały po drodze wszystkie pozostałe kosmiczne banany – nie chcemy przecież, żeby znowu wszystkie się rozbiegły!

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita T, oznaczająca numer obszaru.
W drugim wierszu wejścia znajdują się dwie liczby całkowite N i M oddzielone pojedynczym odstępem, oznaczające wymiary tablicy ASCII reprezentującej mapę. W następnych N wierszach znajduje się po M znaków ASCII (bez znaków białych), symbolizujących zawartość zdjęcia satelitarnego.

Wyjście

Program powinien wypisać jedną liczbę całkowitą L nie większą niż 10 000, a następnie L wierszy, każdy zawierający jedno ze słów: POLNOC, POLUDNIE, ZACHOD albo WSCHOD. Powinny one przedstawiać poprawną listę komend, która umożliwi małpom z danego obszaru bezpieczne dotarcie do punktu zbiórki.

Ograniczenia

1 ≤ T ≤ 6, 1 ≤ N, M ≤ 15.

Obszary

Poniżej przedstawione są wszystkie obszary, które są do rozwiązania. W zadaniu nie będzie innych testów.

1
9 9
#########
#......@#
#.##.####
#.@#....#
####.##.#
#@#..#..#
#.#.##.##
#...#^.##
#########

2
9 9
#########
#@.....x#
#xxxx..x#
#@..#..x#
#^..x..x#
#..#x..x#
#......x#
#xxxxxxx#
#########

3
9 9
#########
#...)...#
#..@....#
#.......#
#.^...).#
#@......#
#..)....#
#......@#
#########

4
9 9
#########
#@.#...O#
#O)#....#
####....#
#...^...#
#...xxxx#
#...x.).#
#o.@xo..#
#########

5
9 9
#########
#@O#..xO#
#.....xx#
#...)...#
#.......#
#xxxxxx.#
#x@....^#
#xxxxxxx#
#########

6
13 15
###############
#xxxxxxx#xxxxx#
#.........@...#
#o###########^#
#x............#
#............x#
#)OO....x.x).x#
########x.x####
#).........@..#
#xxxxxxx#xxxxx#
#...).....@..o#
#xxxxxxxxxxxxx#
###############

Testowanie

Rozwiązania do pierwszych pięciu obszarów, bez kary czasowej za błędną odpowiedź, możesz testować na następującej stronie: https://mistrzostwa.solve.edu.pl/task/bananowa-przygoda/special.

Kapitan Kostka planuje stworzyć nową stację kosmiczną, która pozwoli mu na dokładne zbadanie galaktyki Cubix. W tym celu będzie mu potrzebne 8 sześciennych modułów, z których należy złożyć sześcienną stację.

Jednakże w przypadku kapitana Kostki nie jest to takie proste jak się wydaje, gdyż ma on bardzo wyszukany zmysł estetyczny. Aby stacja dobrze się prezentowała w telewizji, każda jej ściana (czyli wszystkie ściany modułów ją tworzących) musi być pokryta materiałem z fragmentami odpowiedniego kamienia szlachetnego. Co więcej, kapitan Kostka wie już jaki jest optymalny układ tych kamieni. Patrząc na stację badawczą od przodu są to:

• górna ścianka powinna zawierać fragmenty perły (oznaczanej kolorem 1),
• dolna ścianka powinna zawierać fragmenty cytrynu (oznaczanego kolorem 2),
• przednia ścianka powinna zawierać fragmenty szafiru (oznaczanego kolorem 3),
• lewa ścianka powinna zawierać fragmenty szmaragdu (oznaczanego kolorem 4),
• tylna ścianka powinna zawierać fragmenty rubinu (oznaczanego kolorem 5),
• prawa ścianka powinna zawierać fragmenty bursztynu (oznaczanego kolorem 6).

Kapitan Kostka znalazł już 8 modułów, z których każdy ma 3 wzajemnie sąsiadujące ze sobą ścianki zawierające fragmenty kamieni szlachetnych. Czy jesteś w stanie odpowiedzieć, czy da się z nich stworzyć stację badawczą o optymalnym układzie kamieni szlachetnych?

Wejście

Wejście składa się z 8 wierszy. Każdy z nich zawiera dokładnie 3 liczby całkowite, oddzielone pojedynczymi odstępami, oznaczające kamienie szlachetne znajdujące się na ściankach jednego z sześciennych modułów. Kolory są podane w kolejności zgodnej z ruchem wskazówek zegara, czyli jeśli przyjmiemy, że pierwsza liczba oznacza kolor górnej ścianki, druga liczba oznacza kolor prawej ścianki, to trzecia liczba oznacza kolor przedniej ścianki. Kostki te można dowolnie obracać.

Wyjście

Na wyjściu wypisz słowo TAK jeśli z podanych na wejściu modułów można złożyć stację badawczą o pożądanym układzie kamieni szlachetnych. W przeciwnym wypadku wypisz słowo NIE.

Ograniczenia

Każda z liczb reprezentujących kolory należy do zbioru {1, 2, 3, 4, 5, 6}.

Przykłady

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

TAK

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

TAK

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

NIE

Wyjaśnienia

Zestaw modułów z pierwszego testu przykładowego:

Zestaw modułów z drugiego testu przykładowego:

Zestaw modułów z trzeciego testu przykładowego:

W końcu się udało! Po wielu nieudanych próbach mały Bitek w końcu zdobył bilety na Kosmiczny Mecz! Poza zaciętym kibicowaniem swojej ulubionej drużynie, ma on jeszcze jeden cel – zdobycie autografu samego Bajkela Bordana.

Jak podają media, Bajkel przybędzie na mecz jednym z umieszczonych na stadionie portali, lecz nikt nie wie którym. Wszystkie portale mają numery od 0 do M oraz są kolejno ułożone w jednej linii, w równych odległościach. Przy każdym portalu ustawiła się już kolejka osób czekających na autografy. Sam Bajkel nie będzie miał dużo czasu, więc przed treningiem zdoła rozdać tylko K autografów. Będzie on rozdawał autografy kolejnym osobom, które stoją w kolejce przy jego portalu. Jednak osoby czekające w innych kolejkach, będą miały okazję podejść do kolejki, przy której jest Bajkel. Naturalnie, osoby które stały przy bliższych kolejkach będą mogły ustawić się w niej wcześniej. Zatem, jako pierwsze zdążą się ustawić osoby które były przy sąsiednich portalach, potem osoby które były 2 portale dalej itd. W przypadku, gdy kilka osób podejdzie do kolejki jednocześnie, jako pierwsza ustawia się ta, która przyszła na stadion wcześniej.

Po ustawieniu się wszystkich osób (łącznie z Bitkiem) w kolejkach, nazwijmy portal wygrywającym, gdy pojawienie się Bajkela w danym portalu sprawi, że Bitkowi uda się zdobyć autograf.

Bitek przyszedł na stadion ostatni, po czym zanotował w których kolejkach ustawiły się kolejne osoby. Teraz, mając wiedzę, że Bajkel przybędzie lada moment, zastanawia się do której kolejki powinien się ustawić, żeby jak największa liczba portali była dla niego wygrywająca. Postanowił, że jeśli kilka kolejek daje taką samą szansę, wybierze tę, która ma najmniejszy numer.

Czy jesteś w stanie mu pomóc i wyznaczyć, do której kolejki powinien się ustawić?

Wejście

W pierwszym wierszu wejścia podane są trzy liczby całkowite N, M oraz K, oddzielone pojedynczymi odstępami. Oznaczają one kolejno ile osób przyszło po autografy przed Bitkiem, jaki jest numer ostatniego portalu oraz ile autografów rozda Bajkel.
W drugim wierszu podane jest N oddzielonych pojedynczymi spacjami liczb całkowitych, oznaczających numery portali przy których ustawiały się osoby, które kolejno przychodziły na stadion.

Wyjście

Na wyjściu wypisz dwie liczby całkowite oddzielone spacją. Pierwsza z nich powinna oznaczać największą liczbę portali wygrywających, jaką może uzyskać Bitek. Druga liczba powinna oznaczać najmniejszy numer portalu, przy którym musi się on ustawić, aby uzyskać ten wynik.

Ograniczenia

1 ≤ K, N ≤ 1 000 000, 0 ≤ M ≤ 10¹⁸.

Przykłady

3 6 2
1 4 5

4 2

7 7 1
2 4 7 3 0 1 6

1 5

Podczas najnowszej misji statku U.S.S. Coder, kapitan Jan Bitovsky, został omyłkowo przeteleportowany na powierzchnię nieznanej dotąd planety.

Szukając sposobu na komunikację ze swoją załogą, Jan odnalazł prastary artefakt starożytnej cywilizacji Ziemi – urządzenie mobilne zdolne do połączeń międzyplanetarnych firmy Bajtorola. Niestety, pojawił się kolejny problem. Mimo że Jan, jako przedstawiciel rasy ludzkiej, doskonale zna dawny sposób zapisu numerów komórkowych, oznaczenia na klawiaturze urządzenia są już zupełnie nieczytelne. Wiadomo jedynie, że na klawiaturze znajduje się dokładnie M przycisków z cyframi w systemie o bazie M oraz jeden przycisk usunięcia ostatnio napisanego znaku (jeżeli na ekranie nie ma napisanej żadnej cyfry, to przycisk ten nic nie robi).

Jan chciałby zadzwonić do swojej załogi, do czego potrzebuje wpisać odpowiedni numer (jest on również złożony z cyfr w systemie o bazie M, czyli cyfr od 0 do M − 1). Zastanawia się, ile wynosi oczekiwana liczba kliknięć w klawiaturę, zakładając, że Jan zawsze wybiera optymalnie przyciski w danej sytuacji oraz klawisze są nierozróżnialne, dopóki nie zostaną wciśnięte. Pomóż mu!

Wejście

W pierwszym wierszu wejścia dane są dwie liczby naturalne N i M oddzielone pojedynczym odstępem, oznaczające kolejno długość numeru do załogi Jana Bitovsky’ego oraz bazę systemu liczbowego, do jakiego należą cyfry z numeru oraz klawiatury urządzenia. W drugim i ostatnim wierszu wejścia znajduje się N oddzielonych pojedynczymi odstępami liczb całkowitych – numer, który potrzeba wpisać.

Wyjście

Na wyjściu program powinien wypisać jedną liczbę całkowitą W taką, że W = P ⋅ Q⁻¹ mod  1 000 000 007, gdzie $\frac{P}{Q}$ oznacza oczekiwaną liczbę kliknięć koniecznych do wpisania numeru przez Jana, a Q⁻¹ mod  1 000 000 007 oznacza odwrotność modularną liczby Q modulo 1 000 000 007.

Ograniczenia

1 ≤ N ≤ 1 000 000, 2 ≤ M ≤ 1 000, liczby oznaczające numer są z przedziału od 0 do M − 1.

Przykład

1 2
0

666666674

Wyjaśnienie przykładu

W przykładzie są dwie cyfry (0 i 1) oraz trzeci przycisk cofania. Jan nie wie, który to który, więc przyciska dowolny z nich.

• Z prawdopodobieństwem $\frac{1}{3}$ przyciśnie on 0 i uda mu się wpisać numer do załogi.
• Również z prawdopodobieństwem $\frac{1}{3}$ przyciśnie on cofanie i nic się nie stanie. Wtedy z prawdopodobieństwem $\frac{1}{2}$ uda mu się wybrać 0. W przeciwnym razie wciśnie klawisz 1, który potem musi usunąć i wybrać ostatni pozostały przycisk, którym musi być 0. W tym scenariuszu potrzebował by 4 wciśnięć.
• Finalnie, z prawdopodobieństwem $\frac{1}{3}$ może wcisnąć jako pierwszy przycisk 1. Wtedy, jeśli jako drugi wciśnie przycisk cofania, to będzie potrzebował już tylko wybrać ostatni przycisk (w sumie trzy wciśnięcia). W najgorszym przypadku, jeśli wciśnie 0 jako drugie, to będzie potrzebował dwukrotnie użyć cofania zanim wpisze poprawny numer (łącznie 5 wciśnięć).

Łącznie otrzymujemy wartość oczekiwaną $\frac{1}{3} + \big( 2 \cdot \frac{1}{6} + 4 \cdot \frac{1}{6} \big) + \big( 3 \cdot \frac{1}{6} + 5 \cdot \frac{1}{6} \big) = \frac{16}{6}$. Odwrotność modularna 6 modulo 1 000 000 007 to 166666668, więc 16 ⋅ 166666668 = 666666674 mod  1 000 000 007.

Jest to problem interaktywny. Powinieneś wykonać operację flush po wypisaniu każdego wiersza. W C++ możesz użyć funkcji fflush(stdout) lub cout.flush(), w Javie System.out.flush(), w Pythonie sys.stdout.flush().

Bajter Bitl znowu wdał się w kłopoty w kosmosie. Żeby wykaraskać się z tarapatów, musi w idealny sposób rozdysponować pozostałe K litrów paliwa na N silników.

Każdy silnik w jego statku pozwala na przebycie pewnej odległości, zależnej od tego, ile litrów paliwa się do niego wleje. Dokładniej, dla i-tego silnika istnieje pewna funkcja f_i, określona na liczbach całkowitych od 0 do K, która jest nieujemna i ściśle malejąca. Po wlaniu T_i litrów paliwa do i-tego silnika, można przelecieć $\sum_{t = 0}^{T_i} f_i(t)$ jednostek astronomicznych. Przez specyficzną konstrukcję silników, zachodzi f_i(x) ≠ f_j(y), jeśli i ≠ j lub x ≠ y.

Niestety, tabelka z dokładnymi wartościami tych funkcji uległa zniszczeniu. Na szczęście, ostała się niezwykle stara maszyna z technologią z XX wieku, która pozwala porównywać wartości funkcji. Bajter może z jej pomocą odpowiedzieć na zapytanie: “Czy wartość funkcji f_i(x) jest większa od wartości funkcji f_j(y)?”.

Bajter chce, mimo tak ograniczonej technologii, wykorzystać każdy litr paliwa do perfekcji i dotrzeć najdalej jak jest to możliwe.

Niestety, przez wolne działanie maszyny porównującej, Bajter może zadać tylko 5 000 zapytań do maszyny, zanim dopadną go bandyci. Czy jesteś w stanie mu pomóc i uratować jego statek?

Interakcja

Na początku sprawdzaczka podaje (na standardowe wejście programu) dwie liczby całkowite N i K, oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę silników i liczbę litrów paliwa, którymi dysponuje Bajter Bitl.
Twój program może zadać co najwyżej 5 000 zapytań. Każde zapytanie powinno składać się ze znaku zapytania i czterech liczb całkowitych i, x, j, y (1 ≤ i, j ≤ N, 0 ≤ x, y ≤ K), oddzielonych pojedynczymi odstępami. Po wypisaniu wiersza, należy wczytać jedną liczbę całkowitą 0 bądź 1, oznaczającą odpowiednio, że f_i(x) < f_j(y) lub f_i(x) > f_j(y). W zadanym zapytaniu powinien zajść co najmniej jeden z następujących warunków: i ≠ j lub x ≠ y.
Jeżeli znajdziesz optymalne rozwiązanie T₁, T₂, …, T_N, wypisz wiersz składający się z wykrzyknika i kolejnych wartości ciągu T_i, pooddzielanych pojedynczymi odstępami. Wypisanie rozwiązania nie wlicza się do limitu zapytań.
Interaktor może być adaptywny i zależeć od wyników Twoich poprzednich zapytań. Możesz założyć, że odpowiedzi na zadane przez Ciebie zapytania są poprawne tj. istnieją pewne funkcje f_i, które spełniają wszystkie podane założenia.
Uwaga: błędne zapytanie albo przekroczenie limitu zapytań może zakończyć się werdyktem błędu wykonania.

Ograniczenia

1 ≤ N ≤ 32, 1 ≤ K ≤ 2³⁰.

Przykładowa interakcja

O nie! Koniec jest już blisko! Najlepsi światowi astronomowie właśnie odkryli ogromny meteoryt, który zmierza dokładnie w kierunku słońca! W momencie gdy dojdzie do zderzenia, wszystkie planety w całym układzie planetarnym ulegną zniszczeniu. Jedyną nadzieją jest teleportacja ludności na inny zbiór planet, którym zagłada nie grozi.

Sztab kryzysowy rozpoczął już działania w tym kierunku. Z racji, że podczas zderzenia N starych planet ulegnie zniszczeniu, zostało już wybrane inne N nowych planet, na które zostaną przetransportowani mieszkańcy. Będzie się to działo poprzez specjalny system teleportów, z których każdy będzie miał możliwość przeniesienia dowolnej liczby osób z pewnej starej planety na pewną nową planetę.

Plan sieci teleportów musi zapewniać komfort teleportowanym mieszkańcom. Z tego względu system teleportów będzie musiał spełniać kryterium, że dla każdego zbioru pewnych k starych planet, ich teleporty będą prowadzić do co najmniej k różnych nowych planet. Tylko takie plany będą uznawane za dopuszczalne, gdyż plany przenosin nie spełniające tego kryterium mogą spowodować, że mieszkańcom będzie za ciasno.

Jednakże są też grupy mieszkańców, które nie powinny się nadmiernie rozprzestrzenić, dlatego niektóre zbiory starych planet powinny być ograniczone. Oznacza to, że dla pewnych zbiorów k starych planet, ich teleporty powinny prowadzić do dokładnie k różnych nowych planet.

Sztab kryzysowy zlecił już pewnemu studentowi przygotowanie układu teleportów. Jednakże, jak się można było domyślić, plan ten nie dość, że niekoniecznie jest optymalny pod względem ilości teleportów, to jeszcze nie wiadomo czy jest dopuszczalny! Dlatego teraz sztab zwrócił się o pomoc do kogoś bardziej doświadczonego, czyli właśnie do Ciebie.

Twoim zadaniem jest teraz weryfikacja oraz optymalizacja tego planu. Jeżeli dostarczony Tobie plan nie jest dopuszczalny, powinieneś udowodnić to Sztabowi, wskazując zbiór planet, który nie spełnia tego kryterium. W sytuacji, gdy jednak plan jest dopuszczalny, Twoim zadaniem jest wskazanie dopuszczalnego planu, który minimalizuje liczbę teleportów. Powinien on spełniać kryterium, że jeśli jakiś zbiór planet był wcześniej ograniczony, to w nowym planie też powinien być on ograniczony. Analogicznie, jeśli zbiór planet nie był ograniczony, to w nowym planie też nie powinien być.

Czy podołasz temu arcytrudnemu zadaniu? Teraz zależą od Ciebie losy nie tylko świata, ale i całego układu planetarnego!

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz M, oddzielone pojedynczym odstępem. Liczba N oznacza zarówno liczbę starych, jak i nowych planet. Liczba M oznacza liczbę teleportów w pierwotnym planie teleportacji.
W kolejnych M wierszach podane są opisy kolejnych teleportów. Każdy z nich zawiera dwie liczby całkowite x oraz y, oddzielone pojedynczym odstępem, oznaczające, że na starej planecie o numerze x zaplanowany jest teleport na nową planetę y. Każda para x, y może wystąpić na wejściu co najwyżej raz. Stare planety są numerowane liczbami od 1 do N, a nowe numerami od N + 1 do 2 ⋅ N.

Wyjście

Jeżeli plan teleportacji podany na wejściu nie jest dopuszczalny, w pierwszym wierszu wyjścia wypisz jedno słowo NIE. W drugim wierszu wyjścia wypisz liczbę k, a w trzecim wierszu wypisz k liczb x₁, x₂, …, x_k, oddzielonych pojedynczymi odstępami. Liczby te powinny oznaczać, że w pierwotnym planie teleportacji ze zbioru starych planet S = {x₁, x₂, …, x_k} nie da się teleportować do k różnych nowych planet.
Jeżeli jednak podany na wejściu plan teleportacji jest dopuszczalny, w pierwszym wierszu wyjścia wypisz jedno słowo TAK. W drugim wierszu wyjścia wypisz liczbę M′, oznaczającą liczbę teleportów w nowym, również dopuszczalnym planie teleportacji. Następnie, w kolejnych M′ wierszach wypisz kolejne teleporty z nowego planu, w takim samym formacie jak na wejściu.

Ograniczenia

1 ≤ N ≤ 1000, 0 ≤ M ≤ N², dla każdego zaplanowanego teleportu zachodzi 1 ≤ x ≤ N, N + 1 ≤ y ≤ 2 ⋅ N.

Przykłady

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

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

3 4
1 4
1 5
2 6
3 6

NIE
2
2 3 

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

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

Bitolandia postanowiła dołączyć do wyścigu o zaludnienie Proximy Centauri b. Pierwszym krokiem, jaki planuje wykonać, jest wysłanie tam dwóch statków, oznaczonych po prostu jako A i B, które zbadają tamtejsze warunki atmosferyczne.

Inżynier Kowalski jest odpowiedzialny za konfigurację ustawień i sprawdzenie wszystkich parametrów obu statków. Jednym z tych parametrów są prędkości, z jakimi będą poruszać się statki podczas lotu. Są to dwie, możliwie bardzo duże liczby V_A i V_B. Dodatkowo wszyscy mieszkańcy Bitolandii są bardzo przesądni. W Bitolandii cyfra 1 kojarzy się ze zdradą, 4 z biedą, 6 z utratą pracy, 8 z zapętlonym programem, 9 z brakiem internetu, a 0 z pustką. Dlatego też Kowalski w ustawieniach używał tylko cyfr 2, 3, 5 i 7. Tak było i w przypadku prędkości.

Zostało już mało czasu do startu, gdy Kowalski przypomniał sobie bardzo ważną rzecz: Przecież statek A musi odpowiednio przygotować lądowisko dla statku B! Dlatego konieczne jest, aby prędkość V_A była większa niż V_B. Kowalski przeraził się tym faktem, ale udało mu się zachować zimną krew. Wie, że jedyna operacja, którą jest teraz w stanie wykonać, to jedna zamiana dwóch cyfr miejscami. Może on wybrać dowolne dwie pozycje z dowolnych liczb.

Czy jesteś w stanie mu pomóc? Czy potrafisz zweryfikować czy wyprawa kosmiczna jest jeszcze do uratowania, a jeśli tak, to jak to należy zrobić?

Wejście

W pierwszym wierszu wejścia podana jest jedna liczba całkowita V_A, prędkość statku A.
W drugim wierszu wejścia podana jest jedna liczba całkowita V_B, prędkość statku B.

Wyjście

Jeżeli nie da się zamienić dwóch cyfr miejscami w taki sposób, że prędkość V_A będzie większa od prędkości V_B, na wyjściu wypisz jedno słowo NIE.
Jeżeli taka zamiana nie jest potrzebna, na wyjściu wypisz jedno słowo OK.
W przeciwnym przypadku na wyjściu wypisz dwa wiersze, zawierające informacje które cyfry z których prędkości należy zamienić ze sobą, aby otrzymać rozwiązanie. Dokładniej, w pierwszym wierszu wyjścia wypisz wartości s₁ oraz i₁, a w drugim wartości s₂ oraz i₂, takie że s₁ i s₂ są literkami A lub B, 1 ≤ i₁ ≤ |V_s1| oraz 1 ≤ i₂ ≤ |V_s2|. Wartości te powinny oznaczać, że aby uzyskać poprawne ustawienia, należy zamienić cyfrę na pozycji i₁ w prędkości V_s1 z cyfrą na pozycji i₂ w prędkości V_s2.

Ograniczenia

1 ≤ V_A, V_B ≤ 10^{1 000 000}. Liczby V_A oraz V_B składają się wyłącznie z cyfr 2, 3, 5 i 7.

Przykłady

375
537

A 1
B 1

27
355

NIE

5232375235757527357527532
2775527357527357352735273

OK

Jednym z kroków podczas kolonizacji sąsiednich planet jest sprawdzenie jakie panują na nich warunki atmosferyczne. W tym celu Bajtazar wyhodował bakterię, która każdego dnia dzieli się na dokładnie k identycznych bakterii. Parametr k jest liczbą całkowitą zależną od warunków panujących na planecie, na której aktualnie znajduje się bakteria. W przypadku wyjątkowo złych warunków atmosferycznych bakteria może się w ogóle nie dzielić (wtedy k = 1). Z poczynionych wcześniej obserwacji, Bajtazar wie, że warunki na każdej planecie nigdy się nie zmieniają.

Bajtazarowi udało się już rozesłać na różne planety po pewnej liczbie bakterii. Rozesłał też stacje nadawcze wysyłające codzienne raporty z liczbą bakterii na każdej planecie. Niestety, jak to jednak bywa w kosmosie, aparatura okazała się zawodzić. Nie dość, że niektóre raporty przestały dochodzić do Bajtazara, to jeszcze żadne z nich nie miały informacji z jakiej planety pochodzą, a zdarzało się nawet tak, że pomiary z kilku dni na jednej planecie przychodziły w losowej kolejności.

Bajtazar ma teraz do dyspozycji jeden długi raport, w którym znajdują się kolejne liczności bakterii, jakie udało się zanotować z przychodzących do niego informacji. Teraz jego plan polega na tym, aby wyciąć z niego spójny fragment, w którym znajdą się takie pomiary, które mogły pochodzić z co najmniej trzech kolejnych dni na jednej z planet. Czy jesteś w stanie mu pomóc i odpowiedzieć na ile sposobów może on wybrać taki fragment raportu?

Wejście

W pierwszym wierszu wejścia podana jest jedna liczba całkowita N, oznaczająca długość raportu, jaki udało się uzyskać Bajtazarowi.
W drugim wierszu podane jest N, pooddzielanych pojedynczymi odstępami liczb całkowitych, oznaczających kolejne liczności bakterii w raporcie.

Wyjście

Na wyjściu wypisz jedną liczbę, oznaczającą liczbę przedziałów, które zawierają taki fragment raportu, że znajdują się na nim co najmniej trzy wartości, które mogły być zanotowane na jednej planecie w ciągu kolejnych dni.

Ograniczenia

1 ≤ N ≤ 10⁵, wszystkie liczby w raporcie są z przedziału od 1 do 1 000 000 włącznie.

Przykład

10
3 1 8 15 27 16 2 7 9 4

4

Słynny na cały świat astrofizyk Mleil waGrasse Tysok wyczytał ostatnio o istnieniu bliźniaczych gromad galaktyk. Zanim jednak przekaże tę wiedzę szerszej publiczności w swoim programie popularnonaukowym S.tarT-ok, chce na własną rękę potwierdzić ich istnienie. Mleil jest świadom, że ogrom wszechświata jest potężny (niemal tak potężny, jak jego umiejętności obserwacyjne), postanowił więc spróbować szczęścia i znaleźć jakąś do tej pory nieznaną parę bliźniaczych gromad.

W tym celu spojrzał przez swój TLEskop na niezbadany jeszcze skrawek nieba, w którym znajduje się w szeregu dokładnie 2^K + 1 galaktyk, a i-ta z nich składa się z g_i (0≤g_i<4^K) gwiazd.

Gromada galaktyk to dowolny niepusty przedział galaktyk spośród znajdujących się w polu obserwacji Mleila. Cecha gromady jest równa wartości alternatywy rozłącznej (potocznie zwanej xor-em) liczb gwiazd galaktyk zawartych w tej gromadzie.

Dwie gromady są bliźniacze wtedy i tylko wtedy, gdy mają równe cechy oraz przedziały galaktyk im odpowiadające są rozłączne.

Napisz program, który wczyta opis skrawka nieba obserwowanego przez astrofizyka, a następnie albo wypisze położenie dowolnej pary bliźniaczych gromad, albo wypisze -1 jeżeli takie gromady nie istnieją.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna T oznaczająca liczbę przypadków testowych.
W kolejnych wierszach znajdują się opisy przypadków testowych, z których każdy składa się z dokładnie dwóch wierszy.
W pierwszym wierszu każdego przypadku testowego znajduje się jedna liczba naturalna K. W drugim znajduje się 2^K + 1 liczb oddzielonych pojedynczymi odstępami, które są wartościami g_i dla kolejnych galaktyk.

Wyjście

Dla każdego przypadku testowego w osobnej linii na wyjściu powinny się znaleźć cztery liczby całkowite a, b, c oraz d oznaczające zakresy [a,b] oraz [c,d] kolejno pierwszego oraz drugiego przedziału (pierwszy nie musi zaczynać się wcześniej od drugiego, ale przedziały muszą być rozłączne). Jeżeli odpowiedź jest negatywna, to należy zamiast tego wypisać jedną liczbę naturalną -1.

Ograniczenia

1 ≤ T ≤ 2¹⁷, 0 ≤ K ≤ 17, 0 ≤ g_i < 4^K,
suma wartości 2^K + 1 po wszystkich przypadkach testowych nie przekracza 2¹⁸.

Przykład

2
2
4 15 0 7 11 8 3 2
1
0 1 2 3

5 5 1 2
2 2 3 4

Po ostatnim starciu ze sługami imperium rebelianci ponieśli olbrzymie straty i zostali rozbici, co oznacza, że nastały mroczne czasy dla naszego skrawka galaktyki. Na szczęście jeszcze nie cała nadzieja przepadła. W drodze na wykład tajnych kompletów w Bajtku obudziła się dusza rajdowca i rozpędził się przypadkiem do 142 kilometrów (88 mil) na godzinę. Kiedy dojechał na miejsce, okazało się, że do wielkiej bitwy zostało jeszcze dużo¹ czasu – ma do niej dojść dopiero za K godzin.

Rebelianci umieścili po jednym statku na każdej z N planet, pomiędzy którymi jest M jednokierunkowych tuneli czasoprzestrzennych. Pokonanie każdego z nich zajmuje dokładnie godzinę. Imperium bardzo dokładnie zaplanowało bitwę, ale jego wojska nie potrafią dynamicznie dostosowywać się do sytuacji. Dlatego wystarczy wytworzyć sztuczny ruch jednostek tuż przed bitwą, aby osiągnąć zwycięstwo. Ze względu na liczne i skomplikowane strategiczne uwarunkowania, które tutaj pominiemy, rebelianci ostrzeżeni przez Bajtka chcieliby wybrać dwa statki, które będą latać przez cały czas pozostały do bitwy (dokładnie K godzin), a każdy z nich ostatecznie wyląduje na planecie, z której startował przeciwny statek. Ze względu ma małą ilość paliwa, dopuszczalną strategią jest też wybranie jednego statku, który również będzie latał bez przerwy przez K godzin, a następnie wróci na swoją pierwotną pozycję.

Na ile sposobów dowództwo rebeliantów może wybrać statki do wypełnienia tej misji i odmienienia losów galaktyki?

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite N, M oraz K, oddzielone pojedynczymi odstępami, oznaczające odpowiednio liczbę planet, tuneli czasoprzestrzennych i godzin pozostałych do bitwy.
Kolejne M wierszy zawiera po dwie liczby całkowite x i y oznaczające istnienie tunelu czasoprzestrzennego, który może przenieść statek z planety x w dowolnym momencie na planetę y godzinę później.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą: liczbę możliwych sposobów wyboru dwójki lub pojedynczego statku.

Ograniczenia

1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000, N³ ≤ K ≤ 10¹⁸, 1 ≤ x, y ≤ N, x ≠ y.

Przykład

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

5

W ruchu kosmicznym, podobnie jak w ruchu drogowym, nie ma miejsca na pomyłki. Dlatego też bardzo ważnym jest zarówno posiadanie, jak i regularne odnawianie prawa lotu, czyli kosmicznej wersji prawa jazdy. Obowiązek ten nie ominął też Bajtka.

Egzamin na prawo lotu odbywa się na małym statku Gołąb Dekady. Jest to statek w kształcie trójkąta równoramiennego, w którym ramiona mają długość co najmniej taką jak podstawa.

Jednym z elementów egzaminu jest lądowanie na lądowisku o kształcie koła. Zadaniem egzaminowanego jest nie tylko wylądowanie, ale też określenie czy statek jest w stanie zmieścić się w obszarze lądowiska. To okazało się największą trudnością dla Bajtka. Czy jesteś w stanie mu pomóc i policzyć czy statek rzeczywiście zmieści się na lądowisku?

Przyjmujemy, że statek musi się w całości zmieścić na lądowisku i nie może dotykać jego krawędzi.

Wejście

W pierwszym i jedynym wierszu wejścia podane są trzy liczby całkowite A, B oraz R, oddzielone pojedynczymi odstępami. Liczby A i B oznaczają wymiary Gołębia Dekady, gdzie A wyznacza długość podstawy, a B oznacza długość ramienia trójkąta równoramiennego, którego kształt ma statek. Liczba R oznacza promień koła wyznaczającego lądowisko.

Wyjście

Wypisz na wyjściu jedną linię zawierającą słowo TAK jeżeli Gołąb Dekady jest w stanie zmieścić się na lądowisku. W przeciwnym przypadku wypisz NIE.

Ograniczenia

1 ≤ A ≤ B ≤ 100, 1 ≤ R ≤ 100.

Przykłady

6 8 4

NIE

6 7 13

TAK

39 98 50

TAK

61 63 36

NIE

Mieszkańcy planety Lex w galaktyce K-TY mierzą czas inaczej niż Ziemianie. Na ich zegarach wyświetlają się trzy dodatnie liczby a, b i c, gdzie liczba a jest zawsze A-cyfrowa, liczba b jest B-cyfrowa, a liczba c jest C-cyfrowa. Zapisy tych liczb nigdy nie zawierają zer wiodących. Z niezrozumiałych dla nas powodów, liczba c zawsze jest równa sumie liczb a i b. Standardowym zapisem czasu jest więc ciąg znaków postaci a + b = c.

Pilot Bajtek odwiedza właśnie planetę Lex w celach dyplomatycznych. Prezydent planety, który lubi zadawać zagadki algorytmiczne przyjezdnym, umówił się z Bajtkiem na spotkanie o czasie, którego standardowy zapis jest K-tym najmniejszym leksykograficznie spośród wszystkich poprawnych zapisów o danych długościach. Pomóż Bajtkowi i podaj czas, w którym odbędzie się spotkanie lub ustal, że prezydent się pomylił i wszystkich możliwych zapisów czasu jest mniej niż K.

Ciąg znaków s jest leksykograficznie mniejszy od ciągu znaków t wtedy i tylko wtedy, gdy zachodzi jedno z poniższych:

• s jest prefiksem t i jest od niego krótsze,
• na pierwszej pozycji, na której s różni się od t, w s występuje litera o mniejszym kodzie ASCII niż odpowiadająca jej litera w t.

Wejście

W pierwszym i jedynym wierszu wejścia znajdują się cztery liczby A, B, C i K, oddzielone pojedynczymi znakami odstępu.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinien znaleźć się K-ty leksykograficznie zapis czasu, zgodny z wymaganymi długościami wszystkich liczb. Pomiędzy liczbami i operatorami arytmetycznymi (+ i =) powinny występować pojedyncze odstępy.
Jeżeli różnych wyświetlanych zapisów czasu jest mniej niż K, na wyjściu wypisz jedno słowo NIE.

Ograniczenia

1 ≤ A, B, C ≤ 6, 1 ≤ K ≤ 10¹².

Przykłady

1 1 2 3

2 + 9 = 11

2 1 1 1

NIE

2 2 3 1

10 + 90 = 100

5 6 6 176032534

10197 + 821839 = 832036

Bajtek jest naczelnym programistą na niszczycielu należącym do gwiezdnej floty Konfederacji Niezależnych Systemów Operacyjnych. Jednym z jego zadań jest sprawdzanie, czy elektroniczne mózgi maszyn nie zostały uszkodzone podczas walk.

Pierwszym testem, który Bajtek przeprowadza, jest ustawienie robotów w kilka szeregów, jeden za drugim. Następnie porównuje on pozycje zarejestrowane przez maszyny z rzeczywistymi i na tej podstawie ocenia, czy któraś z nich jest wadliwa.

Niestety, po ostatniej bitwie o bitowe rubieże ze złośliwymi robakami, uszkodzeniu uległ system detekcji położenia robotów. Bajtkowi udało się jedynie wydobyć z każdej z maszyn informację o tym, ile jednostek stało na lewo od niej w jej szeregu podczas testu.

Zbliża się czas złożenia Wielkiemu Deklaratorowi raportu z testu. Bajtek postanowił, że w celu uniknięcia nagany za niedziałający system statku, sfinguje ułożenie robotów, tak żeby było one zgodne z tym, co twierdzą maszyny.

Pomóż mu i napisz program, który wypisze TAK, gdy istnieje ułożenie robotów w szeregi zgodne z ich zeznaniami lub NIE w przeciwnym przypadku (wtedy Bajtek będzie musiał przyjrzeć się każdej maszynie z osobna i spróbować wydedukować, która z nich się popsuła, zanim spotka go gniew Wielkiego Deklaratora).

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę robotów.
W drugim wierszu wejścia znajduje się N liczb całkowitych l₁, l₂, …, l_N, pooddzielanych pojedynczymi odstępami. Liczba l_i jest równa liczbie maszyn na lewo od i-tego robota w jego szeregu.

Wyjście

Twój program powinien wypisać TAK, jeżeli istnieje ułożenie robotów w szeregi zgodne z opisem lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ l_i < 1 000 000.

Przykłady

6
0 1 2 0 1 0

TAK

###
##
#

9
0 0 0 0 1 1 1 2 2

TAK

###
##
###
#

3
0 0 2

NIE

Do Twardowskiego to mi jednak trochę brakuje, ten to wiedział, jak sprawnie umknąć wierzycielom – tak właśnie myślał sobie Ban Bajtolo, kiedy był prowadzony przed oblicze Wielkiego Jaszczura – no cóż, przynajmniej ja nikomu duszy nie obiecywałem.

Wielki Jaszczur nie był w humorze do podejmowania poważnych decyzji, więc stwierdził, że kłopotliwy dłużnik zostanie zamrożony i przechowany w specjalnym magazynie przez N lat, a potem się zobaczy. Magazynier zabrał Bana Bajtolo i umieścił go w maszynie hibernującej. Jej obsługa jest dość prosta, wystarczy podać liczbę lat, po której zawartość ma być rozmrożona, a następnie wcisnąć enter. Niestety, urządzenie jest wiekowe i przyjmuje wejście tylko w systemie jedynkowym (I to jeden, II to dwa, a IIIIIIIIIIIIIIII oznacza szesnaście). Na ekranie początkowo znajduje się I (zapis liczby jeden), magazynier może zmieniać tę wartość przy użyciu następujących operacji:

• zaznacz wszystko – zaznacza całą zawartość ekranu,
• kopiuj – umieszcza zaznaczoną część napisu w schowku, który początkowo jest pusty,
• wklej – dopisuje zawartość schowka na koniec liczby znajdującej się na ekranie.

Jakiej minimalnej liczby powyższych trzech operacji magazynier potrzebuje, żeby na ekranie pojawił się zapis liczby N?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna T oznaczająca liczbę zapytań. Każdy z kolejnych T wierszy opisuje jedno zapytanie i składa się z jednej liczby naturalnej N – pożądanej długości hibernacji Bana Bajtolo.

Wyjście

Dla każdego zapytania w osobnym wierszu wyjścia należy wypisać jedną liczbę naturalną – minimalną liczbę operacji potrzebną do uzyskania zapisu odpowiedniej liczby.

Ograniczenia

1 ≤ N ≤ 10⁶, 1 ≤ T ≤ 40 000.

Przykład

2
2
3

3
4