Contest problemset description

Dobra impreza nie może obejść się bez odpowiednich przekąsek! Jasio, jako gospodarz, postanowił zadbać o zaopatrzenie i kupić paluszki, chipsy oraz ciastka. W kieszeni kurtki znalazł banknot o nominale 100 złociszy i wyruszył na zakupy.

Jednak stanął przed trudnym wyborem, ponieważ w pobliżu jego domu znajdują się trzy sklepy: Bitronka, Bitl i Bajtland, a ceny tych produktów różnią się w zależności od sklepu. Dodatkowo, każdy ze sklepów posiada płatny parking, za który Jasio musi uiścić opłatę (c_i złociszy dla i-tego sklepu), jeśli zdecyduje się skorzystać z jego oferty.

Napisz program, który obliczy, ile maksymalnie reszty może zachować Jasio, kupując po jednej sztuce każdego rodzaju przekąsek i płacąc za parkingi przy wybranych sklepach.
Jeśli Jasiowi nie wystarczy pieniędzy na zakupy, program powinien wypisać pojedyncze słowo NIE. Cenę benzyny na przejazd pomiędzy sklepami należy zignorować, gdyż płacą za nią rodzice Jasia.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne pooddzielane pojedynczymi odstępami, oznaczające ceny parkingu przy kolejnych sklepach, czyli liczby c₁, c₂, c₃. W kolejnych 3 wierszach znajdują się po 3 liczby naturalne, w i-tym z nich – ceny kolejnych produktów w złociszach w i-tym sklepie (p_i, 1, p_i, 2, p_i, 3 ).

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się największa możliwa reszta, jaka zostanie Jasiowi po dokonanych zakupach lub pojedyncze słowo NIE, jeśli Jasiowi nie wystarczy pieniędzy.

Ograniczenia

1 ≤ c_i, p_i, j ≤ 100.

Przykład

1 99 99
20 20 20
1 1 1
1 1 1

39

15 10 5
15 35 35
35 15 35
35 35 15

25

óźnym wieczorem goście Jasia znaleźli w oczku wodnym gospodarza żabę. Ich widok wyrwał ją z letargu, a chcąc rozruszać stawy, zaczęła wykonywać skoki – zawsze dokładnie w lewo lub w prawo. Nie miała ochoty obracać się w innych kierunkach. W pierwszej minucie skoczyła o 1 centymetr, w drugiej o 2 centymetry, w trzeciej o 3 centymetry i tak dalej.

Zachowanie żaby wzbudziło duże zainteresowanie wśród zgromadzonych. Zaczęli się zastanawiać, ile najmniej czasu zajęłoby jej dotarcie do punktu oddalonego o K centymetrów w prawo od początkowej pozycji.

Uwaga! Żaba wykonuje skok w każdej minucie – nie może pozostać na miejscu.

Rozwiąż zagadkę kolegów Jasia! Napisz program, który wyznaczy minimalną liczbę minut potrzebną żabie na dotarcie do określonego miejsca.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna K, odległość w centymetrach od jej miejsca startowego.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna znaleźć się jedna liczba oznaczająca minimalną liczbę minut potrzebną żabie na dotarcie do wyznaczonego miejsca. Jeśli żaba nie może dotrzeć do celu, zamiast liczby wypisz pojedyncze słowo NIE.

Ograniczenia

1 ≤ K ≤ 10¹⁸.

Przykład

6

3

8

4

Przyjaciel Jasia, Tomek, po udanej imprezie obudził się w samo południe na środku polany. Niepewny wydarzeń minionej nocy, zaczął zastanawiać się, jak wrócić do domu. Jednak żar lejący się z nieba i obawa przed poparzeniami słonecznymi skutecznie zniechęcały go do drogi. Na szczęście na łące rośnie n drzew, a każde z nich rzuca choć odrobinę cienia.

Dla uproszczenia przyjmujemy, że i-te drzewo rzuca cień będącym kołem o promieniu r_i oraz środku w (x_i,y_i). Cienie drzew mogą na siebie nachodzić lub siebie wzajemnie zawierać.Zakładamy również, że pnie drzew są nieskończenie cienkie i nie utrudniają poruszania się Tomka, który w naszych rozważaniach jest reprezentowany jako punkt.

Tomek może poruszać się w dowolnym kierunku z prędkością 1 jednostki odległości na sekundę i w każdej chwili zmieniać kierunek ruchu. Tomek obudził się w punkcie (x_s,y_s), a jego dom znajduje się w punkcie (x_e,y_e).

Napisz program, który wyznaczy minimalny czas (w sekundach), jaki Tomek musi spędzić na słońcu, aby dotrzeć do domu.

Wejście

W pierwszym (jedynym) wierszu wejścia znajdują się cztery liczby pooddzielane pojedynczymi odstępami oznaczające kolejno x_s, y_s, x_e, y_e. Drugi wiersz wejścia zawiera pojedynczą liczbę n.
W następnych n wierszach wejścia znajdują się po 3 liczby całkowite, w i-tym z nich x_i, y_i, r_i oznaczające współrzędne środka oraz promień cienia i-tego drzewa.
Wszystkie liczby na wejściu są całkowite.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna znaleźć się jedna liczba rzeczywista, oznaczająca minimalny czas, jaki Tomek musi spędzić na słońcu, aby dotrzeć do domu.
Twoja odpowiedź zostanie zakceptowana, jeśli błąd względny lub bezwględny nie przekroczy 10⁻⁶.

Ograniczenia

•  − 10⁹ ≤ x_s, y_s, x_e, y_e ≤ 10⁹,
• Punkty (x_s,y_s) i (x_e,y_e) nie pokrywają się,
• 1 ≤ n ≤ 1000,
•  − 10⁹ ≤ x_i, y_i ≤ 10⁹,
• 1 ≤ r₁ ≤ 10⁹.

Przykład

7 0 -1 3
3 
0 3 1
4 0 1
6 0 1

3.0000000000

1 1 5 5
1
3 3 2

1.6568542495

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

0.0000000000

Przykład 1.

Przykład 2.

Przykład 3.

Jedną z atrakcji, jakie Jasio chce przygotować na przyjęcie, jest przepowiadanie przyszłości. Planuje sprawdzić, jak układają się fusy herbaty na dnie filiżanki każdego z gości, zbadać linie życia na ich dłoniach oraz określić ich znaki zodiaku. Choć Jasio dobrze przygotował się z wróżbiarstwa, wciąż ma problem z kalendarzem i odczytywaniem dat.

Pomóż zapracowanemu gospodarzowi i napisz dla niego program, który na podstawie dnia i miesiąca urodzin każdego z gości wypisze jego znak zodiaku, zgodnie z poniższym kalendarium astrologicznym. Każdemu ze znaków przypisany jest domknięty przedział dat:

  Baran: 21 marca - 19 kwietnia
  Byk: 20 kwietnia - 20 maja
  Bliźnięta: 21 maja - 20 czerwca
  Rak: 21 czerwca - 22 lipca
  Lew: 23 lipca - 22 sierpnia
  Panna: 23 sierpnia - 22 września
  Waga: 23 września - 22 października
  Skorpion: 23 października - 21 listopada
  Strzelec: 22 listopada - 21 grudnia
  Koziorożec: 22 grudnia - 19 stycznia
  Wodnik: 20 stycznia - 18 lutego
  Ryby: 19 lutego - 20 marca

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się dzień i miesiąc urodzin jednego z gości Jasia w formacie: dd.mm

Wyjście

Na wyjściu należy wypisać pojedyncze słowo będące nazwą znaku zodiaku odpowiadającego podanym na wejściu dniowi oraz miesiącowi, zgodnie z powyżej opisanym kalendarium astrologicznym.

Uwaga! Nazwę należy wypisać małymi literami alfabetu angielskiego, tak jak w przykładach.

Ograniczenia

Podany na wejściu dzień i miesiąc odpowiadają dowolnemu istniejącemu dniowi roku.

Przykład

16.06

bliznieta

01.01

koziorozec

01.02

wodnik

Do dekoracji domu Jasia przydałby się także ładny, ozdobny łańcuch. Jasio nie lubi chaosu i braku ładu, a taki łatwo otrzymać rozwieszająć łańcuch z oczkami w wielu kolorach, z których żaden się przebija. Dlatego Jasio chciałby, aby najczęściej występujący kolor oczek w jego łańcuchu, występował na ponad połowie oczek.
Gospodarzowi szkoda złociszy na stworzenie nowego łańcucha, dlatego chciałby wykorzystać stary, znaleziony w piwnicy. Pomóż Jasiowi, napisz dla niego program, który sprawdzi czy ze starego łańcucha da się wyciąć kawałek o pożądanej przez Jasia własności. Uwaga! Jedno oczko to żaden łańcuch, dlatego Jasia interesują fragmenty złożone z co najmniej dwóch oczek.

Wejście

W pierwszym wierszu wejścia znajduje się pojedyncza liczba naturalna n, oznaczająca liczbę oczek starego łańcucha znalezionego przez Jasia w piwnicy. W drugim wierszu wejścia znajduje się jedno słowo s składające się z n (s₁, s₂, s₃...s_n) małych znaków alfabetu angielskiego. Różne litery odpowiadają różnym kolorom oczek łańcucha.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać dwie liczby naturalne l < r, takie, że fragment starego łańcucha s_l, s_l + 1, ...s_r zawiera co najmniej t wystąpień pewnego koloru, gdzie $t > \lfloor \frac{r-l+1}{2} \rfloor$. Możesz wypisać indeksy odpowiadające dowolnemu z takich fragmentów. Jeśli taki fragment nie istnieje, zamiast tego należy wypisać pojedyncze słowo NIE.

Ograniczenia

1 ≤ n ≤ 200000.

Przykład

5
solve

NIE

6
ananas

1 5

8
accepted

2 4

Jedną z bardziej zaskakujących rzeczy na imprezie Jasia okazała się być jego dziwna czekolada. Każdy, kto kiedyś jadł czekoladę wie, że jej poszczególne kawałki zwykle smakują tak samo, albo chociaż bardzo podobnie. Z czekoladą Jasia było jednak inaczej. Jej prostokątny kształt został pocięty poziomo na paski o wysokościach A₁, A₂, ..., A_k oraz pionowo, na paski o szerokościach B₁, B₂, ...B_k, linie podziału przebiegają równolegle do brzegów czekolady. W ten sposób czekolada została pocięta na k² prostokątnych kostek. Im większy kawałek tym lepszy. Ponadto smak kawałka zależy w dziwny sposób od jego pozycji na oryginalnej tabliczce czekolady. Smakowitość kawałka powstałego na przecięciu pasków A_i oraz B_j wyraża bowiem się dziwnym wzorem: A_i ⋅ B_j ⋅ (i⊕j), gdzie ⊕ oznacza operację xor.

Pomóż Jasiowi oraz jego gościom ustalić, jaka jest sumaryczna smakowitość wszystkich kawałków powstałych po pocięciu czekolady.

Wejście

W pierwszym wierszu wejścia znajduje się pojedyncza liczba natrualna k oznaczająca liczbę pasków pionowych i poziomych w podziale czekolady. Drugi wiersz wejścia zawiera k liczb naturalnych, kolejno: A₁, A₂, ..., A_k poodzielanych pojedyczymi odtępami. Są to wysokości kolejnych poziomych pasków podziału czekolady. Analogicznie trzeci wiersz wejścia zawiera k liczb naturalnych B₁, B₂..., B_k, reprezentujących kolejne szerokości pionowych pasków podziału czekolady.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna znaleźć się suma smakowitości wszystkich kawałków powstałych przez pocięcie czekolady.

Ograniczenia

$1 \leq k \leq 100\thinspace000, 1\leq A_i, B_i \leq 1\thinspace000\thinspace000$.

Zagwarantowane jest, że sumaryczna smakowitość kawałków czekolady nie przekracza 10¹⁸.

Przykład

2
1 2 
3 4 

30

3 
1 3 2 
2 1 3 

46

Jasio, przygotowując się na przyjęcie gości, postanowił udekorować swój dom. Przeglądając internet, natrafił na fraktal o ciekawym wyglądzie – dywan Sierpińskiego. Wpadł na pomysł, aby wydrukować go na plakatach i przykleić do ścian. Niestety, jego stara drukarka obsługuje wyłącznie standardowe znaki ASCII.

Pomóż Jasiowi i napisz program, który wczyta stopień fraktalu i wydrukuje go przy użyciu jedynie znaków spacji oraz #.

Dywan stopnia 0 (D₀) to pojedynczy znak #.

Dywan stopnia k + 1 (D_k + 1) otrzymujemy, układając osiem kopii dywanu stopnia D_k w układzie 3×3, pozostawiając środkowy fragment pusty.

Graficzna ilustracja tego procesu:

Puste miejsca w trakcie konstrukcji kolejnych stopni fraktalu należy wypełnić spacjami (patrz przykłady).

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się pojedyczna liczba całkowita n, oznaczająca poziom fraktalu, jaki należy wypisać.

Wyjście

Na wyjściu powinien znaleźć się dywan sierpińskiego według powyżej opisanych reguł i konwencji.

Ograniczenia

0 ≤ n ≤ 7.

Przykład

0

#

1

###
# #
###

2

#########
# ## ## #
#########
###   ###
# #   # #
###   ###
#########
# ## ## #
#########