Programowanie i algorytmy

Zadania - II edycja

powrót

Wyznacz promień

Dla zadanych trzech niewspółliniowych punktów, określ jaka będzie długość promienia okręgu przechodzącego przez te punkty.

Wejście

W pierwszym i jedynym wierszu sześć liczb całkowitych xA, yA, xB, yB, xC, yC będących współrzędnymi punktów AB oraz C i należących do przedziału:[-1000; 1000].

Wyjście

Jedna liczba określająca długość promienia zaokrąglona do dwóch miejsc po przecinku.

Przykład

Wejście:
0 0 3 0 3 4

Wyjście:
2.50

Małe problemy Bajtka

Bajtek bardzo chce od następnego roku pójść do przedszkola z kierunkiem rozszerzonego nauczania programowania. Poza możliwością rozwijania swoich umiejętności w najważniejszej dziedzinie życia Bajtkiem kieruje również chęć poznania pięknej pani przedszkolanki. Jednak aby się tam dostać chłopiec musi rozwiązać zagadkę, z którą mierzył się każdy 3-latek:

Jeżeli:
104 = 1
106 = 2
112 = 0
136 = 1
148 = ?

Jako starszy brat Bajtka musisz napisać program, który rozwiąże jego problem i pomoże ci poznać piękną panią przedszkolankę.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość testów (0<n<101). Każdy test zawiera ciąg składający się z 6 liczb: k1, k2, ..., k(0 ≤ ki ≤ 999 oraz 1 ≤ i ≤ 6).

Wyjście

Dla każdego ciągu wybierz najmniejszą i największą liczbę, a następnie wypisz odpowiadającą jej według wzoru zagadki wartość.

Przykład

Wejście:
2
2 800 491 256 321 123
8 100 121 211 432 234
Wyjście:
0 4
2 0

Znak pierwiastka

Na ostatnim sprawdzianie z matematyki Jasio dostał ocenę bardzo dobrą i z tego powodu był bardzo niezadowolony. Okazało się, że w ostatnim zadaniu nie wyciągnął maksymalnej liczby przed znak pierwiastka, za co srogi nauczyciel odjął mu jeden punkt i nie postawił oceny celującej. Od tej chwili nasz młody bohater postanowił już nigdy nie popełnić tego błędu. Ty też nie popełnij takiego błędu na maturze i napisz program, który będzie wyciągał maksymalną liczbę całkowitą przed znak pierwiastka.

Wejście

W pierwszym wierszu liczba t określająca ilość zestawów danych (0 < t < 105). Każdy zestaw składa się z dwóch liczb całkowitych a i s, gdzie a to liczba znajdująca się pod pierwiastkiem oraz s to stopień pierwiastka (0 < a < 109) oraz (1< s < 11).

Wyjście

Dla każdego zestawu dwie liczby całkowite. Pierwsza z nich to liczba, która będzie stała przed znakiem pierwiastka, natomiast druga to liczba stojąca pod pierwiastkiem.

Przykład

Wejście:
4
4
4 2
8 2
7 3
24 3
Wyjście:
2 1
2 2
1 7
2 3

 


Małe szyfrowanko

Istnieje pewien szyfr, którego działanie jest oparte na tablicy, składającej się z 26 kolumn i 26 wierszy wypełnionych literami.
Pierwszy wiersz zaczyna się od A i kończy na Z (A,B,C,...,Z - alfabet angielski),
pierwsza kolumna składa się z tych samych liter w tej samej kolejności.
Czytając litery z tablicy w prawą stronę lub w dół, zawsze będziemy odczytywali alfabet angielski w kolejności (możliwe są przeskoki z litery Z na literę A).
Twoim zadaniem będzie zaszyfrować podaną wiadomość, skłądającą się z ciągu dużych liter alfabetu angielskiego tym szyfrem.
Na wejście zostanie podane słowo-klucz oraz ciąg liter do zaszyfrowania.
Szyfr działa w następujący sposób:
Załóżmy, że nasz ciąg liter wygląda następująco: TO ZADANIE NIE JEST TRUDNE, a słowo-klucz: SZYFR.
Ze słowa klucza musimy ułożyć ciąg liter o tej samej długości, co ciąg
który będziemy musieli zaszyfrować (Słowo-klucz może być dłuższe od wiadomości). Wygląda to w następujący sposób:

TO ZADANIE NIE JEST TRUDNE
SZ YFRSZYF RSZ YFRS ZYFRSZ

Dzięki takiemu układowi otrzymujemy współrzędne liter z tablicy, które podstawimy za litery z właściwej wiadomości. Współrzędne pierwszej litery to (T,S), drugiej (O,Z),trzeciej (Z,Y) itd...
Szyfrując wiadomość trzeba pamiętać o zachowaniu spacji pomiędzy słowami.

Wejście

W pierwszym wierszu podana zostanie liczba t (t<=1001), która określa ilość zestawów danych.
Jeden zestaw danych składa się z dwóch wierszy. W pierwszym słowo-klucz (jeden wyraz),
zaś w drugim wiadomość - ciąg wyrazów oddzielonych spacjami lub pojedynczy wyraz, który należy zaszyfrować według klucza.
Słowo-klucz jak i wiadomość zawierają maksymalnie 10001 znaków.


Wyjście

t wierszy, w każdym zaszyfrowana wiadomość.

Przykład:

Wejście

3
KOT
ALA MA KOTA
TOK
BOLEK I LOLEK
RAK
SZYFROWANIE


Wyjście

KZT WO DYHT
UCVXY S ECVXY
JZIWRYNAXZE

 


Żyjątka na pewnej planecie

Na pewnej planecie, której nazwy nie pamiętam, rozróżniamy dwa rodzaje żyjątek: Zera i Jedynki. Na początku było ich bardzo dużo. Tylko Jedynki są zdolne do rodzenia swoich potomków i mogą to robić nawet w sytuacji, gdy nie mają partnera czyli Zera do pary (jedynki mają tylko jednego potomka przez całe swoje życie), ale wtedy rodzi się tylko żyjątko płci Zero. Jeśli natomiast Jedynka ma partnera, to w takiej sytuacji rodzi się następna Jedynka. Twoim zadaniem jest określenie, ilu wszystkich przodków swojej płci ma Zero urodzone w n-tym pokoleniu. Przyjmujemy, że pierwsi przodkowie to pokolenie numer0.

Wejście

W pierwszym wierszu jedna niewielka liczba określająca ilość zestawów danych (nie więcej niż 100 000).

Każdy zestaw składa się z jednej liczby n, przedstawiającą numer pokolenia Zera (0 ≤ ≤ 100000).

Wyjście

Dla każdego zestawu liczba przodków żyjątka płci Zero urodzonego w n-tym pokoleniu, które są także Zerami. Wynik przedstaw modulo 1010101010101.

Przykład

Wejście:
2
3
5
Wyjście:
2
7

 


BMI

Wskaźnik masy ciała

Na lekcji biologii klasa Bajtka uczyła się o wskaźniku masy ciała, tzw. BMI, który klasyfikuje daną osobę w jednym z zakresów wartości: niedowadze, wartości prawidłowej oraz nadwadze. Pani od biologii podała klasie wzór:

BMI=masa[kg]/(wzrost)^2[m^2]

Natomiast zakres wygląda następująco: 

< 18,5 – niedowaga

[18,5; 25) – wartość prawidłowa

≥ 25,0 – nadwaga

Klasyfikacja ta nie może być stosowana u dzieci, więc Bajtek nie może wyliczyć wartości dla siebie. Postanowił więc, że napisze program, który określi w jakim zakresie znajduje się badana osoba, a Ty jako dobry kolega Bajkta, mu w tym pomożesz. Bajtek zebrał chętnych, którzy podali mu swoje dane.

 

Wejście

W pierwszym wierszu jedna liczba t (1 ≤ t ≤ 100) określająca ilość badanych osób. W kolejnych t wierszach - imię, masa i wzrost osoby podane odpowiednio w kilogramach i centymetrach (imię - maksymalnie 20 znaków, masa i wzrost to wartości naturalne dodatnie nie przekraczające 200).

Wyjście

Napis: "niedowaga", następnie w osobnych liniach wypisane imiona osób z tej grupy, podobnie z grupami: "wartosc prawidlowa" oraz "nadwaga". Dane osób wypisujemy w kolejności wczytania. Wstawienie znaku końca linii po każdej grupie jest opcjonalny.

Przykład

Wejście:
5
Ala 50 173
Beata 70 190
Boleslaw 100 180
Wincent 85 186
Hiacynta 62 164

Wyjście:
niedowaga
Ala

wartosc prawidlowa
Beata
Wincent
Hiacynta

nadwaga
Boleslaw

 


Profesor Algobit na zakupach

Dziś profesor Algobit będzie robił obiad. Poszedł więc do sklepu, zakupił produkty, między innymi także ziemniaki. Poprosił więc panią ekspedientkę o kilogram. Ona zapakowała mu w reklamówkę i zapytała czy 1,2 kg może być, na co profesor odpowiedział, że to jest za dużo. Pani odłożyła trzy ziemniaki i okazało się, że po zważeniu waga pokazała 980 g. Profesor stwierdził, że to jest za mało i chce dokładnie 1 kg. Pani Ania (tak miała na imię ekspedientka) nieco podirytowana stwierdziła, że nie da się dokładnie wyważyć 1 kg ziemniaków. Na to profesor popatrzył na ziemniaki i z uśmiechem na twarzy oznajmił, że da się to zrobić na dokładnie sześć sposobów.

Zakładamy, że dwa ziemniaki o tej samej wadze to dwa różne ziemniaki. Twoim zadaniem jest sprawdzenie, czy profesor ma rację.

Wejście

W pierwszym wierszu określająca liczbę ziemniaków, jakie bierzemy pod uwagę (liczba ta jest nie większa niż 1000).

W drugim wierszu n liczb całkowitych, określających wagi kolejnych ziemniaków (0 < n < 501).

Następnie jedna liczba q, określająca liczbę zapytań (< 10 000).

Każde zapytanie jest wagą o wartości k, jaką profesor chce uzyskać nakładając ziemniaki (0 < k < 2 000 001). 

Wyjście

Dla każdego zapytania liczba sposobów uzyskania żądanej przez profesora wagi modulo 10+ 9.

Przykład

Wejście:
5
100 100 200 100 200
3
200
400
300

Wyjście:
5
7
7

Wyjaśnienie
Dla rozróżnienia ziemniaków ponumerujmy kolejne wagi: 1001, 1002, 2001, 1003, 2002
Liczbę 200 możemy przedstawić jako: {1001+1002}, {1001+1003}, {1002+1003}, {2001}, {2002}.
Liczbę 400 możemy przedstawić jako: {1001+1002+2001}, {1001+1003+2001}, {1002+1003+2001}, {1001+1002+2002}, 
{1001+1003+2002}, {1002+1003+2002}, {2001+2002}

Walidacja adresu e-mail

Bitek dopiero poznaje tajniki tworzenia stron WWW, a jego wuj Bajtosław bardzo mu w tym pomaga. Dziś mają za zadanie stworzyć witrynę obsługującą sklep internetowy. Jak zwykle obaj webmasterzy dzielą się pracą. Bitek zajmuje się częścią programistyczną, zaś jego wuj częścią wizualną. Najtrudniejszą rzeczą będzie zaimplementowanie formularza kontaktowego, w którym nasz bohater musi stworzyć walidację adresu e-mail - nie wie jeszcze, że HTML 5 ma wbudowany mechanizm walidacji adresów mailowych. Czasu jest niewiele, a Bitek ma spore problemy, żeby to poprawnie zaprogramować - szczególnie dlatego, że musi używać języka PHP. Pomóż naszemu bohaterowi i napisz program w dowolnym języku sprawdzający poprawność adresu e-mail. Oto kryteria:

adres e-mail powinien

  • zawierać dokładnie jeden znak (@)
  • można używać małych lub dużych liter języka łacińskiego, cyfr oraz znaki:
    • kropka (.)
    • podłoga (_)
  • adres e-mail musi mieć format [pierwszy ciąg znaków]@[drugi ciąg znaków].[trzeci ciąg znaków składający się z 2 lub 3 liter] (pierwszy i drugi ciąg znaków musi się składać z znaków, gdzie n zawiera się w przedziale [1..20],
  • w mailu może być wiele znaków kropki i każda musi znajdować się między dwoma znakami różnymi niż znak (.) i (@)

Wejście

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

Każdy zestaw składa się z jednego wiersza, w którym mogą wystąpić znaki ASCII z przedziału [32..126]. Długość wiersza nie przekracza 100 znaków. Na początku i końcu każdego wiersza nie występują spacje.

Wyjście

Dla każdego zestawu testowego napis Tak, jeśli adres e-mail jest prawidłowy oraz Nie w przeciwnym razie.

Przykład

Wejście:
5
mat Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript.
 
Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript.
 
Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript.
 
Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript.
 
Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript.
 

Wyjście:
Nie
Tak
Tak
Tak
Nie

Kolejne wartości

Napisz program, który sprawdzi, czy dana wartość wystąpiła co najmniej trzy razy w posortowanym ciągu.

Wejście

W pierwszym wierszu jedna liczba określająca ilość liczb całkowitych (0 < n < 1 000 001).

Następnie n posortowanych niemalejąco liczb całkowitych, gdzie każda mieści się w przedziale [-230, 230].

W trzecim wierszu jedna liczba q określająca liczbę zapytań (0 < q < 300 001).

W ostatnim wierszu q liczb całkowitych należących do przedziału [-230, 230].

Wyjście

Dla każdego zapytania napis Tak, jeśli dana liczba powtórzyła się co najmniej trzy razy, napis Nie jeśli liczba powtórzyła się mniej niż trzy razy i przynajmniej raz lub napis brak, jeśli dana liczba nie występuje w ciągu.

Przykład

Wejście:
10
1 2 2 2 3 3 4 4 4 5
3
1 2 3

Wyjście:
Nie
Tak
Nie

Skalowanie

Zadanie polega na zeskalowaniu napisu.  Skalować będziemy tylko jego szerokość. Napis będzie niezmieniony, gdy poziom skalowania będzie równy 1. Gdy poziom będzie równy n, to między każdą literę wstawiamy |n| - 1 spacji. Gdy jest liczbą ujemną, napis powinien być wyświetlony od tyłu. Dla n = 0 wypisujemy tylko ostatnią literę. Na wyjściu nie mogą się pojawić zbędne spacje i znaki końca linii.

Wejście

W pierwszym wierszu napis złożony z wielkich liter języka łacińskiego (maksymalnie 100 znaków).

W drugim wierszu jedna liczba q określająca liczbę zeskalowań danego napisu (q < 100).

Następnie q wierszy, w każdym wierszu liczba n określająca poziom zeskalowania (|n| < 101)

Wyjście

Dla każdego zapytania w osobnym wierszu zeskalowany napis

Przykład

Wejście:
FRAKTAL
5
-2
-1
0
1
2

Wyjście:
L A T K A R F
LATKARF
L
FRAKTAL
F R A K T A L

U2

System U2 to system, w którym komputery przechowują liczby całkowite. Algorytm zamiany liczby dziesiętnej na U2 opisany jest w tym miejscu. Napisz program, który zamieni liczbę całkowitą na system U2 lub wypisze napis "niewykonalne", w sytuacji, gdy nie da się zapisać liczby na podanym polu.

<p>Napisz program, kt&oacute;ry zamieni liczbę całkowitą na system U2 lub wypisze napis "<strong>imbossible operation</strong>", w sytuacji, gdy nie da się zapisać liczby na pdoanym polu.</p>
<h3>Wejście</h3>
<p>W pierwszym wierszu jedna liczba <strong>t</strong> określająca ilość zestaw&oacute;w danych (<strong>0 &lt; t &lt; 10<sup>6</sup></strong>).&nbsp;</p>
<p>Każdy zestaw składa się z dw&oacute;ch liczb całkoiwtych <strong>n </strong>&nbsp;i <strong>p </strong>(<strong>|n| &le; 2<sup>60</sup>, 0 &lt; p &lt; 101</strong>) określające liczbę, kt&oacute;rą trzeba zapisać systemie U2 na polu <strong>p</strong>&nbsp;bit&oacute;w.</p>
<h3>Wyjście</h3>
<p>Dla każdego zestawu jedna liczba zapisana w systemie U2 lub napis "<strong>imbossible operation</strong>", w sytuacji, gdy liczba nie zmieści się na polu <strong>p </strong>bit&oacute;w.</p>
<h3>Przykład</h3>
<pre><strong>Wejście:</strong>
2
100 8
-100 8
<strong>Wyjście:</strong>
01100100
10011100
</pNapisz program, który zamieni liczbę całkowitą na system U2 lub wypisze napis "imbossible operation", w sytuacji, gdy nie da się zapisać liczby na pdoanym polu.

Wejście

W pierwszym wierszu jedna liczba t określająca ilość zestawów danych (0 < t < 106). 

Każdy zestaw składa się z dwóch liczb całkoiwtych  i (|n| ≤ 260, 0 < p < 101) określające liczbę, którą trzeba zapisać systemie U2 na polu p bitów.

Wyjście

Dla każdego zestawu jedna liczba zapisana w systemie U2 lub napis "niewykonalne", w sytuacji, gdy liczba nie zmieści się na polu bitów.

Przykład

Wejście:
2
100 8
-100 8

Wyjście:
01100100
10011100

 


Śnieg

Wesoła rodzinka Państwa Bajtockich wybrała się w góry. Właśnie wędrują sobie gęsiego po śniegu. Pierwszy idzie mały Bitek, następnie jego mama Bajbitka a na końcu ojciec Bajtjusz. 

Zadanie: napisz program, który określi, ile razy na odcinku metrów ślady wszystkich trzech osób pokryją się.

Zakładamy, że wszyscy ruszają z tego samego miejsca, pierwszy ślad jest tuż przed linią startu oraz wielkość śladu jest pomijalnie mała.

Wejście

W pierwszym i jedynym wierszu cztery liczby całkowite a, b, c oraz s, gdzie a, b i c to długości kroków, jakie stawiają osoby z rodzinki (w centymetrach), następnie liczba całkowita s, określająca długość trasy (w metrach), wszystkie te liczby zawierają się w przedziale: [1..1010]. (dane są tak dobrane, że do obliczeń wystarczą typy 64 bitowe)

Wyjście

Jedna liczba określająca ile razy pokryją się ślady wszystkich osób w rodzinie.

Przykład 1

Wejście:
30 40 50 2

Wyjście:
0

Przykład 2

Wejście:
30 30 60 3

Wyjście:
5

 


Liczby (nie)pierwsze

Liczby pierwsze to takie liczby naturalne, które są większe od 1 i mają dokładnie dwa dzielniki (dzielą się tylko przez jeden i przez samą siebie). Pojęcie to nie jest trudne i uczy się o o tym już w szkole podstawowej, jednakże największe umysły matematyczne nie uporały sobie ze znalezieniem ogólnego wzoru na nie. Takie sławy jak Pierre de Fermat, Martin Mersenne, Leonhard Euler czy Johann Carl Friedrich Gauss zmagali się z tymi wspaniałymi liczbami tworząc często błędne Hipotezy. Na szczęście twoje zadanie nie będzie aż tak skomplikowane. Dziś zajmiemy się liczbami naturalnymi, które nie są pierwsze. Napisz program, który określi, jaki jest maksymalny podzbiór kolejnych liczb naturalnych należących do przedziału obustronnie domkniętego, które nie są pierwsze.

 

Wejście

W pierwszym wierszu jedna liczba n określająca ilość zestawów danych (0 < ≤105). Każdy zestaw składa się z dwóch liczb ab reprezentujących przedział[a, b], gdzie 0 ≤ a ≤ b  4⋅106.

Wyjście

Dla każdego zestawu znajdź największy spójny podciąg kolejnych liczb naturalnych, które nie są pierwsze

Przykład

Wejście:
3
1 10
10 10000
20 22

Wyjście:
3
35
3

Współliniowość punktów II

Rozważmy zbiór punktów na płaszczyźnie kartezjańskiej, gdzie każdy punkt jest reprezentowany przez dwie liczby całkowite x i y oraz ich liczba nie przekracza 103. Napisz program, który stwierdzi, czy istnieje w danym zbiorze taka trójka punktów, które są współliniowe.

Wejście

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

Każdy zestaw składa się z jednej liczby n określającej liczbę punktów (2 < n < 1001). Każdy punkt zapisany jest w oddzienym wierszu za pomocą dwóch liczb całkowitych x i  y (|x| < 109|y| < 109). 

Wyjście

Dla każdego zestawu napis Tak, jeśli istnieje szukana trójka oraz napis Nie w przeciwnym razie.

Przykład

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

Wyjście:
Tak
Nie
Tak

 


Liczby podzielne przez 3

Jasio jest już w czwartej klasie. Dziś poznaje cechy podzielności liczb naturalnych. Jako pracę domową, uczeń miał określić, czy dana liczba jest podzielna przez trzy. Profesor zapisał kilka przykładów na tablicy, ale niestety jego pismo ma wiele do życzenia, nie jest ono zbyt czytelne. Niektórych cyfr podanych liczb Jasio nie był wstanie prawidłowo odczytać. Postanowił więc, że w te miejsca dopasuje tak cyfry, żeby dana liczba była podzielna przez 3. Dodatkowo chce wypisać wszystkie możliwe kombinacje takich liczb. Niestety okazało się, że dla niektórych z nich jest to zbyt duża liczba możliwości. Zrezygnował więc z wypisania wszystkich liczb, a pozostał przy określeniu liczby kombinacji. A co Ty byś zrobił w takiej sytuacji? Ty napisałbyś program, który rozwiąże problem za Ciebie :). 

Wejście

Wejście składa się z pewnej liczby zestawów danych (nie więcej niż milion). Każdy zestaw składa się z jednej liczby, której nieczytelne cyfry zastąpiono znakiem (?). Liczba posiada maksymalnie dziesięć cyfr lub znaków (?). Popatrz na wyjaśnienie.

Wyjście

Dla każdego zestawu danych, liczba kombinacji jakich można uzyskać zamieniając znaki (?) na cyfry, aby otrzymać liczby podzielne przez trzy.

Przykład

Wejście:
2?3
?33
11??

Wyjście:
3
3
33

Wyjaśnienie
Dla 2?3 uzyskujemy następujące liczby: 213, 243 oraz 273.
Dla liczby ?33: 333, 633 oraz 933 (uwaga 033 nie traktujemy jako liczbę).
Dla liczby 11?? mamy: 1101, 1104, ..., 1197.

Odpytywanie

Jasiu został uczniem pierwszej klasy szkoły podstawowej. Szkoła bardzo mu się podoba, bo jest dużo dzieci i sporo można się nauczyć. Z nauką jest jednak pewien problem, bo pani codziennie odpytuje z poprzednich zajęć, każdego dnia innego ucznia i nigdy nie wiadomo kto to będzie. Jasiu jest jednak bystry i już po tygodniu odgadł klucz, według którego odpytywani są uczniowie. Pani odpytuje według porządku wieku, starszy uczeń będzie pytany przed młodszym, a gdy co najmniej dwaj uczniowie urodzili się tego samego dnia miesiąca i roku, o porządku decyduje numer w dzienniku. Uczeń z przyporządkowanym niższym numerem będzie odpowiadał jako pierwszy. Teraz wystarczy zrobić listę porządkową kolejności odpytywań i każdy uczeń będzie wiedział, którego dnia będzie musiał odpowiadać na niekoniecznie łatwe pytania swojej pani.

 

Wejście
Pierwszy wiersz wejścia podaje liczbę przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego, w pierwszym wierszu podana jest liczba całkowita n (1 ≤ n ≤ 104) oznaczająca liczbę uczniów. W kolejnych n wierszach opisane są dane ucznia potrzebne do ustalenia porządku: unikalny numer w dzienniku i data urodzenia w formacie RRRR-MM-DD. Między przypadkami testowymi występuje dodatkowy znak końca linii.

Wyjście
Dla każdego przypadku testowego w osobnym wierszu należy wypisać listę porządkową numerów, według kolejności odpytywań.

Przykład

Wejście
1
5
3 2007-12-15
1 2008-03-30
5 2007-05-02
2 2007-05-02
4 2008-11-17

Wyjście
2 5 3 1 4

 


Najdłuższy podciąg różnowartościowy

Z podanego ciągu liczb wyznacz najdłuższy spójny podciąg o różnych wartościach.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Każdy przypadek opisany jest w dwóch wierszach. W pierwszym podana jest liczba całkowita n (1 ≤ n ≤ 106) oznaczająca długość ciągu. W wierszu drugim danych jest n wyrazów ai ciągu (1 ≤ ai ≤ 1000).

Wyjście
Dla każdego przypadku testowego należy podać w pierwszym wierszu długość takiego podciągu, w wierszu drugim szukany podciąg. Jeśli istnieje więcej niż jeden podciąg o najdłuższej długości, należy wypisać ten, który wystąpi w ciągu jako pierwszy.

Przykład

Wejście
2
10
7 1 9 5 3 1 2 10 3 9
5
4 2 5 4 4

Wyjście
6
9 5 3 1 2 10
3
4 2 5

 


Kapitan drużyny

Jasiu uczęszcza na dodatkowe zajęcia z gimnastyki, gdzie trener dzieli uczniów na drużyny. Za każdym razem uczniowie w pewnym porządku zajmują punkty na okręgu. Odbywa się to w taki sposób, ze uczeń nr 1 zajmuje dowolny punkt na okręgu, uczeń nr 2 z punktu, w którym stoi pierwszy uczeń odlicza dwa punkty w kierunku zgodnym z ruchem wskazówek zegara i zajmuje ten punkt. Z tego punktu, kolejny uczeń nr 3 odlicza trzy punkty i zajmuje ten punkt, itd.. Proces ten powtarzany jest tak długo, aż wszyscy uczniowie zostaną przyporządkowani pewnym punktom. Niektóre z tych punktów będą miały przyporządkowanych więcej niż jednego ucznia, a niektóre nie będą miały w ogóle przyporządkowanych uczniów. Uczniowie przyporządkowani do jednego punktu tworzą drużynę, a pierwszy uczeń, który zajmie ten punkt zostaje kapitanem. Niektórzy uczniowie zanim zaczną odliczać po okręgu, chcieliby wiedzieć wcześniej z kim będą w drużynie, i co najważniejsze, kto będzie kapitanem drużyny. Twoim zadaniem jest wyjść naprzeciw oczekiwaniom uczniów i znając ich numer porządkowy odpowiedzieć na pytanie, kto będzie kapitanem drużyny.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Każdy przypadek opisany jest w dwóch wierszach. W pierwszym wierszu znajdują się dwie liczby całkowite n i q (2 ≤ n, ≤ 1000, 1 ≤ q ≤ 1000), gdzie n oznacza liczbę punktów na okręgu, a q to liczba zapytań niektórych uczniów. W wierszu drugim danych jest q liczb ai (1 ≤ ai ≤ 105) oznaczających numery porządkowe uczniów, którzy chcą znać swojego kapitana, zanim zaczną swój marsz po okręgu.

Wyjście
Dla każdego zapytania ai należy podać numer porządkowy ucznia, który będzie kapitanem drużyny, do której należeć będzie uczeń z numerem ai. Na zapytania odpowiadamy w takiej kolejności, w jakiej zostały podane na wejściu. 

Przykład

Wejście
1
14 8
4 14 15 3 5 14 11 12

Wyjście
4 6 8 3 1 6 4 8


Taniec węża

Mały Jasio uczęszcza na zajęcia taneczne, gdzie wraz z innymi chłopcami i dziewczynkami ćwiczą różne układy taneczne. W tym tygodniu ćwiczą taniec węża, tzn. przytupują w rytm salsy trzymając się za ręce. Prowadząca zajęcia chciałaby sprawdzić swoich podopiecznych we wszystkich możliwych ustawieniach, ale nie wie jak to zrobić. Przyjmując, że chłopcy i dziewczynki są nierozróżnialni na poziomie płci, pomóż prowadzącej i wydrukuj dla niej wszystkie kombinacje ustawień chłopców i dziewczynek w rzędzie.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 100). Każdy przypadek opisany jest w osobnym wierszu, gdzie podane są dwie liczby całkowite ab (1 ≤ a+b ≤ 20) oznaczające odpowiednio liczbę chłopców i liczbę dziewcząt w grupie.

Wyjście
Dla każdego przypadku testowego należy wypisać w osobnych wierszach wszystkie kombinacje ustawień chłopców i dziewcząt w porządku leksykograficznym, przypisując chłopcom literę a, a dziewczętom literę b. Między przypadkami testowymi można wypisać dodatkowy znak końca linii, ale nie jest on wymagany.

 

Przykład

Wejście
3
1 1
2 1
5 0

Wyjście
ab
ba

aab
aba
baa

aaaaa


Podzielność przez 4

Dla ilu całkowitych wartości k (0 ≤ k ≤ n), liczba nk (n nad k) jest podzielna przez 4?

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

Wyjście
Dla każdego przypadku testowego należy wypisać jedną liczbę będącą odpowiedzią na pytanie postawione w zadaniu.

 

Przykład

Wejście
2
6
10

Wyjście 
1
3

 

Zadanie posiada 10 testów, każdy test za 10 punktów.
Test 1: (n < 64)
Test ≤ 5: (n < 105)
Test > 5: (105 ≤ n ≤ 109)
Zadanie zostanie zaakceptowane, jeśli uzyskasz co najmniej 50/100 punktów.