Contest problemset description

W gorący letni dzień Piotrek i jego dwaj przyjaciele, Bartek i Tomek, postanowili kupić arbuza. Wybrali największego i najbardziej dojrzałego. Po zważeniu okazało się, że arbuz waży w kilogramów. Chłopcy szybko pobiegli do domu, umierając z pragnienia, i postanowili podzielić arbuza. Jednak napotkali trudny problem.

Piotrek, Bartek i Tomek są wielkimi fanami liczb parzystych, dlatego chcą podzielić arbuza w taki sposób, aby każda z trzech części ważyła parzystą liczbę kilogramów. Nie jest konieczne, aby części były równe. Chłopcy są bardzo zmęczeni i chcą jak najszybciej rozpocząć posiłek, dlatego Twoim zadaniem jest pomóc im ustalić, czy można podzielić arbuza w taki sposób. Oczywiście każda z części powinna mieć dodatnią wagę.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba całkowita w, będąca wagą zakupionego arbuza.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinien się znaleźć napis TAK, jeśli chłopcy mogą podzielić arbuza zgodnie z wymaganiami. W przeciwnym razie należy wypisać NIE.

Ograniczenia

1 ≤ w ≤ 100.

Przykład

8

TAK

5

NIE

Łukasz znany jest ze swojej niezwykłej techniki czytania treści zadań. Na początku konkursu dzieli je na N kupek, na i-tej z nich znajduje się x_i treści, a przeczytanie każdej z nich zajmuje mu t_i sekund.

Niezwykłość techniki Łukasza polega na tym, że kolejno wybiera dwie nieprzeczytane jeszcze treści, z dwóch różnych kupek i oraz j, a następnie czyta je na raz, co zajmuje mu max (t_i,t_j) sekund, po czym wyrzuca je pod stół. Oczywiście Łukasz może także przeczytać tylko jedną treść z kupki i, co zajmuje mu t_i sekund.

Twoim zadaniem jest obliczenie ile minimalnie czasu potrzebuje Łukasz na przeczytanie wszystkich treści.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, będąca liczbą kupek. W i-tym z kolejnych N wierszy znajdują się dwie liczby całkowite x_i oraz t_i, będące odpowiednio liczbą treści znajdujących się na i-tej kupce oraz czasem potrzebnym na przeczytanie jednej z nich.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca minimalnym czasem potrzebnym Łukaszowi na przeczytanie wszystkich treści.

Ograniczenia

1 ≤ N ≤ 1 000, 1 ≤ x_i ≤ 10 000, 1 ≤ t_i ≤ 10⁹.

Przykład

3
3 8
2 2
2 5

26

3
1 20
5 9
3 3

56

3
2 8
2 6
2 7

23

Dwaj gracze grają w grę na prostokątnej planszy o wymiarach N × M. Plansza składa się z pól, które początkowo mogę być puste albo zajęte. Gracze na zmianę kładą kamienie na pustym polu, zajmując je. Każdy kolejny kamień musi być sąsiadem poprzedniego (muszą mieć wspólny bok), z wyjątkiem pierwszego, który można położyć w dowolnym pustym miejscu. Gra kończy się, gdy gracz nie może wykonać ruchu – wtedy przegrywa, a drugi gracz wygrywa.

Twoim zadaniem jest policzyć, ile pól jest wygrywających – czyli takich, że jeśli pierwszy gracz postawi tam pierwszy kamień, to wygra grę przy optymalnej grze obu stron.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i M, będące wymiarami planszy. W kolejnych N wierszach znajduje się opis planszy, w każdym z nich znajduje się ciąg M symboli – kropka (.) odpowiada polu pustemu, a kratka (#) polu zajętemu.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita będąca liczbą pól wygrywających.

Ograniczenia

1 ≤ N, M ≤ 50.

Przykład

3 4
.#..
.#.#
....

3

1 5
#...#

2

4 4
..##
..##
##..
##..

0

Dysponujesz bardzo prostym komputerem, który posiada tylko dwa rejestry (X oraz Y). Komputer jest bardzo prosty i udostępnia tylko cztery operacje:

• X+, która powoduje podstawienie do rejestru X sumy X + Y,
• X-, która powoduje podstawienie do rejestru X różnicy X − Y,
• Y+, która powoduje podstawienie do rejestru Y sumy Y + X,
• Y-, która powoduje podstawienie do rejestru Y różnicy Y − X.

Twoim zadaniem jest sprawdzić czy z początkowego ustawienia rejestrów, da się uzyskać ustawienie końcowe.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, będąca liczbą zestawów testowych. W każdym z kolejnych N wierszy znajdują się cztery liczby całkowite X_p, Y_p, X_k, Y_k, będące odpowiednio początkowym oraz końcowym ustawieniem rejestrów.

Wyjście

Na wyjściu należy wypisać N wierszy. W i-tym z nich powinna znaleźć się opowiedź dla i-tego zestawu testowego, będąca napisem TAK, jeśli z początkowego da się przejść do końcowego ustawienia rejestrów, lub NIE w przeciwnym wypadku.

Ograniczenia

1 ≤ N ≤ 100.

 − 10⁹ ≤ X_p, Y_p, X_k, Y_k ≤ 10⁹.

Przykład

2
1 4 5 9
4 2 -7 0

TAK
NIE

Ułamki postaci $\frac{1}{x}$ zawsze pełniły ważną rolę w historii ludzkości. W tym zadaniu przyjrzymy się bliżej problemowi przedstawienia ich w postaci sumy dwóch takich ułamków. Twoim zadaniem jest znalezienie liczby różnych par dodatnich liczba całkowitych (x,y) będących rozwiązaniem równania $\frac{1}{x} + \frac{1}{y} = \frac{1}{N}$, dla danego N.

Uwaga! Pary różniące się tylko kolejnością liczb uznajemy za różne.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba całkowita N.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć liczba rozwiązań równania podanego w zadaniu.

Ograniczenia

1 ≤ N ≤ 10⁷.

Przykład

3

3

7

3

Na stole znajdują się trzy karty. Na każdej z nich zapisano jedną z liczb 1, 2 albo 3, tak że każda z tych liczb znajduje się na dokładnie jednej karcie. W jednym ruchu można wybrać dwie sąsiednie karty i zamienić je miejscami. Ile najmniej ruchów trzeba wykonać, aby ułożyć karty w kolejności od najmniejszej do największej (od lewej do prawej)?

Wejście

W pierwszym (jedynym) wierszu wejścia znajdują się trzy liczby całkowite A, B, C, będące kolejnymi wartościami na kartach (w kolejności od lewej do prawej).

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć minimalna liczba ruchów potrzebnych do ułożenia kart w odpowiedniej kolejności.

Ograniczenia

1 ≤ A, B, C ≤ 3. A, B, C są parami różne.

Przykład

2 1 3

1

1 2 3

0

Turnieje programistyczne odbywaja się w dwóch wersjach – indywidualnej oraz drużynowej. Tym razem jednak z powodu specjalnej okazji planujemy przygotować nietypowy turniej par.

W tym turnieju uczestnicy na początku zostaną dobrani w pary, a następnie każde z przygotowanych zadań zostanie przydzielone dokładniej jednej parze, w taki sposób, że każda para otrzyma dokładnie jedno zadanie. Zwycięzcą zostanie para, która jako pierwsza rozwiąże przydzielone zadanie.

Oczywiście zadania są różnej trudności, a zawodnicy mają różne doświadczenie. Szacujemy, że jeśli zadanie ma trudność h, a zawodnicy mają doświadczenie odpowiednio d₁ i d₂ to rozwiązanie zadania zajmie im h ⋅ (d₁+d₂) minut (wyjątkowo im niższe ,,doświadczenie’’ tym lepszy jest zawodnik).

Zawodnicy mają różne, ale nie aż tak różne doświadczenie, to znaczy możemy ich podzielić na trzy grupy – mistrzów, zaawansowanych i początkujących. Zawodnicy z tych grup mają odpowiednio d_m, d_z i d_p doświadczenia.

Twoim zadaniem jest sprawdzenie jaki jest maksymalny czas trwania turnieju, to znaczy ile minut upłynie do momentu rozwiązania zadania przez najszybszą z drużyn, przy założeniu, że zawodnicy zostaną tak sparowani oraz zostanie im przydzielone takie zadanie, żeby ten czas zmaksymalizować.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite m, z i p, będące odpowiednio liczbą zawodników: mistrzów, zaawansowanych i początkujących. W drugim wierszu wejścia znajdują się trzy liczby całkowite d_m, d_z i d_p. W trzecim wierszu wejścia znajduje się $\frac{m + z + p}{2}$ liczb całkowitych będących trudnościami (wartościami h) kolejnych zadań.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita będąca maksymalną długością trwania turnieju.

Ograniczenia

0 ≤ m, z, p ≤ 100 000. 2 ≤ m + z + p ≤ 100 000. m + z + p jest liczbą parzystą.

1 ≤ d_m < d_z < d_p ≤ 1000. 1 ≤ h_i ≤ 100 000.

Przykład

0 2 2
3 5 8
4 5

52

2 3 3
1 2 3
1 1 1 10

5