Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Zadania z VI edycji


FR_06_01 - Biegiem przez życie

 

W listopadowym Bajtockim biegu "Niepodległości" wzięła udział bardzo liczna grupa zawodników. Uczestników podzielono na cztery kategorie:

  • mężczyźni kategoria wiekowa 16 - 35 lat (M16),
  • kobiety, kategoria wiekowa 16 - 35 lat(K16),
  • mężczyźni, kategoria wiekowa 36+ (M36),
  • kobiety, kategoria wiekowa 36+ (K36).

Tym razem zostałeś dyrektorem tej prestiżowej imprezy. Do twoich obowiązków należy rejestrowanie wyników i tworzenie odpowiednich statystyk. Masz już gotowy serwis, który bardzo czytelnie przedstawia osiągnięcia sportowców. Do napisania został jeszcze tylko jeden moduł - program, który wylicza średnią wieku wszystkich kobiet, wszystkich mężczyzn oraz wszystkich uczestników. 

Wejście

W pierwszym wierszu cztery liczby rzeczywiste określające średnie wieków każdej z kategorii wiekowej w kolejności M16, K16, M36, K36, każda średnia mieści się w przedziale [16..100] i zapisana jest z dokładnością do dwóch miejsc po przecinku.

W drugim wierszu cztery liczby całkowite należące do przedziału [1..10 000] określające liczbę uczestników w każdej kategorii, odpowiednio M16, K16, M36, K36.

Wyjście

Trzy liczby rzeczywiste z dokładnością do dwóch miejsc po przecinku. Pierwsza to średnia wieku wszystkich kobiet, druga wszystkich mężczyzn, trzecia wszystkich uczestników biegu w formacie jak podano w przykładzie.

Przykład

Wejście:
20.00 30.00 40.00 50.00
10 10 10 10

Wyjście:
K16K36: 40.00
M16M36: 30.00
M16K16M36K36: 35.00

FR_06_02 - O Janku Wędrowniczku

 

O Janku Wędrowniczku

Mały Jasiu ledwo nauczył się czytać, a już zainteresował się opowiastką napisaną przez Marię Konopnicką - O Janku Wędrowniczku. Bohaterem opowiastek jest mały Janek, który postanawia wyruszyć w świat. Po drodze czekają go liczne przygody, dzięki którym chłopiec poznaje otaczającą go naturę, spotyka na swej drodze zwierzęta i poznaje ich zwyczaje. Książka wzbudza w dziecku ciekawość świata oraz rozwija więź z przyrodą. Jasiu do książki powraca nieustannie, a wszystkie opowiastki zna chyba już na pamięć. Jasiu, co już wiemy, ma także zamiłowanie do arytmetyki, nieustannie liczy i rachuje, rozwijając swoje zdolności matematyczne. Postanowił połączyć przyjemne z pożytecznym i zliczać zdania występujące w opowiadaniach. Jasiu jest bystry i szybko zauważył, że każde zdanie kończy się jednym z czterech znaków interpunkcyjnych, tj.: kropką, znakiem zapytania, wykrzyknikiem lub wielokropkiem. No to liczymy razem z Jasiem!


Wejście
Na wejściu znajduje się opowiadanie, na którre składa się tekst złożony z nie więcej niż 104 znaków. 

Wyjście
Na wyjściu należy podać liczbę zdań w opowiadaniu.

Przykład

Wejście
Mały Janek Wędrowniczek w wielką podróż wybrał się.
Świat chciał poznać dookoła, szedł przez łąki, wieś i pola.
Spotkał boćka, owiec stadko... Lecz nie wszystko szło tak gładko!
Także inne miał przygody, aż na koniec wpadł do wody.
Jak skończyła się wycieczka? To zawiera ta książeczka.

Wyjście
7

FR_06_03 - Skoki narciarskie

 

Polski Związek Narciarski postanowił­­­­­­­ zbudować nową skocznię. Jako miejsce nowego obiektu zarząd jednogłośnie wybrał KASPROwy Wierch. Postanowił, że skocznia ta będzie się różnić od innych skoczni tym, że będzie można na niej ustawić punkt konstrukcyjny w dowolnym miejscu. Po roku budowy i późniejszych staraniach o organizację zawodów PZN otrzymał zgodę na przeprowadzenie konkursu Pucharu Świata. Niestety kilka minut przed rozpoczęciem zawodów system zliczający punkty przestał działać. Żeby uratować konkurs, organizator zawodów poprosił Ciebie jako znanego programistę o napisanie programu, który będzie zliczał punkty zawodnikom i generował ranking zawodów.

Wejście

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

Specyfikacja każdego zestawu testowego:

W pierwszej linii znajdują się: dwie liczby rzeczywiste w,b (0< w,b ≤10) podane z dokładnością do 1 miejsca po przecinku, oznaczające odpowiednio ilość punktów dodanych/zabranych za każdy 1m/s prędkości wiatru i ilość punktów dodanych/zabranych za każdy 1 stopień belki, liczba całkowita k (60≤ k ≤250) oznaczająca odległość (w metrach), na której znajduje się punkt konstrukcyjny, liczba całkowita s (1≤ s ≤30) oznaczająca numer belki na początku konkursu oraz liczba całkowita n (1≤ n ≤100) oznaczająca ilość zawodników biorących udział w zawodach.

W kolejnych liniach znajdują się dane uczestników: imię i nazwisko oddzielone spacją, składające się wyłącznie z wielkich liter alfabetu łacińskiego których długość zawiera się w przedziale <3;20>, liczba rzeczywista d (0≤ d ≤k+50) podana z dokładnością do 1 miejsca po przecinku oznaczająca długość skoku (w metrach), liczba rzeczywista p (-10≤ p ≤10) podana z dokładnością do 1 miejsca po przecinku oznaczająca siłę (w m/s) oraz kierunek wiatru wiejącego podczas skoku, liczba całkowita a (1≤ a ≤30) oznaczająca numer belki, z której startuje zawodnik oraz liczb rzeczywistych podanych z dokładnością do 1 miejsca po przecinku z przedziału (0;20>  oznaczające noty od sędziów za styl.

Wyjście

Na wyjściu należy podać ranking konkursu posortowany nierosnąco względem ilości punktów zdobytych przez skoczków. W każdej linii znajduje się: imię_nazwisko_ilość zdobytych punktów (zaokrąglona do 1 miejsca po przecinku). Po danych każdego skoczka znajduje się znak nowej linii. W przypadku gdy taką samą ilość punktów ma więcej niż jeden zawodnik, należy wypisać tych skoczków alfabetycznie względem ich nazwisk. Zakłada się, że nazwisko każdego skoczka jest unikatowe.

- za skok na punkt konstrukcyjny zawodnik otrzymuje bazowe 60pkt. Za każdy metr powyżej/poniżej punktu konstrukcyjnego od bazowych 60pkt dodaje/odejmuje się:

  • 2,0 pkt gdy (60≤ k ≤100),
  • 1,8 pkt gdy (100< k ≤160),
  • 1,2 pkt gdy (k>160);

- długość skoku oraz noty sędziów za skok są w formacie x/2 gdzie jest liczbą całkowitą;

- do noty zawodnika dodawane są 3 oceny od sędziów. Najwyższa oraz najniższa ocena nie jest brana pod uwagę;

- gdy p>0, oznacza to, że wiatr wieje w plecy i punkty są dodawane, gdy p=0, oznacza to, że nie ma wiatru i nie dodajemy/odejmujemy żadnych punktów, gdy p<0, oznacza to, że wiatr wieje pod narty i punkty są odejmowane;

- gdy belka podczas skoku znajduje się wyżej niż początkowo punkty są odejmowane, gdy belka jest na tej samej wysokości jak początkowo, nie dodajemy/odejmujemy żadnych punktów, gdy belka jest niżej niż początkowo, punkty są dodawane;

Przykład

Input:
1 3.2 4.6 120 10 2
PIOTR ZYLA 130.5 -2.5 11 17.5 17.0 16.5 17.0 18.0
STEFAN HULA 120.5 1.5 9 18.0 18.0 18.0 19.0 17.0
Output:
STEFAN HULA 124.3
PIOTR ZYLA 117.8


FR_06_04 - Trójkolandia

 

Trójkolandia to kraina w południowej Bajtocji, w której od lat przyjęty jest system trójkowy jako system podstawowy. Trójkolandczycy mają swoje tradycje, ubierają się trójkolorowo, flagę mają złożoną z trzech barw, a nominałami waluty są: 1, 3, 9 i 27. Turyści zwiedzający ten piękny kraj mają często nie lada problem polegający na prawidłowym interpretowaniu liczb. W jednej z trójkolandzkich szkół jest dobrze płatny wakat dla nauczyciela matematyki. Oprócz przygotowania pedagogicznego w tym zakresie wymaga się poprawnego operowania na systemie trójkowym. Dodatkowym utrudnieniem jest to, że nie używa się cyfr arabskich, tylko cyfry oznaczone jako X, Y, Z i nie wiadomo do końca, która cyfra jest 0, 1 czy 2. Jeśli interesuje cię ten wakat lub po prostu lubisz programować rozwiąż następujący problem. Mając do dyspozycji podstawowe działanie arytmetyczne, określ (jeśli to możliwe), jakie cyfry arabskie kryją się pod znakami X, Y i Z.

Wejście

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

Każdy zestaw składa się z trzech wyrazów złożonych wyłącznie ze znaków XYZ, którym przyporządkowano pewne cyfry arabskie z systemu trójkowego. Pierwsze dwa wyrazy to składniki dodawania, trzeci natomiast jest ich sumą. Każdy wyraz składa się z maksymalnie 1000 znaków.

Wyjście

Dla każdego zestawu trzy znaki X, Y oraz odpowiadające cyfrom odpowiednio 0, 1 i 2 lub znak ? w miejsce cyfry, której jednoznacznie nie można określić.

Uwaga! Nie ma testów, w których wynik dodawania wychodzi sprzeczny.

Przykład

Wejście:
3
ZYY X ZYX 
XXXX YYYY XXXXZ
X X X


Wyjście:
Y??
ZXY
X??

FR_06_05 - Dystans

 

Dystans

Kiedy za oknem jest szaro i zimno, nic tak nie poprawia samopoczucia jak lekka przebieżka. Przyjemność tę musisz chwilowo odłożyć, bo aktualizacja oprogramowania w zegarkach biegowych, za którą byłeś odpowiedzialny, zawiera poważny błąd. Funkcja naliczania dystansu, na podstawie śladu GPS, nie działa poprawnie, a to powoduje, że pozostałe istotne funkcje aktywności biegowej także działają błędnie. Ślad GPS rysowany jest na podstawie zapisanych kolejnych punktów położenia współrzędnych geograficznych. Znając te punkty, wyznacz dystans śladu, który jest długością odcinka lub sumą długości wszystkich boków łamanej.


Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 1000) oznaczająca liczbę zestawów danych. W pierwszym wierszu każdego zestawu znajduje się liczba całkowita n (2 ≤ n ≤ 1000) oznaczająca liczbę punktów. W kolejnych n wierszach podane są po dwie całkowite współrzędne xy (-104 ≤ x,y ≤ 104) oznaczające koordynaty kolejnych punktów. Odcinkiem jednostkowym układu współrzędnych jest 1 metr. Wielkość rozmiaru plików wejściowych nie przekracza 5 MB. 

Wyjście
Dla każdego zestawu danych, wyznacz całkowity dystans śladu w km, z dokładnością do co najmniej dwóch cyfr po przecinku.

Przykład

Wejście
2
2
0 0
30 40
5
0 0
30 100
0 0
30 100
0 0

Wyjście
0.05
0.42

FR_06_06 - Bajtek i trójkąt

 

W Bajtocji szalała burza. Bajtek był bardzo znudzony, więc postanowił się pobawić. Narysował trójkąt, a następnie poprowadził z wierzchołka odcinek, który przeciął przeciwległy bok. Bajtek długo zastanawiał się, jaką długość ma powstały odcinek. Następnego dnia spytał Ciebie, czy znasz odpowiedź na nurtujące go pytanie. Jako że jesteś najbliższym kolegą Bajtka i specem od trójkątów, nie pozostaje Ci nic innego jak napisanie progamu, który oblicza długość szukanego odcinka.

Input

W pierwszym wierszu znajduje się ilość trójkątów narysowanych przez Bajtka; <1;5*105>;
W następnych wierszach znajdują się dwie liczby całkowite a,b <1;104> określające długość ramion trójkąta. Następnie dwie liczby całkowite c,d oznaczające długości odcinków na jakie została podzelona podstawa odpowiedno przy ramieniu b i a.
UWAGA: Dane są tak dobrane, żeby z danych odcinków mógł powstać trójkąt. 

Output

Na wyjściu znjaduje się długość szukanego odcinka zaokrąglona do dwóch miejsc po przecinku. Po każdej długości znajduje się znak nowej linii.

Example

Input:
1
5 5 4 4 
Output:
3.00

Rysunek do przykładu:





FR_06_07 - Format daty

 

Napisz program, który zamieni ciąg cyfr na format zaprezentowany w przykładzie. Data jest prawidłowo zakodowana, jeśli pierwsze dwie cyfry reprezentują dzień, drugie dwie miesiąc, natomiast kolejne cztery rok (rok jest poprawny jeśli należy do przedziału [1000..2200].

Wejście

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

Każdy zestaw składa się zakodowanej daty (poprawnie lub nie). W skład daty wchodzi maksymalnie 20 cyfr.

Wyjście

Odkodowujemy datę pisząc [dzień - w postaci liczby bez zer wiodących] [miesiąc - słownie bez polskich znaków, w dopełniaczu] [rok w postaci liczby]. Jeśli data jest niepoprawnie zakodowana wypisujemy "niepoprawny format daty".

Przykład

Wejście:
5
20101987
31022000
111111111
29022004
29022005

Wyjście:
20 pazdziernika 1987
niepoprawny format daty
niepoprawny format daty
29 lutego 2004
niepoprawny format daty

FR_06_08 - Miara kąta

 

Miara kąta

Wyznacz miarę (w stopniach) kąta wypukłego między wskazówkami minutową a godzinową zegara o zadanej godzinie.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 1000) oznaczająca liczbę przypadków testowych. W kolejnych d wierszach podane są przypadki. Każdy przypadek to godzina zapisana w formacie G:MM (0 ≤ G ≤ 23, 00 ≤ MM ≤ 59). 

Wyjście
Dla każdego przypadku testowego należy podać miarę kąta wypukłego (w stopniach, z dokładnością do jednej cyfry po przecinku), jaki tworzą wskazówki minutowa i godzinowa zegara o zadanej godzinie.
Dla godziny 0:00 i 12:00 rozwiązaniem jest kąt zerowy.

Przykład

Wejście
4
3:00
9:30
12:00
18:00

Wyjście
90.0
105.0
0.0
180.0

FR_06_09 - Coś poszło nie tak!

 

W Bajtockim Instytucie Badań (BIB) profesor Algobit opracowuje właśnie modyfikację genetyczną DNA, która rozwiąże problem z niekontrolowanym rozmnażaniem się króliczków. Profesor planuje wydłużyć czas, po którym zwierzątka będą osiągały dojrzałość. Do tej pory już po miesiącu były wstanie kopulować, a w następnym rodziła się kolejna para młodych. Jak mówi pewne prawo: „jak coś ma pójść źle, to pójdzie”, i tym razem tak się stało. Rzeczywiście udało się profesorowi wydłużyć ten czas, ale zamiast jednej pary zaczęły rodzić się dwie. Kolejne próby rokowały jeszcze gorzej, zamiast jednej pary, rodziło się k par.

Twoim zadaniem jest zbadanie powagi problemu i napisanie programu, który określi ile par króliczków będzie po s miesiącach, zakładając, że zwierzątka osiągają dojrzałość po n miesiącach i potem regularnie co miesiąc rodzą się kolejne pokolenia. W każdym urodzeniu dana para  króliczków ma k par młodych. Zakładamy, że króliczki nie umierają. Na początku jest jedna para, która właśnie się urodziła - jest to miesiąc o numerze 0.

Wejście

W pierwszym wierszu trzy liczby całkowite dodatnie q, n, k gdzie to liczba zapytań, dwie pozostałe liczby opisane są w zadaniu (<= 105<= n <= 10, 1 <= k <= 10).

Każde z zapytań składa się z jednej liczby s (0 <= <=106).

Wyjście

Dla każdego zapytania liczba par królików po s miesiącach modulo 1010101011.

Przykład

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

Wyjście:
1
1
1
3
5

FR_06_11 - Programowanie jest jak muzyka...

 

Jaś został muzykiem, ale jego zamiłowanie do kryptologii nie ustało. Postanowił więc połączyć te dwie dziedziny i zaszyfrować Ci pewne wiadomości, a Twoim zadaniem jest je (a jakże) odczytać. Jedyne informacje, jakie Pan Kryptolog zdradził bez użycia szyfrów są następujące:

 

  • szyfr składa się z pauz, ćwierćnut, ósemek, ósemek z kropką oraz szesnastek; od tradycyjnych nut o tych wartościach różni je niezamalowana główka;
  • ćwierćnuta ma wartość dwóch ósemek, ósemka - 2 szesnastek, a kropka przy nucie zwiększa jej wartość o połowę;
  • nuty zapisane są w kluczu wiolinowym;
  • główka najniższej nuty w zapisie Jasia znajduje się na ostatniej linii, zaś najwyższa - na najwyższej;
  • siedem pewnych liter można zaszyfrować na dwa sposoby;
  • odszyfrowany tekst składa się z dużych liter alfabetu angielskiego oraz spacji;
  • szyfr jest trywialny... dla Jasia.

 

Wejście

W pierwszej linii znajduje się niewielka ilość testów. Każdy test to pięciolinia zbudowana ze znaków: "-" oraz " ". Zapisane na niej nuty są zbudowane ze znaków: "o", "|", "\" i "." oraz znajdują się w odległości jednego znaku od siebie. Pięciolinie oddzielone są znakiem końca linii.

Wyjście

Na wyjściu powinny znaleźć się odszyfrowane wiadomości oddzielone znakiem nowej linii.

Przykład

Wejście:
3
                |\                       
                |                        
---------------o|---------|\-------------
                          |              
-------------------------o|--------------
  |\      |\ -      |\ -      |\      |\ 
--|\------|\--------|\--------|-------|\-
 o|      o|        o|        o|.  |\ o|  
------|\--------------------------|------
      |                          o|.     
-----o|----------------------------------

                                                 
          |\  |\              |\          |\     
----------|---|\--|\----------|-----------|\--|\-
         o|  o|   |          o|          o|   |  
--|\-------------o|-----|\-------------------o|--
  |\  |\             -  |  -      |\             
-o|---|----------------o|---------|--------------
     o|.                         o|.             
--------------------------------------|\---------
                                      |          
-------------------------------------o|----------

                                                                   |\                                       
                                                           |\      |                                        
------|\----------|\---------------------------------------|\-----o|.------------|\---------------|--|\-----
      |           |                                    |\ o|             |\      |                |  |      
--|\-o|.---------o|.--------------|----------|\--------|-----------------|------o|---------------o|-o|------
  |       |\          |\      |\  |  |\      |      - o|              - o|   |\     -                    |\ 
-o|.------|---|\------|\------|--o|--|\--|\-o|-------------------------------|\------------|\------------|\-
         o|.  |\     o|   |\ o|.    o|   |                                  o|         |\  |            o|  
-------------o|-----------|-------------o|-------|\------------|\----------------------|--o|.--|------------
                         o|                      |\            |                      o|       |            
------------------------------------------------o|------------o|.-----------------------------o|------------


Wyjście:
Podanie wyjściowych danych zepsułoby zabawę :)

FR_06_10 - Czas brutto, czas netto

 

Czas brutto, czas netto

Podczas imprez biegowych ranking generowany jest na podstawie czasu brutto, czyli czasu, jaki upłynął od wystrzału z pistoletu startowego do osiągnięcia mety przez zawodnika. Tak być musi w zawodach rangi mistrzowskiej, inaczej niejednokrotnie zwycięzcą biegu nie byłby ten, który linię mety minął jako pierwszy. Ale czy musi być tak na biegach amatorskich? Zawodnik, który stoi daleko od linii startu, musi przebiec dłuższy dystans oraz pierwsze (kilo)metry rywalizować w sporym ścisku. System, w którym ten, który ma lepszy czas rzeczywisty (netto - mierzony od chwili przekroczenia linii startu) często jest sklasyfikowany niżej niż ten, kto przed biegiem ustawił się bliżej startu, nie jest do końca sprawiedliwy. Dlatego czasami w biegach ulicznych, ranking generowany jest na podstawie czasów netto, choć czasami dopiero od pewnego ustalonego miejsca. Twoim zadaniem jest wygenerować klasyfikację z biegu uwzględniając czas netto, mając do dyspozycji ranking brutto oraz informacje o opóźnieniu zawodników w stosunku do przekroczenia linii startu. 

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita n (2 ≤ n ≤ 105) oznaczająca liczbę uczestników biegu. W kolejnych n wierszach znajdują się rekordy, w których podane są kolejno: nazwisko, imię, czas brutto w formacie GG:MM:SS oraz opóźnienie czasowe w formacie MM:SS. Nazwisko i imię to ciągi małych i dużych liter alfabetu łacińskiego, których sumaryczna długość nie przekracza 30 znaków. Należy założyć, że dane są poprawne, tzn. czas netto będący różnicą czasu brutto i opóźnienia jest zawsze dodatni. 

Wyjście
Na wyjściu należy wygenerować dokładnie n rekordów, składających się na klasyfikację biegu według czasów netto. Każdy rekord to kolejno: numer porządkowy uczestnika, nazwisko, imię, czas netto (GG:MM:SS), czas brutto (GG:MM:SS), rozdzielone pojedynczym znakiem spacji. W przypadku, gdy co najmniej dwóch zawodników ma jednakowy czas netto, o ich kolejności w rankingu decyduje porządek leksykograficzny nazwisko - imię. 

Przykład

Wejście
10
Bak Adam 00:37:00 00:02
Kakol Piotr 00:40:00 00:01
Kasprowicz Marcin 00:40:01 00:00
Bejnar Mieczyslaw 00:40:02 00:02
Sliwinski Mariusz 00:40:03 00:04
Dlugosz Witold 00:41:11 00:03
Nowaczynski Arkadiusz 00:43:17 00:01
Boniecki Maciej 00:43:18 00:02
Konczak Jaroslaw 00:43:57 00:02
Kraska Bartek 00:43:59 00:04

Wyjście
1 Bak Adam 00:36:58 00:37:00
2 Kakol Piotr 00:39:59 00:40:00
3 Sliwinski Mariusz 00:39:59 00:40:03
4 Bejnar Mieczyslaw 00:40:00 00:40:02
5 Kasprowicz Marcin 00:40:01 00:40:01
6 Dlugosz Witold 00:41:08 00:41:11
7 Boniecki Maciej 00:43:16 00:43:18
8 Nowaczynski Arkadiusz 00:43:16 00:43:17
9 Konczak Jaroslaw 00:43:55 00:43:57
10 Kraska Bartek 00:43:55 00:43:59

 

FR_06_12 - Jasio, Stasio i ich zakład

 

Jasio i Stasio są wielkimi fanami angielskiej Premier League. Cały tydzień czekali na niedzielę, kiedy to miały się odbyć 2 derbowe spotkania – Derby Manchesteru (Manchester United – Manchester City) oraz rozpoczynające się zaraz po nich Derby Merseyside (Everton – Liverpool FC). Obaj chcieli obejrzeć te mecze, lecz przypomniało im się, że nie odrobili jeszcze pracy domowej z informatyki. Na ich nieszczęście jest ona dość czasochłonna, przez co muszą sobie odpuścić obejrzenie meczu pomiędzy drużynami z Liverpoolu. Jej treść wygląda następująco:

Dla zadanej liczby a znajdź wszystkie permutacje składające się z cyfr tej liczby (jeśli jakaś cyfra powtórzyła się co najmniej raz to do tworzenia permutacji należy wykorzystać ją jednokrotnie), a następnie wypisz je malejąco względem ilości dzielników dla danej permutacji. Natomiast jeśli kilka permutacji ma tyle samo dzielników, wypisujemy je malejąco. Permutacje wypisujemy oczywiście bez zer wiodących.

Jasio i Stasio wpadli na ciekawy pomysł. Obstawili zwycięzcę pierwszego meczu i zadecydowali, że ten, który poprawnie obstawił będzie mógł spokojnie obejrzeć drugi mecz, natomiast przegrany będzie musiał zrobić zadanie domowe i przedstawić je koledze. Jasio, jako kibic Manchesteru United, obstawił wygraną „Czerwonych Diabłów”, natomiast Stasio postawił na zwycięstwo „Obywateli”. Zasiadli więc przed ekranami telewizorów i kibicowali swoim ulubieńcom. Po ponad półtora godzinnej walce zwycięsko z boiska zeszła drużyna z czerwonej części Manchesteru, która pokonała swoich sąsiadów 4:1. Bramki strzelali dla gospodarzy: Wayne Rooney, Zlatan Ibrahimović, Antonio Valencia oraz Juan Mata, zaś dla gości bramkę honorową zdobył Sergio Aguero. Stasio był bardzo zasmucony faktem, że przegrał zakład. Od razu po Derbach Manchesteru poszedł rozwiązywać zadanie domowe, zaś Jasio cieszył się oglądając drugie spotkanie derbowe.
Twoim zadaniem jest wcielić się w rolę Stasia i napisać program, który rozwiąże zadany problem. 

Wejście

W pierwszym wierszu znajduje się liczba całkowita n(0<n<11) oznaczająca ilość liczb. Następnie w każdej z następnych n linii znajduje się jedna liczba całkowita a(0<a≤109).

Wyjście

Dla każdej liczby należy wypisać wszystkie permutacje zgodne z treścią zadania w formacie liczba_ilość dzielników. Dodatkowo po wypisaniu wszystkich permutacji dla każdej liczby znajduje się pusty wiersz.

Przykład

Input:
2
336
24 Output: 36 9
63 6

42 8
24 8 

FR_06_13 - Upraszczanie ułamków

 

Upraszczanie ułamków

Nie wiem kto i kiedy wprowadził do podręczników nazewnictwo skracania ułamków. Skrócić to można spódnicę. Czyż nie ładniej brzmiałoby upraszczanie ułamków? Niestety sformułowanie przyjęło się i uczniowie chyba będą już tylko skracać ułamki, o ile potrafią :). No właśnie, nie każdy uczeń potrafi w pamięci znaleźć największy wspólny dzielnik dla licznika i mianownika pewnego ułamka. Stąd pani, przy omawianiu zagadnienia, podała prosty przepis na odnalezienie takiego dzielnika. Opiera się on na spostrzeżeniu, że jeśli od większej liczby odejmiemy mniejszą, to mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Postępujemy w ten sposób tak długo, aż różnica będzie równa 0. Ostatnia niezerowa reszta jest największym wspólnym dzielnikiem dwóch liczb - licznika i mianownika.
Sprawdźmy to na przykładzie ułamka 6/24:
24 - 6 = 18
18 - 6 = 12
12 - 6 = 6
6 - 6 = 0
Ostania niezerowa reszta to 6, więc ułamek 6/24 można uprościć przez 6, co daje nam 1/4. W przypadku tego ułamka wykonaliśmy cztery operacje arytmetyczne, które pozwoliły znaleźć wspólny dzielnik. Niestety algorytm ten, oparty na odejmowaniu ma jedną dużą wadę. Czasami liczba odejmowań, jakie trzeba wykonać, jest tak duża, że lepiej pozostawić ułamek w spokoju, nie wspominając o przypadkach, w których jedynym dzielnikiem jest 1 i ułamka nie da się uprościć.
A polecenie dla tego zadania jest takie: wyznacz liczbę operacji, jakie uczeń musi wykonać, aby znaleźć największy wspólny dzielnik metodą podaną wyżej.


Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 105) oznaczająca liczbę przypadków testowych. Każdy przypadek to ułamek zwykły zapisany w postaci a/b, gdzie (1 ≤ a,b ≤ 109). 

Wyjście
Dla każdego ułamka wyznacz liczbę odejmowań, która potrzebna jest do znalezienia największego wspólnego dzielnika licznika i mianownika.

Przykład

Wejście
3
4/6
6/24
1/5

Wyjście
3
4
5

 

FR_06_14 - Wiadukty

 

Od pewnego czasu trwa modernizacja dróg w południowej Bajtocji. Pan Andrzej Inżynierski zaproponował algorytm, według którego będzie budowana autostrada w tym kraju. Będzie ona ciągnęła się przez wszystkie miasta według algorytmu:

  • zaczynamy od miasta, którego współrzędne podano jako pierwsze
  • łączymy je z najbliższym, do którego jeszcze nie ma połączenia. Jeśli jest kilka takich, wybieramy to, którego współrzędna jest najmniejsza, jeśli i takich jest kilka, wybieramy to, którego współrzędna jest najmniejsza. 

Gwarantuje się, że miasta mają różne pozycje.

Jak pewnie zauważyłeś, niektóre autostrady mogą się przecinać. Aby uniknąć kolizjii w punkcie przecięcia się autostrady budujemy wiadukt.

Warunki postawienia wiaduktu:

  • wiadukt stawiamy tylko wtedy, gdy dwie drogi przecinają się pod kątem większym od 0 stopni (nie nakładają się na siebie równolegle w dowolnym odcinku),
  • wiaduktu nie stawiamy, gdy trafia on na współrzędne miasta,
  • jeśli więcej dróg przecina się w tym samym punkcie, dla każdej z nich stawiamy wiadukt,

Twoim zadaniem jest obliczenie długości autostrady oraz wyznaczenie liczby wiaduktów.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę miast (n < 5001).

W kolejnych n wierszach po dwie liczby całkowite x i będące współrzędnymi miast (|x| < 10001, |y| < 10001).

Wyjście

Dwa wiersze. W pierwszym wierszu długość sumaryczna autostrad zaokrąglona do dwóch miejsc po przecinku. W drugim liczba wiaduktów.

Przykład

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

Wyjście:
18.17
1

FR_06_15 - Lewa, prawa

 

Lewa, prawa

Miało nie być już o bieganiu, ale będzie. Jasiu długie wybiegania trenuje na ścieżkach leśnych w taki sposób, że startuje z pewnego ustalonego punktu i biegnąc zakreśla ślad będący wielokątem, kończąc w punkcie startu. Biegając w ten sposób jedna jego ręka będzie poruszać się wewnątrz wielokąta, druga zaś poza wielokątem. Powstaje pytanie, która ręka będzie zawierać się wewnątrz wielokąta? To trzeba rozstrzygnąć na podstawie danych współrzędnych geograficznych będących kolejnymi wierzchołkami wielokąta. Punkt startu jest punktem końca treningu.


Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. Pierwszy wiersz każdego zestawu zawiera liczbę całkowitą n (3 ≤ n ≤ 1000) oznaczająca liczbę wierzchołków wielokąta. W kolejnych n wierszach podane są po dwie całkowite współrzędne xy (-103 ≤ x,y ≤ 103) oznaczające koordynaty kolejnych wierzchołków. Żadne trzy kolejne punkty nie są współliniowe. 

Wyjście
Dla każdego zestawu danych wypisz słowo LEWA, jeśli to lewa ręka będzie zawierać się w wielokącie, albo słowo PRAWA, gdy podczas biegu prawa ręka będzie zawierać się we wnętrzu wielokąta.

Przykład

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

Wyjście
LEWA
PRAWA

 

FR_06_16 - Wskaźnik szczęśliwości II

 

Firma FRAKTAX z okazji 3-lecia istnienia firmy organizuje bankiet, na który chce zaprosić jak największą liczbę pracowników. Organizatorowi zależy bardzo, aby wszyscy zaproszeni czuli się komfortowo, aby wskaźnik szczęśliwości na tej imprezie był maksymalnie największy. Nie może zdarzyć się tak, aby na bankiecie znalazły się dwie osoby, które są ze sobą w relacji szef-podwładny. W firmie panuje następująca hieriarchia: pracownikiem numer 1 jest prezes firmy - Bajteusz Niewielki. Jego bezpośrednimi podwładnymi są wiceprezesi. Podwładnymi wiceprezesów są dyrektorzy, itd. W firmie FRAKTAX pracuje do 1000 osób. Napisz program, który określi ile tych osób maksymalnie można zaprosić na bankiet, jeśli nie mogą się na nim znaleźć jednocześnie szef i jego bezpośredni podwładni.

Wejście

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

Specyfikacja każdego zestawu:

w pierwszym wierszu liczba całkowita będąca liczbą pracowników w firmie (0 < < 1001).

Następnie n wierszy. I-ty wiersz określa i-tego pracownika w następujący sposób: najpierw jedna liczba definiująca liczbę bezpośrednich podwładnych, następnie numery tych podwładnych.

Wyjście

Dla każdego zestawu testowego maksymalna liczba osób, które mogą znaleźć się na bankiecie.

Przykład

Wejście:
1
19
2 2 3
3 4 5 6
3 7 8 9
0
1 10
0
0
2 11 12
0
3 13 14 15
4 16 17 18 19
0
0
0
0
0
0
0
0

Przykład:
14

FR_06_17 - Spirala Ulama

 

Spirala Ulama

Jasiu, znany badacz liczb pierwszych, dzisiaj przygląda się Spirali Ulama. Spirala zaproponowana przez polskiego matematyka Stanisława Ulama to kwadratowa tablica, w której wypisane są spiralnie, w kierunku rotacji przeciwnej do ruchu wskazówek zegara, kolejne liczby od 1 do n2, gdzie n jest pewną z góry ustaloną liczbą rozmiaru tablicy. Problem dotyczy głównie grupowania się liczb pierwszych na przekątnych spirali. Jasiu chce także sprawdzić, jak grupują się liczby pierwsze w wierszach spirali. W tym celu potrzebuje pomocy. Dla zadanej wartości n, należy wypisać ciąg n-wyrazowy, w którym i-ty wyraz odpowiada liczebności liczb pierwszych w i-tym wierszu spirali o rozmiarze n

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. Każdy przypadek to liczba całkowita n (2 ≤ n ≤ 1000) oznaczająca rozmiar tablicy. 

Wyjście
Dla każdego przypadku, w osobnym wierszu, należy wypisać ciąg n-wyrazowy, w którym i-ty wyraz odpowiada liczebności liczb pierwszych w i-tym wierszu spirali Ulama o rozmiarze n

Przykład

Wejście
2
5
6

Wyjście
2 2 3 1 1
1 2 3 3 1 1

Wyjaśnienie dla spirali o rozmiarze 5.

17 16 15 14 13
18  5  4  3 12
19  6  1  2 11
20  7  8  9 10
21 22 23 24 25

W pierwszym wierszu są dwie liczby pierwsze: 17, 13
W drugim wierszu są dwie liczby pierwsze: 5, 3
W trzecim wierszu są trzy liczby pierwsze: 19, 2, 11
W czwartym wierszu jest jedna liczba pierwsza: 7
W piątym wierszu jest jedna liczba pierwsza: 23

Stąd w kolejnych wierszach liczby pierwsze grupują się 2 2 3 1 1.

FR_06_18 - Trójkątna galaktyka

 

W odległej o miliony lat świetlnych galaktyce, wszystkie planety są trójkątami, których trajektorie orbit są okręgami opisanymi na tych trójkątach. Niekiedy dochodzi do kolizji tych objektów, w wyniku czego zostają zmienione ich trajektorie. Twoim zadaniem jest określenie, do ilu może dojść kolizji. Kalizją będziemy nazywać taką sytuację, w której para trójkątów w jakiś sposób będzie ze sobą się zderzać.

Wejście

W pierwszym wierszu jedna liczba calkowita definiująca liczbę planet(1 ≤ n ≤ 100). W kolejnych n wierszach współrzędne wierzchołków i-tego trójkąta w pewnym miejscu jej orbity. Jest to 6 liczb rzeczywistych x1 y1 x2 y2 x3 y3 spełniających warunek (-300 ≤ x1, y1, x2, y2, x3, y3 ≤ 300).

Wyjście

Liczba kolizji, jaka może nastąpić w podanej galaktyce.

Przykład

Wejście:
2
1 1 5.5 1 1 5.5
5 5 1 5 5 1
Wyjście:
1

FR_06_19 - Liczby wyborne

 

Liczby wyborne

Zadanie dotyczy podzielności. Zdefiniujmy pewne ciekawe liczby:

Liczbę n-cyfrową nazwiemy wyborną, jeśli dla każdego k∈{1,…,n} jej pierwszych k cyfr tworzy liczę podzielną przez k.

Np. liczba pięciocyfrowa 12320 jest liczbą wyborną, bo
1|1
2|12
3|123
4|1232
5|12320

Zadanie polega na znalezieniu najbliższej liczby wybornej dla pewnego zapytania. 


Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 104) oznaczająca liczbę przypadków testowych. Każdy przypadek testowy, to jedna liczba całkowita n (1 ≤ n ≤ 10100).

Wyjście
Na wyjściu, dla każdego przypadku testowego, należy wyznaczyć najbliższą liczbę wyborną. Jeśli dwie liczby wyborne, na osi liczbowej, są oddalone od liczby n w jednakowej odległości, należy wypisać mniejszą z nich.


Przykład

Wejście
4
25
123
2020
20000

Wyjście
24
123
2016
20120

 

FR_06_20 - Bajtoboty

 

Bajtek interesuje się robotyką. Ostatnio pracuje nad Bajtobotem - robotem, który potrafi rozpoznawać kolory. Nasz mały inżynier chciałby sprawdzić, jakie możliwości ma ów robot. W tym celu zbudował plac do testów złożony z kolorowych kwadratów. Interesuje go, gdzie na którym kwadracie powinien umieścić Bajtobota, by ten, poruszając się do przodu, tyłu, w lewo i prawo, przejechał przez kolejno wybrane kolory oraz na jakim kwadracie zakończy swoją wędrówkę. Współrzędne kwadratu to dwie liczby: pierwsza - numer kolumny i druga - numer wiersza. Kolumny i wiersze numerujemy od zera.

Wejście

W pierwszym wierszu jedna liczba całkowita n określająca rozmiar kwadratowej macierzy (2 < < 101). Nastepnie n wierszy po n liczb całkowitych nie wiekszych niz 109. W kolejnym wierszu dwie liczby: liczba aokreslajaca kolor startowy i liczba b okreslajaca ilosc nastepnych kolorow. Nastepnie b wierszy kolejnych kolorow, po których Bajtobot będzie się poruszał.

Wyjście

Współrzędne początku i końca wędrówki Bajtobota. Jeśli jest kilka odpowiedzi wypisujemy je posortowane rosnąco bez powtorzeń (sortujemy według początku (najpierw po x, potem po y), następnie po  końcu). 

Przykład

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

Wyjście:
1 2 1 0
2 2 3 1