Zadania - I Edycja

---

powrót

Zadania można rozwiązywać pod tym linkiem

Fibonacci w przedziale

Zadanie polega na wyznaczeniu ilosci różnych liczb Fibonacciego mieszczących się w przedziale [a..b].

Wejście

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

Każdy zestaw danych składa się z dwóch liczby całkowitych a i b takich, że 1 ≤ a ≤ b ≤ 109.

Wyjście

Dla każdeog zestawu jedna liczba określająca ilość różnych liczb Fibonacciego znajdujących się w przedziale [a..b].

Przykład

Wejście:
4
1 3
4 7
8 8
1000000 1000000000

Wyjście:
3
1
1
14

---

 

Dodawanie ułamków

Napisz program, kóry doda do siebie dwa ułamki

Wejście

Dwa ułamki w formacie licznik1/mianownik1 licznik2/mianownik2, gdzie licznik1, licznik2, mianownik1 oraz mianownik2 to liczby naturalne z przedziału[1..232-1]

Wyjście

Na wyjściu powinien pojawić się wynik w postaci:

licznik1/mianownik1 + licznik2/mianownik2 = licznik_wynikowy/mianownik_wynikowy

Ułamek wynikowy powinien być przedstawiony w postaci nieskracalnej.

Dane są tak dobrane, że do wszystkich obliczeń wystarczą typy 64 bitowe.

Przykład

Input:
1/2 3/4

Output:
1/2 + 3/4 = 5/4

---

 

Trzy odcinki

Na osi liczbowej rysujemy trzy odcinki, które mogą się pokrywać. Twoim zadaniem jest określenie, przedziału reprezentującego część wspólna tych odcinków.

Wejście

Trzy wiersze. W każdym wierszu reprezentacja odcinka w postaci przedziału obustronnie domkniętego [a, b], gdzie a ≤ b oraz |a| < 1000, |b|<1000.

Wyjście

Dwie liczbay określająca przedział będący częścią wspólną odcinków lub napis null, gdy takiej części nie ma.

Przykład 1

Wejście:
2 5
1 10
4 6

Wyjście:
4 5

Przykład 2

Wejście:
1 2
3 3
4 12

Wyjście:
null

---

 

Zapomniany klucz Cezara

Szyfr podstawieniowy to taki, w którym dane znaki podmienia się innymi według ściśle ustalonych zasad. Do takich szyfrów zalicza się "Szyfr Cezara". Każda z liter przesunięta jest w alfabecie o pewną liczbę zwaną kluczem. Niestety klucz, o którym mowa, został zagubiony, a twoim zadaniem jest odnalezienie go i odszyfrowanie tajnej wiadomości. 

Wejście

W pierwszym wierszu liczba t określająca liczbę zestawów danych. Każdy zestaw składa się z jednego zaszyfrowanego zdania wyrażonego dużymi literami łacińskimi i znakami spacji. Zdanie składa się z maksymalnie 10000 znaków.

Wyjście

Odszyfrowane zdanie

Przykład

Wejście:
2
CXLMXL ATDXKXF
TET FT DHMT

Uwaga! Wyjście celowo nie zostało podane aby nie ułatwiać odgadnięcie klucza.

---

 

Zamien na dziesietny

Przyszedł czas na systemy liczbowe. Zadanie polega na zamianie liczby zapisanej w systemie o podstawie p na system dziesiętny. Dodatkowo wynik przedstaw modulo 1010101.

Wejście

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

Każdy zestaw składa się z dwóch liczb: p i n, gdzie p to podstawa oraz n to liczba naturalna zapisana w systemie p (p ∈ [2..10], n ∈ [0..1010000] po konwersji na system dziesiętny).

Wyjście

Dla każdego zestawu jedna liczba zapisana wsystemie dziesiętnym modulo 1010101.

Przykład

Wejście:
3
2 1000111010101110100101011
3 120021
10 100000000000

Wyjście:
519793
412
1000

---

 

Ruchy tektoniczne

Profesor Algobit w wolnych chwilach (np. na wakacjach) zajmuje się geologią. Tym razem bada tereny podatne na ruchy tektoniczne. Interesuje go, jak często zmienia się różnica między najwyższym a najniższym punktem na pewnym obszarze. Dla uproszczenia, nie bada całego obszaru, tylko obszar w zdłuż pewnej prostej, na której oznaczył sobie czujniki oddalone od siebie o pewną jednostkę. Profesor czasami potrzebuje tylko wyniku dla pewnego ograniczonego przedziału. Niestety na wakacjach zepsuł mu się komputer i poprosił Ciebie o napisanie programu, który zautomatyzuje obliczenia profesora.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę czujników (numerację zacznamy od 1), gdzie n należy do przedziału [1..106].

W drugim wierszu n liczb całkowitych należących do przedziału [-107.. 107], określających wysokość danego czujnika nad poziomem morza.

Następnie jedna liczba q będąca liczbą zaptyań (q ≤ 107).

Każde zapytanie składa się z liczby o, która należy do zbioru: {0, 1}. Jeśli o ma wartość 0, to podane są jeszcze dwie liczby a i b, gdzie 1≤ a ≤ b ≤ n, to zapytanie o różnicę poziomów między początkiem w a i końcem w b, natomiast, jeśli o ma wartość 1, to podane są trzy liczby a, b oraz v, oznaczające, że w przedziale [a..b], czujniki zanotowały zmianę o v jednostek nad poziomem morza (1≤ a ≤ b ≤ n oraz v należy do przedziału [-107.. 107]).

Wyjście

Dla każdego o mającego wartość 0 należy wypisać maksymalną różnicę poziomów w przedziale [a..b].

Przykład

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

Wyjście:
7
2
7

---

 

Fraktal Cantora

Narysuj zbiór Cantora n-tego rzędu złożonego ze znaków "_" (podłoga). W n-tym wierszu fraktala długość linii jest równa jednemu znakowi "_".

Wejście

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

Każdy zestaw danych składa się z jednej liczby całkowitej z przedziału: [1..12], określające liczbę rzędów do narysowania dla fraktala Cantora.

Wyjście

Dla każdego zestawu danych narysowanie fraktala. Po każdym fraktalu wstawiamy jeden wiersz przerwy(po ostatnim także).

Przykład

Wejście:
3
1
3
2

Wyjście:
_

_________
___   ___
_ _   _ _

___
_ _

 

---

 

Permutacje cyfr

Zadanie polega na określeniu, czy cyfry jednej liczby mogą permutować w taki sposób, aby postała druga liczba.

Wejście

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

Każdy zestaw składa się z dwóch liczb naturalnych a i b, gdzie każda z nich jest nie większa niż 1020.

Wyjście

Dla każdego zestawu danych w osobnym wierszu napis Tak, jeśli pierwsza liczba jest permutacją drugiej lub Nie w przeciwnym razie.

Przykład

Wejście:
5
12 21
456 546
111111 11111
999 999
123 234

Wyjście:
Tak
Tak
Nie
Tak
Nie

---

 

Sortowanie babelkowe

Przyszedł czas na sortowanie bąbelkowe. Jest to najprostszy rodzaj sortowania porównującego ze sobą elementy sąsiadujące. Algorytm został opisany w tym miejscu. Twoim zadaniem jest określenie liczby zamian wartości elementów sąsiadujących (elementy zamieniamy tylko wtedy, gdy drugi element jest mniejszy od pierwszego).

Wejście

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

Każdy zestaw danych składa się z liczby n (1 ≤ n ≤ 106) określającej ilość liczb w ciągu do posortowania. Następnie n liczb całkowitych należących do przedziału [0..106].

Wyjście

Dla każdego zestawu jedna liczba określająca ilość zamian sąsiadujących liczb wykonanych przez algorytm sortowania bąbelkowego

Przykład 

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

Wyjście:
5
3
0

---

 

Czworokat na okregu

Jasiu dużo rozwiązuje zadań z palnimetrii, ponieważ ten dział sprawia mu sporo problemów. Dziś natchnął się na zadanie, w którym należy wpisać okrąg w czworokąt. Narysował więc najpierw czworokąt, a następnie próbował wpisać okrąg, okazało się jednak, że Jasiu nie mógł w żaden sposób dopasować okręgu do tego czworokąta. Po chwili przypomniał sobie, że nie każdy czworokąt można opisać na okręgu. Pomóż Jasiowi i określ, czy dany czworokąt można opisać na okręgu.

Wejście

Pierwszy wiersz określa liczbę zestawów danych (nie więcej niż 105)

Każdy zestaw danych zawiera cztery liczby całkowite z przedziału [1..232-1] oreślające boki czworokąta (nieoniecznie kolejne). Można założyć, że z podanych odcinków można utworzyć czworokąt.

Wyjście

Dla każdego zestawu słowo "Tak", jeśli dany czworokąt można opisać na okręgu, w przeciwnym razie słowo "Nie".

Przykład

Input:
2
2 2 3 3
2 2 3 4

Output:
Tak
Nie

---

 

Dodawanie czy odejmowanie

Mały Jasio bardzo lubi rozwiązywać zadania z matematyki. Dziś na lekcji uczniowie ćwiczą dodawanie i odejmowanie liczb całkowitych. Dla Jasia takie zadania nie stanowią żadnego problemu i gdy jeszcze wszyscy uczniowie zmagają się z zadaniami, nasz bohater już dawno je rozwiązał. Nauczyciel widząc, że jego uczeń jest bardzo bystry postanowił dać mu zadanie innego typu:

"Jasiu, masz tu cztery liczby naturalne: 2 3 1 4. Wstaw pomiędzy te liczby znak + lub - , tak aby otrzymać wynik 0."

I to zadanie nie sprawiło problemu. Uczeń przedstawił następujące rozwiązanie: 2 + 3 - 1 - 4 = 0. Nauczyciel zdumiony talentem Jasia zadał podobne zadanie, z tą różnicą, że liczb było znacznie więcej. Tym razem to zadanie okazało się większym problemem i po dłuższej chwili Jasio zaczął się zastanawiać, czy w ogóle można otrzymać wynik zadany przez nauczyciela.

Jako starszy brat/siostra, pomóż Jasiowi i napisz program, ktory stwierdzi, czy można tak dopasować znaki + i -, aby otrzymać zadany wynik.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość zadanych liczb przez nauczyciela (1 < n < 1001).

W drugim wierszu n liczb naturalnych nie większych niż 100.

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

Każde zapytanie składa się z jednej liczby całkowitej a, przedstawiającej szukany wynik (|a| < 105).

Wyjście

Dla każdego zapytania napis Tak, jeśli można otrzymać zadany wynik lub  Nie w przeciwnym razie.

Przykład

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

Output:
Tak
Nie
Tak
Tak
Nie

---

 

Notowania akcji

Jasio rozwiązując zadanie praktyczne z Excela natchnął się na wykresy słupkowe. Przedstawiały one informacje na temat notowań akcji firmy "FRAKTAX". Jasio miał określić maksymalny okres czasu, jaki akcje przyjmowały status jako niestabilne. Zachowanie akcji będziemy nazywać niestabilne, jeśli spójny podciąg składa się z conajmniej trzech wyrazów i środkowy wyraz jest większy (mniejszy) od swoich sąsiadów.

Wejście

Pierwsza liczba t określa liczbę danych testowych (0 < t < 101).

Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu jedna liczba n określająca długość ciągu liczb określających notowania akcji (nie większa niż milion). W drugim wierszu n liczb naturalnych dodatnich (nie większych niż 2000) określających notowania akcji fimy "FRAKTAX".   

Wyjście

Dla każdego zestawu danych jedna liczba określająca maksymalny okres czasu, w jakim akcje zachowywały się niestabilnie.

Przykład

Wejście:
2
5
1 3 2 5 6
2
1 2

Wyjście:
4
0

Wyjaśnienie:
W pierwszym przykładzie ciąg, który spełnia kryteria zadania składa się z liczb: 1 3 2 5, w drugim podciąg jest za krótki.

---

 

Metoda trapezów

Metoda trapezów została opisana w tym miejscu. Twoim zadaniem jest określenie liczby trapezów, na jakie należy podzielić pole ograniczone funkcją kwadratową, dwiema prostymi równoległymi do osi OY oraz prostą OX, które będzie równe P. Dane zostały tak dobrane, że istnieje tylko jedna taka liczba trapezów.

Wejście

W pierwszym wierszu trzy liczby całkowite a, b i c, gdzie |a|, |b|, |c| ≤ 1000 oraz a ≠ 0, będące współczynnikami funkcji kwadratowej.

Następnie liczba n określająca liczbę zestawów danych (n < 1000).

Każdy zestaw danych składa się z trzech liczb xa, xb oraz P, gdzie xa < xb to liczby całkowite określające początek i koniec badanego przedziału |xa|, |xb| ≤ 1000, natomiast P to liczba rzeczywista przedstawiona z dokładnością do 10-6, określająca pole, jakie zostało wyliczone używając k trapezów.

Dodatkowo wiadomo, że funkcja w badanym przedziale nie ma miejsc zerowych.

Wyjście

Dla każdego zestawu danych jedna liczba całkowita k określająca liczbę trapezów, na jaki został podzielony badany obszar, aby otrzymać pole P. Liczba knależy do przedziału [1..106].

Przykład

Wejście:
1 1 2
5
0 5 85.000000
0 5 69.375000
0 5 66.481481
0 5 64.168750
0 5 64.168709

Wyjście:
1
2
3
100
101

---

 

Szyfr przestawieniowy

 

Napisz program, który zaszyfruje lub odszyfruje ciąg małych liter, który został zaszyfrowany według schematu:

pierwsza spółgłoska zamieniona jest z ostatnią, druga z przedostatnią, itd. Jeśli liczba spółgłosek jest nieparzysta, spółgłoska stojąca po środku nie zmienia swojej pozycji.

Wejście

Jeden wyraz złożony z małych liter języka łacińskiego nie dłuższy niż milion znaków.

Wyjście

Zaszyfrowana (odszyfrowana) wiadomość

Przykład

Wejście:
lokomotywa

Wyjści:
wotomokyla

---

 

Gra w pierwsze

Bolek i Lolek bardzo lubią gry. Tym razem Bolek wymyślił grę w liczby pierwsze. Polega ona na tym, że obaj losują po jednej liczbie. Zasady są proste:

• jeśli obaj wylosują po liczbie pierwszej, wygrywa ten, który wylosował większą
• jeśli tylko jeden z nich wylosował liczbę pierwszą, to on wygrywa
• jeśli obie liczby nie są pierwsze, wygrywa ten, który wylosował mniejszą
• jeśli liczby są równe, wygrywa ten, który zaczynał

Zaczyna zawsze Bolek.

 

Wejście

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

Każdy zestaw składa się z dwóch liczb naturalnych dodatnich nie większych niż 4*109 - pierwsza liczba jest Bolka, druga Lolka.

Wyjście

Dla każdego zestawu danych imię gracza, który wygrał.

Przykład

Wejście:
3
7 9
8 8
13 17

Wyjście:
Bolek
Bolek
Lolek

---

 

Liczba k-cyfrowych liczb

Ile jest k-cyfrowych liczb naturalnych w systemie o podstawie n?

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 105) oznaczająca liczbę przypadków testowych. W kolejnych d wierszach podane są dwie liczby całkowite k, n (1 ≤ k ≤ 64, 2 ≤ n ≤ 16).
Dla danych wejściowych zachodzi dodatkowo warunek: nk ≤ 264.

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

Przykład

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

Wyjście
10
90
18
8

---

 

Podział odcinka

W prostokątnym układzie współrzędnych, odcinek o końcach w punktach A, B należy podzielić na jak najwięcej równych odcinków, których końce będą zawierać się w punktach kratowych.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (d ≤ 105) oznaczająca liczbę przypadków testowych. W kolejnych d wierszach, dla każdego przypadku testowego, podane są cztery liczby całkowite Ax, Ay, Bx By, każda z przedziału [-106; 106], wyznaczające współrzędne końców odcinka AB.

Wyjście
Dla każdego przypadku testowego w osobnym wierszu należy wypisać dwie liczby: największą możliwą liczbę odcinków i długość takiego odcinka zaokrągloną do co najmniej dwóch miejsc po przecinku.

 

Przykład

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

Wyjście
1 5.00
3 1.00
2 1.41
4 2.24

---

 

Dzielniki silni

Wyznacz liczbę dzielników naturalnych liczby n! 

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 10000) oznaczająca liczbę przypadków testowych. W kolejnych d wierszach podana jest jedna liczba całkowita n (1 ≤ n ≤ 10000).

Wyjście
Dla każdego przypadku testowego w osobnym wierszu należy wypisać liczbę dzielników modulo 1000000007. 


Przykład

Wejście
3
3
6
10

Wyjście
4
30
270

---

 

Tulipany

Jasiu i Stasiu hodują tulipany. Jasiu hoduje odmianę przepięknus czerwonus, a Stasiu pospolitus zółtus. W tym roku chcą wyhodować nową odmianę, która będzie połączeniem obu. Każdemu tulipanowi przypisali wartość kwiecistości i postanowili skrzyżować osobnika o czerwonych kwiatach z osobnikiem o żółtych kwiatach, których wartości kwiecistości będą zbliżone. Ta cecha spowoduje, że nowa odmiana będzie wyjątkowa. Gdyby okazało się jednak, że różnica jest zbyt duża, będą musieli wstrzymać się z nową odmianą. Twoim zadaniem jest policzyć najmniejszą różnicę kwiecistości między tulipanami Jasia a Stasia.

Wejście
W pierwszym wierszu wejścia znajduje się liczba kwiatów Jasia n (1 ≤ n ≤ 105). W drugim wierszu danych jest n wartości całkowitych ai (0 ≤ ai ≤ 109) oznaczających kwiecistości tulipanów czerwonych.
W trzecim wierszu wejścia znajduje się liczba kwiatów Stasia m (1 ≤ m ≤ 105). W czwartym wierszu danych jest m wartości całkowitych bi (0 ≤ bi ≤ 109) oznaczających kwiecistości tulipanów żółtych.

Wyjście
Na wyjściu należy wypisać jedną liczbę, najmniejszą różnicę między wartościami kwiecistości tulipanów Jasia i Stasia.

 

Przykład

Wejście
5
15 8 14 8 1
7
4 4 20 10 17 5 11

Wyjście
2

---

 

Trzyliterówka

Jasiu wymyślił nową łamigłówkę. Mając wyrazy trzyliterowe, należy wszystkie połączyć tak, aby pierwsza litera wyrazu następnego była ostatnią literą wyrazu poprzedzającego. Mając trzy wyrazy: tik tak kot, można je dopasować np. tak: tikotak, co prowadzi do rozwiązania łamigłówki.
Zaczął więc Jasiu tworzyć zestawy haseł, gdy pomyślał, że szybciej będzie generować je programem. Napisał więc program i zauważył, że losowe hasła często nie rozwiązują łamigłówki, a tak być nie może. Napisał nowy program, który wyłonić miał spośród wygenerowanych zestawów te poprawne. No tak, miał, bo program do dzisiaj nie zakończył działania. Pomóż Jasiowi i napisz program, który wskaże zestawy haseł prowadzące do rozwiązania trzyliterówki.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. Każdy zestaw danych opisany jest w dwóch wierszach. W pierwszym podana jest liczba całkowita n (1 ≤ n ≤ 100000) określająca liczbę haseł. W wierszu drugim podanych jest n trzyliterowych haseł złożonych z małych liter alfabetu łacińskiego.

Wyjście
Dla każdego zestawu danych należy wypisać albo słowo TAK, jeśli istnieje co najmniej jeden sposób prowadzący do rozwiązania łamigłówki, albo słowo NIE, jeśli nie jest to możliwe.

 

Przykład

Wejście
3
2
ten kot
3
tik tak kot
4
kto kot kat tok

Wyjście
TAK
TAK
NIE