Contest problemset description

Jasiu, wielki fan pizzy, postanowił zrobić niespodziankę swoim przyjaciołom i przygotować ogromną pizzę o promieniu R. Jako wielbiciel matematyki i estetyki, Jasiu chce podzielić pizzę na dokładnie N równych części. Jednak zamiast klasycznego krojenia w trójkątne kawałki od środka, Jasiu ma swój unikalny sposób – kroi pizzę za pomocą linii prostych równoległych do osi OX.

Przyjmij, że środek pizzy znajduje się w punkcie (0,0), a każde cięcie to prosta postaci y = h_i, która przecina pizzę na mniejsze kawałki, mające takie same powierzchnie. Twoim zadaniem jest pomóc Jasiowi znaleźć odpowiednie wysokości h₁, h₂, …, h_N − 1, aby pizza była idealnie podzielona na N równych części.

Wejście

W pierwszym wierszu znajdują się dwie liczby N oraz R, będące odpowiednio liczbą osób oraz promieniem pizzy.

Wyjście

W N − 1 wierszach powinny znaleść się nierosnące wysokości, na których należy przeciąć pizze.

Ograniczenia

2 ≤ N, R ≤ 10⁴

Odpowiedź będzie zaakceptowana, jeśli błąd względny lub bezwzględny od poprawniej odpowiedzi będzie mniejszy od 10⁻⁶.

Przykład

5 3

1.47558549829113
0.47320858140005
-0.47320858140005
-1.47558549829113

3 5

1.32466042301388
-1.32466042301388

Jaś bardzo lubi gofry. Lubi je do tego stopnia, że postanowił kupić sobie jednego ogromnego gofra. Gofry jak wszyscy dobrze wiedzą składają się z kwadracików układające się w kształ kraty, więc ma sens aby ich długość i szerokość mierzyć właśnie tymi kwadracikami. Gofr Jasia ma wymiary N na M kwadracików.

Jako entuzjasta gofrów, Jaś ma w swojej kuchni sporą kolekcję dodatków. Jest ona na tyle duża, że półka na której ona leży ledwo wytrzymuje ciężar tejże kolekcji. No i problem w tym, że półka ta nie wytrzymała i wszystkie dodatki spadły na majestatycznego gofra Jasia.

Jasio początkowo był zdruzgotany całym zajściem, gdyż nakładanie dodatków jest jego ulubioną czynnością, ale po chwili zauważył, że część tego gofra da się jeszcze odratować. Jego planem jest wycinanie kawałków gofra, które nie mają na sobie żadnych dodatków. Oczywiście herezją byłoby przecięcie gofra przechodzące przez kwadraciki lub wycięcie gofra, który nie jest prostokątem, dlatego rozważamy tylko prostokątne kawałki gofra, które albo zawierają dany kwadracik w całości albo wcale.

Jako że możliwości wycięcia pierwszego kawałka jest całkiem dużo, to Jasio poprosił Ciebie o pomoc w policzeniu dla każdych możliwych wymiarów A i B ile jest możliwości wycięcia suchego gofra o tych wymiarach. Jasiu ma wyjątkowo wprawione oko, dlatego rozróżniamy gofry o wymiarach A na B oraz gofry o wymiarach B na A.

Wejście

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite N i M będące odpowiednio liczbą wierszy oraz liczbą kolumn gofra.
W następnych N wierszach znajduje się opis gofra, w i–tym wierszu znajduje się ciąg znaków S_i o długości M. Jeżeli S_i, j jest równe ‘#’, to kwadracik w i–tym wierszu i j–tej kolumnie gofra został pokryty dodatkami. W przeciwnym wypadku S_i, j będzie równe ‘.’.

Wyjście

W pierwszych (jedynych) N wierszach wyjścia powinno się znaleźć po M liczb całkowitych, j–ta liczba w i–tym wierszu powinna być równa liczbie sposób wycięcia gofra o wymiarach i na j.

Ograniczenia

1 ≤ N, M ≤ 2 000.

Przykład

2 3
..#
...

5 3 1 
2 1 0 

W kuchni kluczowe jest idealne zbalansowanie smaków. Podczas przygotowywania potrawy musisz dodać odpowiednią ilość cukru oraz soli, aby uzyskać perfekcyjny efekt. Przepis, który otrzymałeś, składa się z N kroków. Każdy krok określa, czy należy dodać cukier lub sól w ilości będącej potęgą liczby 2.

Jeśli w kroku i przepis ma literę C, dodajesz 2ⁱ jednostek cukru, a jeśli przepis ma literę S, dodajez 2ⁱ jednostek soli.

Twoim zadaniem jest sprawdzenie, czy po wykonaniu wszystkich kroków przepisu, potrawa jest słona, słodka czy idealnie zbalansowana.

Wejście

W pierwszym wierszu znajduje sie liczba N będąca długością przepisu.

W kolejnym wierszu znajduje się napis długości N złożony z liter C oraz S.

Wyjście

W pierwszym i jedynym wierszu powinno znaleść się SLONA gdy dodasz więcej soli niż cukru, SLODKA gdy dodasz więcej cukru niż soli lub BALANS gdy dodasz tyle samo cukru i soli.

Ograniczenia

1 ≤ N ≤ 65.

Przykład

4
SCSC

SLODKA

3
CSS

SLONA

Ulubioną zupą Jasia jest zupa literkowa (zupa pomidorowa z makaronem w kształcie liter). Sympatia Jasia do tej zupy wynika z możliwości grania w gry słowne podczas jedzenia. Ponieważ Mama Jasia ugotowała dla niego dzisiaj tę zupę, Jasio od razu zabrał się do jej konsumpcji. W tym momencie w zupie znajduje się dziewięć liter, które ułożyły się w kształt kraty 3x3. Jasio wymyślił pewne słowo S i zaczął się zastanawiać, czy jest w stanie jednym zgrabnym ruchem nabrać to słowo na łyżkę.

Ruch nazwiemy zgrabnym, jeśli każda nabrana na łyżkę litera (poza pierwszą) -– przed rozpoczęciem nabierania liter –- znajdowała się obok poprzedniej nabranej litery. Formalnie, niech Z_i, j oznacza literę znajdującą się w i–tym wierszu oraz j–tej kolumnie kraty. Wtedy dla każdej pary kolejnych liter Z_i1, j1 oraz Z_i2, j2 musi zachodzić warunek |i₁−i₂| + |j₁−j₂| = 1.

Pomóż Jasiowi ustalić, czy jest w stanie nabrać na łyżkę słowo S jednym zgrabnym ruchem, zaczynając od litery znajdującej się w pierwszym wierszu i pierwszej kolumnie kraty (Z_1, 1).

Wejście

W pierwszym wierszu wejścia znajduje się wymyślone przez Jasia słowo S.
W następnych trzech wierszach znadują się trzyliterowe słowa będące opisem położenia liter w zupie. j–tą literę w i–tym wierszu oznaczamy przez Z_i, j.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno się znaleźć TAK, jeżeli jest możliwe zagarnięcie literek na łyżkę, aby znajdowało się na niej słowo S, lub NIE w przeciwnym przypadku.

Ograniczenia

Słowo S ma dziewięć liter. Z_i mają po trzy litery. S oraz Z zawierają wyłącznie litery alfabetu angielskiego.

Przykład

literkowa
lit
kre
owa

TAK

Jasiu dostał zalecenie od dietetyka, że: musi ograniczyć spożywanie niezdrowych potraw oraz zacząć “trzymać linię”. Jak usłyszał, tak zrobił. Na następne N dni zaplanował po M potraw. Rozpisał je wszystkie w prostokąt N × M i zastanawia się, jak dotrzymać zaleceń fachowca.

Każdą z potraw opisał jako pizzo-podobną lub sałatko-podobną, co oznacza tyle, że potrawa zwiększa lub zmniejsza jego wagę. Jasiu poprzez “trzymanie linii”, zrozumiał dwie następujące rzeczy:

1. Potrawy, które zje, stanowią ścieżkę w prostokącie z górnego lewego do dolnego prawego rogu, poruszając się wyłącznie w prawo lub w dół.

2. Nie może przytyć, ani schudnąć, czyli potraw pizzo-podobnych ma być tyle co salatko-podobnych.

Czy dla podanych potraw na najbliższe N dni, możliwe jest stworzenie diety cud dla Jasia?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M opisujące wymiary prostokąta Jasia.

W następnych N wierszach znajduje się ciąg o długości M złożony z liter P oraz S, opisujący czy w danym polu potrawa jest pizzo-podobna lub sałatko-podobna.

Wyjście

W pierwszym wierszu wyjścia powinno znaleźć się słowo NIE, gdy nie jest możliwe stworzenie diety cud. Jeśli istnieje, wypisz TAK oraz słowo długości (N+M−2), składające się z liter P (ruch w prawo) i D (ruch w dół), opisujące ścieżkę diety Jasia.

Jeśli istnieje wiele poprawnych odpowiedzi, wypisz dowolną z nich.

Ograniczenia

1 ≤ N, M ≤ 1000

Przykład

3 4
PSSS
SPPS
PPPS

TAK
PDPPD

3 4
PSPP
SPSP
PSPP

NIE

1 1
P

NIE

3 4
SSSS
PSPS
PPSP

TAK
DPPDP

2 4
PPSP
SSPS

NIE

Jasiu przyszedł do supermarketu po codzienne zakupy i jak zawsze poszukuje swoich ulubionych batoników. Niestety, supermarket jest ogromny, a stoisko znajduje się w jednym z wielu działów. Jasiu stojąc w punkcie (0,0) zapytał ekspedientkę, jak tam dotrzeć, i otrzymał od niej szczegółową instrukcję N komend, gdzie i-ta z nich jest postaci: “Kieruj się w <LEWO|PRAWO|GÓRĘ|DÓŁ> przez D_i metrów, a następnie…”.

Jednak jako matematyk, Jasiu nie zapamiętał kierunków, a jedynie długości odcinków, przez które ma iść. Ostatnią szansą na odnalezienie ukochanych batoników Jasia jest jego ślepy strzał do miejsca (X,Y). Sprawdź, czy istnieje przyporządkowanie kierunków do podanych długości, tak aby finalnie Jasiu znalazł się w punkcie (X,Y).

Wejście

W pierwszym wierszu znajdują się trzy liczby N, X oraz Y, oznaczające liczbę komend oraz ślepy strzał Jasia. W kolejnym wierszu znajduje się N liczb opisujących kolejne długości w komendach ekspedientki.

Wyjście

W pierwszym wierszu wypisz NIE, jeśli żadne przyporządkowanie kierunków nie znajdzie się w (X,Y). W przypadku gdy takie przyporządkowanie istnieje, wypisz TAK, a w następnym wierszu napis długości N złożony z G, D, L, P, taki że: jeśli w i-tej komendzie idziesz w górę wypisz G, jeśli idziesz w dół wypisz D, jeśli idziesz w lewo wypisz L, a jeśli w prawo to P.

Ograniczenia

1 ≤ N ≤ 2000, 0 ≤ |X|, |Y| ≤ 3.6 × 10⁶, 1 ≤ D_i ≤ 1800

Przykład

3 3 0
1 1 1

TAK
PPP

3 2 -2
1 2 3

TAK
GPD

2 1 0
1 6

NIE

5 6 7
1 3 5 7 9

TAK
LGDPG

Jasiu przygotowuje ciasto na urodziny Małgosi. Jako że Małgosia jest całkiem wybrednym dzieckiem, to powstała lista życzeń odnośnie tego jak ma wyglądać ciasto:

1. Ciasto ma być kwadratowe i mieć wymiary 2^N na 2^N.

2. Na cieście ma się znajdować wisienka, która będzie się znajdowała w punkcie (X,Y).

3. Całe ciasto (poza miejscem z wisienką) ma być pokryte lukrem, w taki sposób, aby tworzył on obrazek składający się z kwadratów, z czego każdy z nich ma inny kolor, a ich boki są równe pewnej całkowitej potędze dwójki.

4. Żadnego miejsca ciasta nie można pokryć lukrem więcej niż jeden raz.

Lista ta jest wyjątkowo specyficzna, a w domu nie ma żadnego lukru, więc Jasiu postanowił nie marnować czasu i pójść do sklepu. Dla każdego i ∈ [0,N−1] kupił L_i opakowań lukru i–tego typu. Opakowanie lukru i–tego typu ma dokładnie tyle lukru ile potrzeba na pomalowanie wypełnionego kwadratu o wymiarach 2ⁱ na 2ⁱ. Każdy z kupionych przez niego lukrów ma inny kolor, więc każdego z nich można będzie użyć do narysowania tylko jednego kwadratu.

Jasiu podejrzewa, że mógł się pomylić i albo nie będzie w stanie spełnić specyfikacji Małgosi, albo kupił za dużo lukru co go mocno zirytuje, bo Jasiu nie lubi kupować rzeczy w nadmiarze. Niestety nie jest w stanie tego szybko ustalić, dlatego poprosił Cię o pomoc w stwierdzeniu czy może on wykorzystać cały lukier do spełnienia zachcianek Małgosi i jeżeli jest to możliwe, o znalezienie sposobu pokrycia ciasta całym lukrem.

Wejście

W pierwszym wierszu wejścia znajduje się trzy liczby całkowite N, X, Y będące odpowiednio liczbą określającą wymiary ciasta oraz współrzędnymi opisującymi położenie wisienki na torcie.
W drugim (i ostatnim) wierszu wejścia znajduję się N liczb całkowitych z czego i–ta z nich to L_i − 1, czyli liczba kupionych opakowań lukru i–tego typu.

Wyjście

W pierwszym wierszu wyjścia powinno się znaleźć słowo TAK, jeżeli jest możliwe wykorzystanie całego lukru do spełnienia zachcianek Małgosii lub NIE w przeciwnym wypadku.
Jeżeli zostało wypisane TAK, to w następnych N wierszach powinien znaleźć się opis pokrycia ciasta lukrem.
W i–tym wierszu opisu powinny się znajdować trzy liczby całkowite K_i, X_i, Y_i oznaczające odpowiednio, że opakowaniem lukru K_i–tego typu namalowano kwadrat o wymiarach 2^K_i na 2^K_i, którego lewy dolny róg jest w punkcie (X_i,Y_i). Liczba wystąpień K_i równych j w opisie powinna być równa L_j.

Ograniczenia

1 ≤ N ≤ 60, 1 ≤ X, Y ≤ 2^N, 0 ≤ L_i ≤ 100 000, ∑L_i ≤ 100 000.

Przykład

1 1 1
3

TAK
0 1 2
0 2 1
0 2 2

Ilustracja poniżej jest reprezentacją podanego rozwiązania powyższego testu przykładowego. Czerwona kropka oznacza wisienkę, a kolorowe kwadraty lukier. Zwróć uwagę, że w punkcie z wisienką nie ma lukru.

2 3 4
7 2

TAK
1 1 2
0 1 1
0 2 1
0 1 4
0 2 4
1 3 2
0 3 1
0 4 1
0 4 4

Jasiu otwiera swoją pierwszą restaurację. Przygotowuje w niej dokładnie dwie potrawy: pizzę (o cenie P bitolarów) oraz spaghetti (o cenie S bitolarów). Po przeprowadzonych analizach rynku Jasiu doszedł do dwóch fundamentalych wniosków:

1. Klient, wydając zbyt mało, odnosi wrażenie, że dania są niskiej jakości. Z drugiej strony, jeśli cena przekracza pewną wartość, klienci czują, że przepłacili. Idealnie jakby wydali na pizzę i spaghetti dokładnie N bitolarów (P + S = N).

2. Oprócz samej sumy rachunku, znaczenie mają także wizualne cechy poszczególnych cen. A dokładniej, poziom satysfakcji klienta z wizyty wynosi s(P) + s(S) (gdzie s(X) to suma cyfr liczby X).

Wyznaczenie cen przerosło Jasia, więc skierował się do Ciebie z pytaniem o ustalenie cen P oraz S zgodnymi z powyższymi wnioskami i podanie maksymalej wartości satysfakcji klienta.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się liczba naturalna N oznaczająca idealną sumaryczną cenę pizzy i spaghetti.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna znaleźć się jedna liczba całkowita, maksymalny możliwy poziom satysfakcji klienta.

Ograniczenia

1 ≤ N ≤ 10¹², 0 ≤ P, S ≤ N

Uwaga: Za darmo to też uczciwa cena, lecz ujemna już jest nie do zaakceptowania.

Przykład

35

17

10000000000

91

Dzisiejsze programy kulinarne często opierają się na gustach kilku jurorów, co może prowadzić do niesprawiedliwych ocen. Jednak nowy program “ChefMaster” zmienia zasady gry! W tej edycji aż miliard jurorów decyduje o przyszłości kucharzy, co daje większą szansę na sprawiedliwą ocenę.

Jasiu, nasz kucharz, bierze udział w programie i przygotował N dań. Jurorzy mają zróżnicowane gusta: dla każdego dania i, posmakuje ono tylko określonej grupie jurorów – od l_i do r_i włącznie. Jedynym warunkiem przejścia do kolejnego etapu jest, aby dla każdych dwóch kolejnych dań i oraz i + 1 istniał juror, który polubi oba dania.

Przed wydaniem Jasiu może jednak dokonywać pewnych zmian w daniach poprzez dwie dostępne operacje:

• Posolenie dania i – powoduje, że juror o indeksie l_i przestaje lubić to danie, ale zaczyna smakować ono jurorowi o indeksie (r_i+1) (jeśli r_i + 1 ≤ 10⁹)

• Posłodzenie dania i – powoduje, że juror o indeksie r_i przestaje lubić to danie, ale zaczyna smakować ono jurorowi o indeksie (l_i−1) (jeśli l_i − 1 ≥ 1)

Czasu jest niewiele, a przejście do kolejnego etapu nie jest pewne. Powiedz, ile minimalnie Jasiu musi wykonać operacji posolenia bądź posłodzenia, aby spełnił warunek awansu.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę dań przygotowanych przez Jasia. W następnych N wierszach znajdują się dwie liczby naturalne l_i oraz r_i oznaczające przedział jurorów, którym początkowo posmakowało danie i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna znaleźć się jedna liczba całkowita oznaczająca minimalną liczbę operacji, aby Jasiu spełnił warunek przejścia do kolejnego etapu.

Ograniczenia

1 ≤ N ≤ 10⁵, 1 ≤ l_i ≤ r_i ≤ 10⁹

Przykład

3
1 3
5 7
1 3

2

3
2 5
4 6
1 4

0

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

1999999680

5
123456 789012
123 456
12 345678901
123456 789012
1 23

246433

1
1 400

0