Programowanie i algorytmy

Zadania IV edycja

powrót

Szyfrogram

Dziś profesor Algobit, na prośbę pięknej pani przedszkolanki, przeprowadzi prelekcję na temat algorytmów w najlepszym Bajtockim przedszkolu. Profesor będzie objaśniał takie znane algorytmy jak algorytm Euklidesa, przeszukiwanie binarne czy faktoryzacja liczb pierwszych. Później omówi podstawy matematyczne: Chińskie twierdzenie o resztach i arytmetykę modularną. Następnie, w harmonogramie swojego wystąpienia, wykładowca będzie opowiadał, w jaki sposób komputer przechowuje znaki. Przygotował także niespodziankę, która będzie polegała na tym, że naukowiec przedstawi ciąg cyfr reprezentujący szyfrogram, a przedszkolacy będą musieli bezbłędnie odgadnąć oryginalną wiadomość. Dla najszybszego ucznia, profesor Algobit przygotował nagrodę - indeks na swoją uczelnię.

Niech żaden przedszkolak cię nie zawstydzi i odszyfruj wiadomość najszybciej ze wszystkich. Wiadomo, że zaszyfrowane zostały tylko małe i duże litery języka łacińskiego, cyfry, znak kropki, przecinka, wykrzyknik oraz spacja.

Wejście

W pierwszym i jedynym wierszu n cyfr reprezentujących szyfrogram (n < 1000 001)

Wyjście

Oryginalna wiadomość.

Przykład

Wejście:
70826575846576443275797875858283326876653267736966736933
Uwaga!!! Oryginalna wiadomość celowo nie została podana. Po odszyfrowaniu pojawi się tekst z sensem.

Naprzeciw

W Bajtogrodzie nastąpiła zmiana rządu. Wszystkie dotychczasowe praktyki zostały zamienione na nowe, w tym także zasady posiedzeń rządu. Ministrowie w tej kadencji będą zasiadać równomiernie rozmieszczeni wokół okrągłego stołu. I tak każdy z ministrów przed posiedzeniem otrzymuje losowy numer porządkowy krzesła, na którym będzie zasiadał. Ministrów, po losowaniu, oprócz tego, kto będzie zasiadał w ich bezpośrednim sąsiedztwie, interesuje także, kto będzie siedział dokładnie naprzeciw nich, i czy nie będzie to czasem sam(a) premier. Wychodząc naprzeciw oczekiwaniom nowych ministrów, trzeba napisać program, który odpowie na zapytanie każdego zainteresowanego.

Wejście
W pierwszym wierszu wejścia znajduje się liczba zapytań q (q ≤ 105). Każde zapytanie opisane jest w osobnym wierszu, gdzie podane są dwie liczby całkowite nk (1 ≤ n ≤ 106, 1 ≤ k ≤ n) oznaczające kolejno liczbę osób biorących udział w posiedzeniu oraz przypisany numer porządkowy pytającego.

Wyjście
Dla każdego zapytania program powinien wypisać numer porządkowy osoby siedzącej dokładnie naprzeciw osoby (k) zadającej pytanie, albo napis BRAK, gdy dokładnie naprzeciw nikt nie zasiada.

Przykład

Wejście
4
2 1
3 2
4 2
4 3

Wyjście
2
BRAK
4
1


Największa suma cyfr

Z danego przedziału obustronnie domkniętego [a..b] wypisz liczbę, której suma cyfr jest największa. Jeśli jest kilka takich liczb, wypisz największą.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (< 200 001).

Każdy zestaw danych składa się z dwóch liczb naturalnych takich, że 0 ≤ a ≤ ≤ 1018.

Wyjście

Dla każdego zestawu testowego jedna liczba spełniająca kryteria zadania.

Przykład

Wejście:
2
20 100
28 46

Wyjście:
99
39

 

Suma algebraiczna

Pani od matematyki codziennie zadaje pracy domowej tak dużo, że jedna tablica to często za mało na jej zapisanie. A ponieważ w sali jest tylko jedna tablica, uczniowie muszą spieszyć się z przepisywaniem, bo jak tylko cała wolna powierzchnia zostanie zapisana, pani natychmiast wszystko zmazuje i zapisuje nowe przykłady. Jasiu, który wolno pisze, zawsze ma problemy z przepisaniem pracy domowej. Dzisiaj udało mu się przepisać wszystko, jednak kosztem czytelności nawiasów. Wszystkie nawiasy otwierające i zamykające w wyrażeniu algebraicznym wyglądają jak pionowe kreski i trudno je odróżnić. Teraz, kiedy musi w domu obliczyć wartość wyrażenia dla podanych zmiennych, musi odszyfrować wyrażenie tak, aby było one poprawnie zapisane. Jasiu wie, że każdy przykład to suma algebraiczna, której wyrazami są jednomiany stopnia pierwszego zmiennej xyz, o współczynnikach jednocyfrowych co do modułu. Przykładów jest tak dużo, że nie pozostaje nic innego, jak tylko napisać program, który zamieni pionowe kreski na odpowiednie nawiasy.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 1000). Każdy przypadek znajduje się w osobnym wierszu, na który składa się ciąg znaków opisujący sumę algebraiczną, w której nawias otwierający i zamykający zastąpiony został znakiem | pionowej kreski. Należy założyć, że wszystkie przykłady zapisane przez panią na tablicy są poprawne, a Jasiu nie pomylił się w przepisywaniu. Długość ciągu dla każdego przypadku jest nie większa niż 1000 znaków.

Wyjście
Na wyjściu należy wypisać wyrażenia algebraiczne odpowiadające przykładom, jakie kolejno podawała pani na tablicy, a które Jasiu zapisał w zmienionej formie w swoim zeszycie.

Przykład

Wejście
2
||x+|y+1||-|2x-y||+x
3-|x-|-y+5||-|2+z|

Wyjście
((x+(y+1))-(2x-y))+x
3-(x-(-y+5))-(2+z)


Księżyce Bajtka

 

Jak to zwykle bywa, na początku roku szkolnego, nauczyciele przygotowują dla swoich uczniów ciekawe zadania, aby zachęcić swoich podopiecznych do pracy na cały długi rok szkolny. Na lekcji matematyki mały Bajtek dostał pewien kolorowy obrazek. Jego zadaniem było wyliczenie sumy pól siwych księżyców.  Jako przyjaciel z ławki i ambitny programista pragniesz mu pomóc. Napisz program, który na podstawie danych R1 i R2 obliczy sumę pól wyróżnionych księżyców.

Uwaga! W C++ pamiętaj o usuwaniu notacji wykładniczej.

księżyce

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych Z (0 < ≤ 104). W każdym zestawie znajdują się dwie liczby rzeczywiste R1 i R2, określające długość promieni okręgów podane z dokładnością do dwóch miejsc po przecinku (0 < R1, R2 ≤ 215).

Wyjście

Dla każdego zestawu danych testowych należy wypisać dokładnie jedną liczbę rzeczywistą z precyzją do dwóch miejsc po przecinku, oznaczającą szukaną przez Bajtka sumę pól księżyców.

Przykład

Wejście:
2
4.00 6.00
3.26 14.68

Wyjście:
48.00 
95.71

 

Ranking

Tym razem trzeba napisać program, który na podstawie informacji podanych przed turniejem oraz wyników poszczególnych gier, wygeneruje ranking turnieju warcabowego. Na początku każdego turnieju podawane są informacje o uczestnikach turnieju. Są to kolejno: przypisany numer porządkowy, unikalna nazwa zawodnika, składająca się małych liter alfabetu łacińskiego i/lub cyfr o długości nieprzekraczającej 20 znaków oraz siła zawodnika - liczba z przedziału [0-2500]. Dla uproszczenia zakładamy, że wartość siły podczas turnieju nie ulega zmianie. Dalej następuje parowanie uczestników i to co najistotniejsze - gry bezpośrednie, które wymagają od zawodnika skupienia i dostarczają dużo emocji. Wynik każdego pojedynku bezpośredniego zapisywany jest za pomocą dwóch liczb całkowitych a i b oraz litery ze zbioru {W,R,P}. Liczby a i b oznaczają, że zawodnik z przypisanym numerem porządkowym a rozegrał partię z zawodnikiem z przypisanym numerem b. Litera zaś oznacza wynik gry. I tak litera W oznacza, że wygrał zawodnik z numerem porządkowym a. Litera R oznacza remis, a litera P informuje o przegranej zawodnika a i jednocześnie wygranej zawodnika b. W przypadku nieparzystej liczby uczestników, w każdej z rund, jeden z uczestników otrzymuje bonus. Wówczas wartość b równa 0 oznacza, że zawodnik z numerem a otrzymuje w tej rundzie bonus równoważny wygranej. Za wygraną w pojedynku bezpośrednim, zawodnik otrzymuje punkt rankingowy, w przypadku remisu zawodnicy otrzymują po 0.5 punktu każdy, przegrana - to brak punków. Po rozegraniu wszystkich partii wszystkich zaplanowanych rund, trzeba podliczyć punkty i wygenerować ranking. Uczestników turnieju należy sklasyfikować w rankingu według priorytetów:
1. Liczba punktów rankingowych.
2. Liczba wygranych gier bezpośrednich.
3. Siła zawodnika sprzed turnieju.
4. Porządek leksykograficzny nazwy zawodnika.
W przypadku, gdy dwóch lub więcej uczestników ma taką sam liczbę punktów, o jego pozycji w rankingu decyduje kolejno punkt 2, 3 i w ostateczności punkt 4.
Ostatnia informacja to taka, że ranking powinien zawierać trzy kolumny: numer porządkowy listy rankingowej, nazwa zawodnika oraz liczba jego punktów, zapisana z dokładnością do jednej cyfry po kropce dziesiętnej.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego, w pierwszym wierszu podane są dwie liczby całkowite n i r (2 ≤ n ≤ 1000, 1 ≤ r ≤ 11) oznaczające liczbę uczestników turnieju oraz liczbę rund. W kolejnych n wierszach podane są rekordy zawierające informacje o uczestnikach turnieju, przed jego rozpoczęciem. Numery porządkowe są różnowartościowe z przedziału [1,n]. W następnych ((n+1)>>1)*r wierszach podane są informacje o bezpośrednich pojedynkach między uczestnikami turnieju. Należy założyć, że dane są poprawne, tzn. zgodne z zasadami sztuki parowania. 

Wyjście
Dla każdego przypadku testowego należy wypisać n wierszy składających się na ranking określony według specyfikacji podanej wyżej. Pomiędzy wydrukowanymi rankingami dozwolony jest dodatkowy znak końca linii. 

Przykład

Wejście
1
11 8
1 xyzbartek 1203
2 xyzagata6 1257
5 copyright 1608
3 xyzkarolm4 1136
4 xyz4martyna 1068
11 xyzkalina 981
6 xyz3ziemekxd 987
7 xyzkornel6 1071
8 xyz6marcin 1345
9 xyz5julka 1196
10 xyz4dominik 949
1 7 W
2 10 P
3 5 P
4 0 W
6 9 P
8 11 W
1 5 P
2 11 P
3 7 W
4 10 W
6 0 W
8 9 R
1 9 R
2 3 R
4 5 P
6 8 P
7 0 W
10 11 W
1 10 P
2 0 W
3 11 W
4 9 W
5 8 W
6 7 P
1 6 W
2 7 W
3 9 W
4 8 P
5 10 W
11 0 W
1 4 P
2 5 P
3 8 W
6 11 P
7 10 W
9 0 W
1 0 W
2 6 W
3 4 P
5 9 W
7 11 R
8 10 W
1 8 P
2 4 W
3 6 W
5 7 W
9 11 W
10 0 W

Wyjście
1 copyright 8.0
2 xyz6marcin 5.5
3 xyzkarolm4 5.5
4 xyz4martyna 5.0
5 xyzagata6 4.5
6 xyz4dominik 4.0
7 xyz5julka 4.0
8 xyzbartek 3.5
9 xyzkornel6 3.5
10 xyzkalina 3.5
11 xyz3ziemekxd 1.0


 

Zlot programistów

DziałdowoJuż tej jesieni w pięknej miejscowości Działdowo w północno-wschodniej Bajtocji, odbędzie się zlot najwybitniejszych Bajtockich programistów. Będą oni prezentowali swoje programistyczne umiejętności rozwiązując skomplikowane problemy w niebywale optymalny sposób. Burmistrz tego miasta zlecił sprawy związane z organizacją wydarzenia właśnie Tobie. Okazało się, że chętnych chcących podziwiać umiejętności najlepszych jest tak dużo, że żadna miejscowa hala ich nie pomieści. Musisz więc zdecydować się na przygotowanie sceny na Działdowskim rynku. Dobrze się składa, że scena w tym miejscu znajduje się w punkcie o współrzędnych (0, 0). Wiesz na pewno, że miejsca siedzące musisz tak ustawić, żeby osoba podziwiająca ten spektakl nie miała przysłoniętego widoku przez żadną inną osobę siedzącą przed nią. System komputerowy, który stworzysz musi działać następująco. Osoba, która deklaruje się na to wydarzenie podaje współrzędne miejsca, na którym chce siedzieć, natomiast system wydaje komunikat TAK, jeśli nie jest ono przez nikogo zajęte oraz gwarantuje doskonałą widoczność sceny, oraz NIE w przeciwnym razie.  

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (t < 100 001).

Każdy zestaw składa sie z dwóch liczb całkowitych x i y definiujących współrzędne rezerwowanego miejsca. Współrzędne są podawane w porządku chronologicznym w jakim zostały rezerwowane miejsca (|x| < 109, |y| < 109).

Wyjście

Dla każdego zestawu TAK, jeśli można zarezerwować miejsce o podanych współrzędnych oraz NIE w przeciwnym razie.

Przykład

Wejście:
4
1 -1
0 2
7 100
1 -1
Wyjście:
TAK
NIE
TAK
NIE

 

Spirala liczbowa

Napisz program, który dla dwóch liczb całkowitych a i b narysuje, zawartą w macierzy a × b, spiralę zbudowaną z kolejnych liczb naturalnych od 1 do a · b, o początku w a11 i kierunku rotacji zgodnej z ruchem wskazówek zegara. Wszystkie liczby od 1 do a · b muszą wypełnić całkowicie macierz a × b oraz wszystkie wyrazy macierzy powinny mieć tę samą długość, równą liczbie cyfr największej liczby. W miarę potrzeb, liczby należy uzupełnić o zera wiodące. Między wyrazami macierzy występuje jeden znak spacji, po każdym wierszu następuje znak końca linii.

Przykład poniżej przedstawia spiralę o wymiarach 5 × 8

01 02 03 04 05 06 07 08
22 23 24 25 26 27 28 09
21 36 37 38 39 40 29 10
20 35 34 33 32 31 30 11
19 18 17 16 15 14 13 12

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 10). Każdy przypadek testowy to dwie liczby całkowite ab (1 ≤ ab ≤ 100) oznaczające wymiary spirali.

Wyjście
Dla każdego przypadku testowego należy wydrukować spiralę według specyfikacji podanej w treści zadania. 
Uwaga: każdy nadmiarowy biały znak lub jego brak na wyjściu spowoduje błędną odpowiedź. Ostatnim znakiem w wierszu musi być cyfra, po której dodajemy znak końca linii.

Przykład

Wejście
2
3 2
4 4

Wyjście
1 2
6 3
5 4
01 02 03 04
12 13 14 05
11 16 15 06
10 09 08 07


 

Silnia

Niech k oznacza iloczyn wszystkich liczb pierwszych od 2 do z . Zadanie polega na znalezieniu maksymalnego p, takiego ze równanie: 

n! mod kp ≡ 0

jest prawdziwe.

Wyjaśnienie

np. dla n=10 i z=5

10!=3628800

iloczyn wszystkich liczb pierwszych od 2 do 5 wynosi

2⋅3⋅5 = 30

10! = 302  4032

czyli

10! mod 302 ≡ 0

gdzie p=2.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (< 10001).

Specyfikacja każdego z t wierszy:

każdy wiersz składa się z dwóch liczb całkowitych z i n takich, że 1 < z ≤ 107, przy czym z jest zawsze liczbą pierwszą oraz 1 ≤ n ≤ 109.

Wyjście

Dla każdego zestawu testowego szukane p.

Przykład

Wejście:
1
10 5

Wyjście:
2

 

Dwa po(d)ciągi

Jasiu jest manewrowym na kolei. Do jego obowiązków należy między innymi sprzęganie i rozprzęganie taboru. Od jakiegoś czasu na stacji manewrowej pojawia się pociąg ze specjalnym składem, nie jest to jednak złoty pociąg...
Skład ten złożony z wagonów należy rozdzielić na dwa składy tak, aby spełniony był pewien warunek. Jasiu nie dopytuje dlaczego tak, po prostu wykonuje swoją robotę. Warunkiem tym jest jednakowa suma oznaczeń wagonów w obu rozdzielonych składach. Czasem nie jest to możliwe, wówczas Jasiu musi przestawiać lub doczepiać inne wagony, tego chce jednak uniknąć, bo to sporo dodatkowej pracy. Czasem jednak taki podział możliwy jest na więcej niż jeden sposób, wówczas maszynowy już sam decyduje, gdzie nastąpi rozdzielenie składu. Twoim zadaniem jest pomóc Jasiowi i udzielić odpowiedzi, na ile sposobów może rozdzielić skład na dwa składy, aby spełniony był warunek. Inaczej mówiąc, na ile sposobów można ciąg liczb całkowitych podzielić na dwa spójne podciągi tak, aby sumy wyrazów obu podciągów były takie same?

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego w pierwszym wierszu znajduje się liczba całkowita n (2 ≤ n ≤ 105) oznaczająca liczbę wagonów. W wierszu drugim znajduje się n liczb całkowitych ai (-106 ≤ ai ≤ 106) będących oznaczeniami kolejnych wagonów. Pliki wejścia nie przekraczają 2MB.

Wyjście
Dla każdego przypadku testowego należy odpowiedzieć na pytanie nurtujące Jasia.

Przykład

Wejście
2
3
1 2 3
4
-1 2 0 2

Wyjście
1
0


 

Liczby (nie) względnie pierwsze

Z danego multizbioru liczb znajdź taki podzbiór, który także może być multizbiorem, którego moc będzie największa oraz największy wspólny dzielnik wszystkich liczb tego podzbioru będzie większy niż 1.

Wejście

W pierwszym wierszu liczba przypadków testowych (nie więcej niż 1000).

Specyfikacja każdego przypadku testowego:

W pierwszym wierszu jedna liczba n (< 10 000) określająca długość ciągu.

W drugim wierszu elementy tego ciągu. Każdy element jest liczbą naturalną mieszczącą się w przedziale [1..106].

Wyjście

Dla każdego przypadku testowego największa moc podzbioru spełniającego kryteria zadania.

Przykład

Wejście:
3
1
3
4
2 3 4 6
5
5 10 15 20 5

Wyjście:
1
3
5

 

Mrówka Langtona

Mrówka Langtona to automat wymyślony i opisany przez Chrisa Langtona, stąd jej nazwa. Mrówka porusza się według pewnych zasad po siatce pól, zamieniając ich kolory na przeciwne. Początkowo nadajemy mrówce jeden z czterech kierunków i ustawiamy ją na pewnym polu siatki, dalej mrówka radzi sobie już sama. Jeśli pole, na którym się znajduje jest koloru białego, mrówka obraca się o 90 stopni w kierunku przeciwnym do ruchu wskazówek zegara, zamienia kolor pola na czarny i przechodzi na sąsiednie pole. Jeśli pole, na którym się znajduje jest koloru czarnego, mrówka obraca się o 90 stopni w kierunku zgodnym z ruchem wskazówek zegara, zamienia kolor pola na biały i przechodzi na sąsiednie pole. Poniżej symulacja kilku początkowych ruchów mrówki Langtona.

W tym zadaniu mrówkę osadzimy w diagramie 6 × 6, którego początkowo wszystkie pola są koloru białego. Swoją przygodę mrówka rozpoczyna w polu (3,3) obrócona w kierunku północnym. To jest jej pierwszy ruch, w którym obraca się na zachód, pole zabarwia na kolor czarny i idzie przed siebie. Mrówka porusza się według zasad podanych wyżej, z drobną różnicą. Ponieważ znajduje się w diagramie ograniczonym, za każdym razem, gdy próbuje wyjść poza jego granice, przechodzi cyklicznie na pole z drugiej strony diagramu. Na przykład z pola (2,6) chcąc iść na wschód przechodzi na pole (2,1), a z pola (1,3) idąc na północ, mrówka przechodzi na pole (6,3). I tak sobie mrówka przechadza po diagramie zmieniając stany pól z każdym kolejnym ruchem. Twoim zadaniem jest odtworzyć aktualny stan diagramu po n ruchach mrówki. Dla potrzeb zadania przyjmujemy, że każde pole koloru białego oznaczamy znakiem kropki (.), a pola koloru czarnego - znakiem x.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 105). Każdy przypadek to jedna liczba całkowita n (1 ≤ n ≤ 109) oznaczająca liczbę ruchów mrówki.

Wyjście
Dla każdego przypadku testowego należy wydrukować diagram 6 × 6 z aktualnym stanem pól po n ruchach mrówki Langtona. Między przypadkami testowymi dozwolony jest dodatkowy znak końca linii.

Przykład

Wejście
3
3
14
100

Wyjście

......
......
.xx...
.x....
......
......

......
..xx..
.xxxx.
.xxxx.
......
......

.xx.xx
xx..xx
xx.xx.
...x.x
..x..x
.x..x.

 

Drzewo genealogiczne

 

Ogłoszenie

Na potrzeby Bajtockiego Systemu Ewidencji (BSE), firma FRAKTAX zajmująca się tworzeniem programu, poszukuje dobrych programistów do współpracy. Jednym z kryteriów przyjęcia, jest zapoznanie się z problemem oraz dobra znajomość jakiegoś języka programowania. Inne wymagania to znajomość języka angielskiego, umiejętność pracy w zespole oraz poczucie humoru. Mile widziane doświadczenie w parzeniu kawy oraz w opowiadaniu dowcipów. A oto problem, jaki powinien rozwiązać kandydat.

Należy stworzyć drzewo genealogiczne pewnej rodziny zamieszkującej Bajtocję. Liczba potomków w danym pokoleniu dla kolejnych ojców (matek) jest definiowana według ciągu. Oznacza to, że pierwszy potomek ma a1 potomków, drugi aitd. Czynność tą powtarzamy cyklicznie. Tzn. jeśli są trzy wyrazy ciągu, to czwarty ojciec (matka) będzie miał (miała) a1 potomków itd. Dla każdego potomka podane są trzy informacje: numer pokolenia (liczymy od zera), numer potomka (liczymy od jeden) oraz jego imię (maksymalnie 10 znaków). Niestety nie wszystkich przodków można było odnaleźć, więc w to miejsce zamiast imienia wpisujemy znak zapytania. Może się zdarzyć także taka sytuacja, że dana informacja zostanie zaktualizowana, tzn., że imię dla danej osoby może zostać podmienione na inne. Napisz program, który rozwiąże problem i zacznij pracować w najlepiej płatnej firmie "FRAKTAX".

Wejście

W pierwszym wierszu liczba n określająca długość ciągu wyznaczającego liczbę potomków dla danego rodzica (< 1000).

W drugim wierszu n liczb naturalnych zawierających się w przedziale [1..3].

W kolejnym wierszu jedna liczba określająca liczbę osób, które będzie budowało drzewo genealogiczne (< 100 001). Następnie p wierszy w postaci trzech informacji pokoleniepotomekimię, gdzie 0 ≤ pokolenie ≤ 20, potomek to numer potomka w n-tym pokoleniu oraz imię to imię złożone z co najmniej 3 i maksymalnie 10 znaków.

Wyjście

Dla każdego wpisania danej osoby do drzewa genealogicznego należy wypisać wszystkich jego przodków odzielając ich "->" (patrz przykład). Jeśli po drodze jakieś imię nie zostało jeszcze wstawione to wypisujemy w tym miejscu znak "?".

Przykład

Wejście:
4
3 1 2 3
8
0 1 Bitek
1 3 Bajtek
2 6 Bibuszka
3 11 Bibitka
3 13 Bajtoslaw
3 1 Bibi
10 1236 Bitkos
0 1 Bibek

Wyjście:
Bitek
Bitek->Bajtek
Bitek->Bajtek->Bibuszka
Bitek->Bajtek->?->Bibitka
Bitek->Bajtek->Bibuszka->Bajtoslaw
Bitek->?->?->Bibi
Bitek->?->?->?->?->?->?->?->?->?->Bitkos
Bibek

 

Najbliższa pierwsza

Dla zadanej liczby naturalnej n znajdź najbliższą jej liczbę pierwszą.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 105). Dla każdego przypadku testowego w osobnym wierszu znajduje się jedna liczba naturalna n (1 ≤ n ≤ 107).

Wyjście
Dla każdej liczby naturalnej n należy wyznaczyć liczbę pierwszą, której odległość na osi liczbowej od liczby n będzie najmniejsza. Jeśli istnieją dwie liczby pierwsze o takiej samej odległości, należy wypisać mniejszą z nich.

Przykład

Wejście
4
30
101
1001
10001

Wyjście
29
101
997
10007


 

Binarne porównywanie

Dla zadanych dwóch liczb binarnych określi liczbę sposobów ustawień bitów w drugiej liczbie, tak aby była ona większa od pierwszej.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę zestawów danych (nie więcej niż tysiąc).

W kolejnych n wierszach po dwie liczby binarne złożone z tej samej liczby cyfr. Każda z nich składa się z maksymalnie 1000 bitów (można założyć, że najbardziej znaczący bit każdej z liczb ma wartość 1).

Wyjście

Dla każdego zestawu danych jedna liczba modulo 1010101011.

Przykład

Wejście:
3
1001 1100
100 101
110 110
Wyjście:
2
2
0

 

Soczystość

Jabłka przemieszczają się po taśmociągu jeden za drugim, a Jasiu musi wybrać spośród wszystkich jabłek te, których suma soczystości będzie możliwie największa. To jest jego zadanie. Ponieważ jabłka przemieszczają się bardzo szybko, Jasiu nie zdąży wybrać dwóch kolejnych jabłek, stąd musi sobie zaplanować przed rozpoczęciem pracy, które jabłka będzie wybierał. Znając z góry ciąg soczystości kolejnych jabłek na taśmociągu, napisz program, który wyznaczy największą sumę jaką można uzyskać z jabłek na taśmociągu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego w pierwszym wierszu podana jest liczba n (1 ≤ n ≤ 105) oznaczająca liczbę jabłek na taśmociągu. W wierszu drugim, danych jest n liczb całkowitych ai (1 ≤ ai ≤ 104) oznaczających soczystości kolejnych jabłek. 
Wyjście
Dla każdego przypadku testowego należy podać maksymalną sumę soczystości.

Przykład

Wejście
2
7
2 4 6 8 3 5 9
5
2 2 2 2 2

Wyjście
21
6


 

Proste i punkty

Dla danej prostej, określ liczbę punktów, przez które przechodzi.

Wejście

W pierwszym wierszu jedna liczb określająca liczbę punktów na płaszczyźnie (< 1000 001).

W kolejnych n wierszach po dwie współrzędne y każdego punktu, takie że |x| < 5001 oraz |y| < 5001.

Nastę™pnie jedna liczba p określająca liczbę™ prostych (< 100 001).

W kolejnych p wierszach po trzy współrzę™dne A, B, C prostych zapisanych w postaci ogólnej: Ax + By + C = 0. (|A|, |B|, |C| < 5001).

Uwaga!! W zadaniu dwa punkty o tych samych współrzędnych to dwa różne punkty.

Wyjście

Dla kaĹźdej prostej liczbę punktów, przez które ona przechodzi.

Przykład

Wejście:
3
1 1
-1 -1
2 4
2
1 -1 0
3 1 -2

Wyjście:
2
0

 

Wartość sumy algebraicznej

Skoro tu jesteś, to zapewne już pomogłeś Jasiowi z odtworzeniem pracy domowej w tym zadaniu. No ale praca domowa sama się nie zrobi, trzeba policzyć wartość wyrażenia dla pewnych zmiennych x, y, z. Są dwa sposoby, pierwszy to kartka papieru i długopis, drugi, jak już się pewnie domyślasz, to Twój ulubiony język programowania.

Wejście
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite d, x, y, z (1 ≤ d ≤ 1000, -1000 ≤ x, y, z ≤ 1000, ), gdzie d oznacza liczbę przykładów do rozwiązania, a liczby x, y, z to wartości zmiennych dla wszystkich przykładów. Każde wyrażenie znajduje się w osobnym wierszu, na które składa się ciąg znaków opisujący sumę algebraiczną, której wyrazami są jednomiany stopnia pierwszego zmiennej xyz, o współczynnikach jednocyfrowych co do modułu. Należy założyć, że wszystkie wyrażenia są poprawne, a długość wyrażenia nie przekracza 1000 znaków.

Wyjście
Na wyjściu należy wypisać wartość liczbową wyrażenia algebraicznego, dla zmiennych x, y, z.

Przykład

Wejście
3 1 2 3
x+y-z
x-(3x+y)
5x+(-y+(-2z+5))

Wyjście
0
-4
2


 

Chera Man

Chera Man jest komiksowym bohaterem, podobnie jak Spiderman, Superman czy X-men, który walczy ze złymi palindromami odpowiedzialnymi za wszelkie zło ówczesnego świata. Żeby je pokonać, Chera Man musi znać ich nazwy. Do tej pory było to proste, ponieważ nasz bohater musiał tylko sprawdzić, czy podany ciąg jest palindromem. Niestety od jakiegoś czasu złe palindromy zaczęły się skutecznie kamuflować, co znacznie utrudniało zadanie. Kamuflaż polegał na tym, że palindrom był ukryty jako spójny podciąg pewnego ciągu. Czasami okazywało się, że ciąg był tak długi, że Chera Man nie mógł sobie z tym problemem poradzić sam. Dodatkowo w zadanym ciągu mogło znajdować się ukrytych wiele palindromów. Naszego bohatera interesował palindrom alfa - taki palindrom, który jest najdłuższy, a jeśli jest kilka o takiej samej długości, to ten, który pojawił się najwcześniej. Przyczyń się do uratowania świata i napisz program, który znajdzie palindrom alfę.

Wejście

Pewna niewielka liczba ciągów złożonych z małych liter języka łacińskiego. Długość ciągu nie przekracza 106 znaków.

Wyjście

Dla każdego zestawu testowego wypisanie palindromu alfa.

Przykład

Wejście:
alamakota
bolekilolek

Wyjście:
ala
lol

 

Górska kraina

Jasiu planuje wycieczkę po malowniczych rejonach górskiej krainy, szlakami wytyczonymi przez górali. W krainie tej danych jest n miejscowości ponumerowanych liczbami naturalnymi od 1 do n, pomiędzy którymi istnieją szlaki. Z każdej miejscowości można dotrzeć pewną trasą do każdej innej miejscowości dokładnie na jeden sposób. Czas dotarcia szlakiem bezpośrednim z miejscowości a do miejscowości b równy jest |a-b|. Jasiu chce tak zaplanować swoją trasę, rozpoczynając z dowolnej miejscowości, aby trwała możliwie najdłużej, przy czym nie chce przechodzić dwa razy tym samym szlakiem. Wyznacz czas trwania wycieczki Jasia.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego w pierwszym wierszu podana jest liczba całkowita (1 ≤ n ≤ 104) oznaczająca liczbę miejscowości. W kolejnych n-1 wierszach podane są po dwie liczby całkowite a, b (1 ≤ a, b ≤ na ≠ b) oznaczające, że pomiędzy tymi miejscowościami istnieje bezpośredni szlak, którego czas przejścia równy jest |a-b|.

Wyjście
Dla każdego przypadku należy wypisać czas najdłużej trwającej wyprawy Jasia. Pliki wejścia nie przekraczają 5MB.

Przykład

Wejście
1
7
1 7
7 6
1 4
7 3
6 2
4 5

Wyjście
15


Wyjaśnienie: najdłużej trwająca wyprawa to trasa pomiędzy miejscowościami 2-6-7-1-4-5. Czas przejścia równy jest 15.