Zadania z VIII edycji konkursu FRAKTAL

FR_08_01 - Parzysta parzystość

 

Napisz program, który stwierdzi, czy podana liczba naturalna jest parzysta, a jeśli nie jest, to czy można tak poprzestawiać cyfry, aby taka powstała.

Wejście

Jedna liczba całkowita należąca do przedziału [0..1015].

Wyjście

Napis Tak jeśli można otrzymać liczbę parzystą oraz Nie jeśli nie ma takiej możliwości.

Przykład

Wejście:
121

Wyjście:
Tak

FR_08_02 - Korekta

 

Jasiu, Stasiu, Wiesiu i Grzesiu lubią grać w Brydża. Za każdym razem dzielą się na dwa dwuosobowe zespoły, no i grają. Każdy z nich prowadzi ogólną ewidencję liczby gier wygranych i przegranych. Jasiu błędnie zsumował swoje wyniki i chciałby to skorygować. Znając liczbę gier wygranych i przegranych pozostałych graczy, należy wyznaczyć liczbę gier wygranych i przegranych Jasia. 

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 1000) oznaczająca liczbę przypadków testowych. W kolejnych wierszach danych jest po sześć liczb całkowitych nieujemnych nie większych od 106 oznaczających liczbę zwycięstw i porażek odpowiednio Stasia, Wiesia i Grzesia. 

Wyjście
Dla każdego przypadku testowego należy wypisać dwie wartości - liczbę zwycięstw i porażek Jasia.

 

Przykład

Wejście
2
8 7 3 12 10 5
0 10 0 10 10 0

Wyjście
9 6
10 0

 

FR_08_03 - Dopasuj hasło

 

Jednym z zabezpieczeń banku przed keyloggerami jest wprowadzanie niepełnego hasła. To znaczy, że po zalogowaniu podajemy tylko niektóre jego litery. Twoim zadaniem jest napisanie modułu dla pewnego banku, który będzie sprawdzał, czy klient poprawnie wpisał litery z hasła.

Wejście

W pierwszym wierszu jedna liczba określająca liczbę danych testowych.

Każdy test składa się z dwóch wierszy. Pierwszy to pełne hasło złożone tylko z małych i dużych liter oraz z cyfr (od 3 do 20 znaków), a drugi to hasło z zakrytymi niektórymi literami (od 1 do 40 znaków). 

Wyjście

Napis ok, jeśli hasła pasują oraz error, jeśli hasła nie pasują.

Przykład

Wejście:
2
fraktal
**ak**l
FRAKTAL
F*RAKTAL

Output:
ok
error

FR_08_04 - Wzrost i spadek wysokości

 

Jasiu wrócił z biegania, połączył zegarek z komputerem i już analizuje swoją aktywność. Niestety zegarek nie zapisuje wzrostu i spadku wysokości, w zamian Jasiu dostaje informacje o średnim nachyleniu i odległości każdego przebiegniętego odcinka. Jasiu na podstawie tych informacji, każdorazowo na kartce papieru, oblicza wzrost i spadek wysokości całej swojej biegowej aktywności. To żmudna i czasochłonna czynność, trzeba coś tu poradzić. 

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita n (1 ≤ n ≤ 100) oznaczająca liczbę przebiegniętych przez Jasia odcinków. Dalej w n wierszach znajdują się po dwie liczby całkowite a, d (-20 ≤ a ≤ 20, 10 ≤ d ≤ 1000), gdzie a oznacza kąt nachylenia odcinka mierzony w stopniach, a d to długość danego odcinka podana w metrach. Wartość a mniejsza od zera oznacza spadek wysokości na całym odcinku, a dla a większego od zera wyznaczamy wzrost wysokości danego odcinka. Wzrost/spadek wysokości całej trasy to suma wszystkich wzrostów/spadków poszczególnych odcinków. 

Wyjście
Na wyjściu należy wypisać dwie liczby (z dokładnością do dwóch cyfr po przecinku) oznaczające kolejno wzrost i spadek wysokości danej aktywności.

 

Przykład

Wejście
5
3 300
0 400
-3 500
0 400
3 200

Wyjście
26.17 26.17

 

FR_08_05 - Kolory w CSS

Jasiu jest początkującym webmasterem. Właśnie zapoznaje się z możliwościami kaskadowych arkuszy stylów CSS. Potrzebuje na "wczoraj" konwertera, który będzie zamieniał kolor zapisany w trybie RGB w systemie dziesiętnym na system szesnastkowy. Wiadomo, że niektóre kolory mają swoje nazwy, np. white, black, pink itd. Twoim zadaniem jest zamienić kolor zapisany w systemie dziesiętnym na system szesnastkowy (format jak w przykładowym wyjściu). Jeśli kolor nie ma nazwy, to zapisujemy go w formacie #RRGGBB, gdzie pierwsze dwie cyfry to nasycenie czerwonego, kolejne dwie zielonego i pozostałe niebieskiego, w przeciwnym razie stosujemy nazewnictwo kolorów podane w tabeli poniżej. 

black

#000000

 

silver

#C0C0C0

 

gray

#808080

 

white

#FFFFFF

 

maroon

#800000

 

red

#FF0000

 

purple

#800080

 

fuchsia

#FF00FF

 

green

#008000

 

lime

#00FF00

 

olive

#808000

 

yellow

#FFFF00

 

navy

#000080

 

blue

#0000FF

 

teal

#008080

 

aqua

#00FFFF

 

Wejście

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

W kolejnych n wierszach po trzy liczby reprezentujące nasycenie koloru czerwonego, zielonego oraz niebieskiego. Każda z nich należy do przedziału [0.255]

Wyjście

Dla każdego zestawu danych należy wypisać kolor w systemie szesnastkowym tak jak podano na wyjściu w przykładzie. Do zapisania literowych cyfr używamy dużych znaków.

Przykład

Wejście: 6 0 0 0 255 255 255 0 255 255 1 2 3 100 200 50 255 0 0 Wyjście: black white aqua #010203 #64C832 red

 

FR_08_06 - Moc zbioru

 

Dla danej liczby naturalnej n wyznacz moc zbioru ułamków a/b spełniających warunek 1 ≤ a < b ≤ n i nwd(a,b) = 1. 

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 1000) oznaczająca liczbę przypadków testowych. Każdy przypadek to jedna liczba naturalna n (1 ≤ n ≤ 106) podana w osobnym wierszu. 

Wyjście
Dla każdej liczby z wejścia wypisz liczbę będącą odpowiedzią na postawiony problem.


Przykład

Wejście
2
5
6

Wyjście
9
11

 

FR_08_07 - Drzewo binarne II

 

Drzewo binarne jakie jest każdy widzi :)

drzewo binarne

 

Określ ile liczb z podanego zbioru znajduje się na i-tym poziomie drzewa binarnego. Na pierwszym poziomie jest liczba 1, na drugim 2 oraz 3, na trzecim 4, 5, 6 i 7 itd.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość liczb w zbiorze (nie więcej niż 105).

W drugim wierszu n liczb całkowitych, każda mieszcząca się w przedziale [1..263-1].

W trzecim wierszu jedna liczba q określająca liczbę zapytań (nie więcej niż 104).

Kolejne q liczb to zapytania złożone z jednej liczby całkowitej i należącej do przedziału [1..106].

Wyjście

Dla każdego zapytania jedna liczba określająca ilość liczb z podanego zbioru znajdujących się na i-tym poziomie drzewa binarnego.

Przykład

Wejście:
10
1 2 9 10 7 6 12 6 6 6
3
1
2
3

Wyjście:
1
1
5


FR_08_08 - Oświetlenie

 

W Bajtocji jest bardzo długa i prosta ulica, przy której zainstalowane są lampy oświetleniowe oraz przystanki. Wszystkie lampy działają w ten sam sposób, tzn. oświetlają wszystkie przystanki, które znajdują się nie dalej niż r od lampy. Twoim zadaniem jest wyznaczenie minimalnej wartości r, dla której wszystkie przystanki będą oświetlone, tzn. dla każdego przystanku istnieć będzie lampa oddalona nie dalej niż r od przystanku. Jedna lampa może oświetlić dowolną liczbę przystanków, ale wszystkie te przystanki muszą znajdować się w odległości nie większej niż r od niej. 

Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n, m (1 ≤ n, m ≤ 5 × 105) oznaczające odpowiednio liczbę przystanków i liczbę lamp znajdujących się przy ulicy. Drugi wiersz zawiera rosnący ciąg nliczb całkowitych a1a2, ..., an (0 ≤ ai ≤ 109) - współrzędne przystanków. Wiersz trzeci zawiera rosnący ciąg mliczb całkowitych b1b2, ..., bm (0 ≤ bi ≤ 109) - współrzędne lamp. 

Wyjście
Na wyjściu należy wypisać minimalne r, przy którym wszystkie przystanki będą oświetlone. 


Przykład

Wejście
7 3
1 8 13 15 20 25 26
4 15 24

Wyjście
4

 

FR_08_09 - Piq

 

Określ współczynniki a1000 i a0 wielomianu W(x) = a1000 x1000 + a999 x999 + ... + ax + a0, jeśli wiadomo, że są one liczbami pierwszymi oraz podany jest jeden z pierwiastków tego wielomianu.

Wejście

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

Każdy zestaw składa się z trzech liczb całkowitych A, L M, oznaczających kolejno całości, licznik i mianownik miejsca zerowego (L < M). Liczby L i M mieszczą się w przedziale [1..2⋅109], natomiast A w [0..109]. Np. zestaw liczb 3 12 30 wyznacza ułamek trzy całe i dwanaście trzydziestych.

Wyjście

Dla każdego zestawu danych dwie liczby a1000 i a0. Dane są tak dobrane, aby uzyskać jednoznaczną odpowiedź.

Przykład

Wejście:
1
3 12 30

Wyjście:
5 17

FR_08_10 - Radio

 

Radio

Miejscowa rozgłośnia radiowa wychodząc naprzeciw oczekiwaniom mieszkańców, postanowiła dotrzeć z informacjami do każdego gospodarstwa w okolicy. Rozgłośnia ta posiada dwa maszty nadawcze ulokowane w różnych miejscach. Trzeba je nastawić, aby wysyłały fale radiowe na takie odległości, które swoim zasięgiem obejmą wszystkie gospodarstwa w okolicy. Po szerokich konsultacjach społecznych postanowiono, że przy regulacji masztów musi być uwzględniony warunek zminimalizowania obszaru zasięgu fal radiowych, bo podobno fale te źle wpływają na samopoczucie zwierząt zamieszkujących pobliskie lasy. Trzeba więc tak dobrać długość promieni fal radiowych obu masztów, aby łączny obszar ich zasięgu był możliwie najmniejszy. Znając współrzędne masztów i współrzędne wszystkich gospodarstw napisz program, który wyznaczy sumę długości promieni zasięgu fal obu masztów, uwzględniając czynnik zminimalizowania obszaru zasięgu fal radiowych. Należy założyć, że czasami wystarczy uruchomić tylko jeden maszt, którego obszar zasięgu fal będzie wystarczający do spełnienia warunków podanych wyżej. . 

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. W pierwszym wierszu każdego zestawu znajduje się pięć liczb całkowitych nx1y1x2y2 (2 ≤ n ≤ 104, -103 x1y1x2y2 ≤ 103), gdzie n to liczba gospodarstw, a x1y1x2y2, to współrzędne całkowite dwóch masztów. Dalej w nwierszach podane są współrzędne gospodarstw, w każdym wierszu dwie liczby całkowite x, y (-103 ≤ x, y ≤ 103). 

Wyjście
Na wyjściu należy wypisać sumę długości promieni fal radiowych obu masztów (z dokładnością do dwóch cyfr po przecinku) obejmujących swoim zasięgiem wszystkie gospodarstwa i jednocześnie spełniających warunek zminimalizowania obszaru zasięgu fal radiowych.

Przykład

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

Wyjście
3.24
4.00
2.83

 

FR_08_11 - Gra w bańki

 

Zasady gry. Wyobraźmy sobie oś liczbową na której umieszczamy bańki poruszające się w lewo lub w prawo. Wszystkie bańki poruszają się ze stałą prędkością niektóre w lewo inne w prawo. Jeśli dojdzie do kolizji, tzn. spotkają się dwie bańki, które poruszają się w przeciwnych kierunkach, to następuje jedna z dwóch sytuacji:

  • jeśli bańki są różnej wielkości, to większa pochłania mniejszą zwiększając swoją objętość o tą zjedzoną
  • jeśli bańki są równej wielkości, to bańki pękają, gdyż żadna z nich nie jest w stanie pochłonąć bańki równej sobie.

Twoim zadaniem jest określenie początkowych pozycji baniek, które ukończą grę. Bańka ukończy grę, wtedy i tylko wtedy, gdy uda jej się opuścić oś.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę baniek na osi (nie więcej niż milion)

W drugim wierszu n baniek w postaci liczby całkowitej reprezentującej objętość bańki (objętości baniek mieszczą się w przedziale [1..106].

W trzecim wierszu znaków należących do zbioru {l, r} określających kierunek poruszania się baniek. I-ty znak określa kierunek i-tej bańki: - w lewo, r - w prawo.

Wyjście

Początkowe pozycje baniek, które opuszczą planszę gry. Pozycje podajemy jako rosnący ciąg. Pierwsza bańka wysunięta najbardziej na lewo ma numer 1, druga 2 itd.

Przykład

Wejście:
5
2 4 3 2 1
r r l r l

wyjście:
1 2 4

FR_08_12 - POMOCY!

 

Cześć, mam na imię Janek i to ja wołałem pomocy. Jestem dobrym duchem tego zadania. Słuchaj, bo jest taka sprawa. Tak wyszło, że utknąłem w mrocznej pustce Wielkiego Sędziego i nie wiem jak się wydostać (autor zadania też jest bezradny). To ten … pomożesz mi? Aby mnie uwolnić musisz rozwiązać to zadanie, a w zamian przyniosę Ci szczęście w następnych zadaniach. Musiałbyś policzyć długość liczby w dowolnym systemie pozycyjnym. Sam zrobiłbym to zadanie w 5 minut, ale wiesz, mroczna pustka – nic tu nie ma, mojego komputera też nie. To jak, umowa stoi?

Wejście

Tak jak powiedział Janek zadanie to polega na obliczeniu długości liczby w dowolnym systemie pozycyjnym. W pierwszym wierszu wejścia znajduje się jedna liczba naturalna (t<=103) oznaczająca liczbę zestawów danych. Każdy zestaw składa się z dwóch liczb całkowitych nieujemnych: n, czyli dana liczba zapisana w systemie dziesiętnym (n<=1012) i p, czyli podstawa systemu, w którym należy podać długość liczby n (2<=p<=103).

Wyjście

Dla każdego zestawu danych należy podać jedną liczbę, będącą długością liczby zapisanej w systemie pozycyjnym p.

Przykład

Wejście:

2

7 2

0 7

Wyjście:

3

1

 

FR_08_13 - Matematostenes i funkcje trygonometryczne

 

Matematostenes jest dosyć ekscentrycznym mieszkańcem Programinii. Krótko mówiąc udaje Greka. Chodzi w todze, na nogach ma koturny, a jego twarz okrywa długa, siwa broda. Często chodzi po głównych rynkach niektórych miast Programinii (gdzieniegdzie zwanych main’ami) i zadaje przypadkowym przechodniom pytania z informatyki i matematyki. Tym razem tym szczęściarzem jesteś Ty i otrzymałeś takie pytanie:

„Azaliż czyliż istnieje sposobność, aby funkcje trygonometryczne dla kąta dowolnego bez użycia funkcji wbudowanych, lecz tylko trygonometrycznych wyznaczyć? Jeżeli twa odpowiedź twierdzącą jest, jak też byś to uczynił?”

Nieco zdziwiony i speszony tak archaiczną mową odpowiedziałeś, że tak istnieje taka możliwość, lecz musisz się nad tym zastanowić. Program z odpowiedzią na to nurtujące pytanie prześlesz Matematostenesowi listem, a on go oceni, akceptując, bądź wytykając błędy.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna (<=103) oznaczająca liczbę zestawów danych. Każdy zestaw składa się z jednej liczby całkowitej (-1012<=k<=1012), która oznacza dany kąt (podany w stopniach), którego wartości funkcji trygonometrycznych (sinus, kosinus, tangens, kotangens) należy wyznaczyć. Uwaga oto lista fraz niedozwolonych: sin, cos, tan, cot, Sin, Cos, Tan, Cot, SIN, COS, TAN, COT.

Mała podpowiedź od autora: w C++ w słowie using jest zawarte słowo sin.

Wyjście

Na wyjściu należy podać wartości funkcji trygonometrycznych dla danego kąta w kolejności: sinus, cosinus, tangens, kotangens. Wartość  funkcji należy zaokrąglić do dwóch miejsc po przecinku. Uwaga, jeśli wartość pewnego kąta dla danej funkcji nie istnieje należy wypisać nie istnieje (chodzi tu np. o tangens 90 stopni).

Przykład

Wejscie:

1

45

Wyjście:

0.71 0.71 1.00 1.00

 

FR_08_14 - Przygody Informatyka Jonesa II

 

Informatyk Jones odkrywa nieznane krainy, gdzie ludzie posługują się przedziwną mową. Pragnie przesyłać jej tajniki królowi Asemblordowi - władcy Programinii.  Tak jak poprzednim razem nasz tytułowy bohater, ze względu na specyfikację Programinii (w każdym regionie lub mieście mówi się innym językiem programowania) musi napisać list do swego władcy, będący programem. Oczywiście wcielasz się w jego rolę i twoim zadaniem jest napisanie takiego programu. Tym razem Jones  jest zainteresowany przypadkami, używanymi w tym dziwnym języku z gramatyką, oto zasady ich tworzenia:

Najpierw zacznijmy od faktu, iż w tym języku każdy rzeczownik posiada rodzaj, który zależy od ostatniej głoski.

 

Rodzaj męski

Rodzaj żeński

Rodzaj nijaki

-a,-h,-k,-d,-g,-r,-t,-s,-p

-b,-e,-o,-w,-i,-j,-l,-m,-u,

-n,-f,-y,-z

 

Jest to tabela, która przyporządkowuje każdej głosce, na którą kończy się dany wyraz, rodzaj tego wyrazu. Na przykład wyraz int miałby rodzaj męski, bo kończy się na -t, wyraz double miały rodzaj żeński, bo kończy się na -e, a wyraz sizeof byłby rodzaju nijakiego, bo kończy się na -f. Rodzaj jest zawsze stały i niezmienny dla danego wyrazu. Zacznijmy omówienie poszczególnych przypadków:

1. Mianownik (M.) - prosta sprawa, wypisujemy wyraz z wejścia.

2. Dopełniacz (D.) – dodajemy końcówki w zależności od rodzaju: -le w rodzaju męskim, -la w rodzaju żeńskim i –lo w rodzaju nijakim. Istnieje jeszcze zasada mówiąca, że jeżeli wyraz kończy się na układ: samogłoska-spółgłoska-samogłoska (np. while) to usuwamy ostatnią samogłoskę i dodajemy powyższe końcówki w zależności od rodzaju, poza tym jeżeli wyraz kończy się na połączenie dwóch lub więcej spółgłosek (np. int) to przed końcówką dopełniacza wstawiamy –e.

3. Celownik (C.) – dodajemy końcówki w zależności od rodzaju: -es w rodzaju męskim, -as w rodzaju żeńskim i –os w rodzaju nijakim. Ustępstwem od tej reguły będą sytuacje gdy:

-w rodzaju męskim wyraz kończy się na układ samogłoska-spółgłoska (np. for) to jeżeli dana samogłoska jest różna od –e oraz –i to usuwamy ostatnią spółgłoskę i dodajemy –es; jeżeli dana samogłoska to –i wtedy możemy usunąć ostatnią spółgłoskę jeśli przed –i stoi –n-k lub –g;

-w rodzaju żeńskim lub nijakim wyraz kończy się na układ samogłoska-spółgłoska to jeżeli dana samogłoska dla rodzaju żeńskiego jest różna od –a oraz –i natomiast dla nijakiego jest różna od –o a także –i to usuwamy ostatnią spółgłoskę i dodajemy końcówki charakterystyczne dla rodzaju; jeżeli przedostatnia głoska to –i wtedy możemy usunąć ostatnią spółgłoskę  jeżeli przed –i stoi –n.

4. Biernik (B.) - jeżeli wyraz kończy się na spółgłoskę charakterystyczną dla rodzaju żeńskiego lub męskiego to dodajemy -o, a jeżeli będzie to spółgłoska charakterystyczna dla rodzaju nijakiego dodajemy -a, jeżeli wyraz kończy się na -e-o lub -y dodajemy –l; jeżeli wyraz kończy się na samogłoski -a-u lub -i pozostawiamy bez zmian.

5. Narzędnik (N.) – przypadek nie jest zależny od rodzaju, zazwyczaj dodajemy –un, chyba, że: wyraz kończy się na –u wtedy dodajemy samo –n oraz jeśli wyraz kończy się na układ samogłoska-spółgłoska wtedy jeżeli dana samogłoska jest różna od -i oraz -u to usuwamy ostatnią spółgłoskę i dodajemy –un; jeżeli dana samogłoska to –i to możemy usunąć ostatnią spółgłoskę tylko wtedy jeżeli przed –i stoi –n.

6. Miejscownik (Ms.) – dodajemy końcówki w zależności od rodzaju: -je dla rodzaju męskiego, -ja dla rodzaju żeńskiego i –jo dla rodzaju nijakiego. Końcówki te możemy dodać jeżeli głoska –j nie występuje w wyrazie na ostatnim lub przedostatnim miejscu, w przeciwnym wypadku wyraz pozostawiamy bez zmian; jeżeli wyraz kończy się na układ samogłoska-spółgłoska-samogłoska to usuwamy ostatnią samogłoskę i dodajemy końcówkę w zależności od rodzaju; jeżeli wyraz kończy się na połączenie dwóch lub więcej spółgłosek to przed końcówką miejscownika dodajemy –e.

7. Wołacz (W.) – przypadek nie jest zależny od rodzaju, najczęściej dodajemy –eo, chyba, że: wyraz kończy się na –e wtedy dodajemy tylko –o oraz jeżeli wyraz kończy się na układ e-spółgłoska wtedy usuwamy daną spółgłoskę i dodajemy –o.

8. Possessivus (P.) – odpowiada na pytania czyj?, czyja?, czyje? (w języku polskim w jego roli używamy dopełniacza), przypadek ten nie jest zależny od rodzaju, zazwyczaj dodajemy –in, chyba, że: wyraz kończy się na –i wtedy dodajemy samo –n oraz jeżeli wyraz kończy się na układ samogłoska-spółgłoska wtedy jeżeli dana samogłoska jest różna od –i to usuwamy ostatnią spółgłoskę i dodajemy –in.

Wejście

W pierwszym wierszu wejścia znajduje się jedna niewielka liczba naturalna oznaczająca liczbę zestawów danych. Każdy zestaw składa się z jednego wyrazu o długości do 25 znaków, będących tylko małymi literami. Podany wyraz ma formę mianownika. 

Wyjście

Na wyjściu należy podać odmianę danego wyrazu przez powyższe przypadki w kolejności tak jak zostały podane. Na początku każdego wiersza należy umieścić skrót od danego przypadku (podane są w nawiasach powyżej), następnie należy podać daną formę rzeczownika (formę i skrót należy oddzielić). Poszczególne przypadki oddzielamy znakiem nowej linii. Poszczególne wyjscia dla danych zestawów testowych należy oddzielić znakiem nowej linii.

Przykład

Wejście:

2

ilja

int 

Wyjście:

M. ilja

D. iljale

C. iljaes

B. ilja

N. iljaun

Ms. ilja

W. iljaeo

P. iljain

M. int

D. intele

C. intes

B. into

N. intun

Ms. inteje

W. inteo

P. intin

 

FR_08_15 - Bryła

 

Zadanie polega na obliczeniu pola (P) i objętości (V) bryły zbudowanej z sześcianów o wymiarach 1x1x1.

Wyobraźmy sobie płaszczyznę współrzędnych XYZ, na której w punkcie docelowym (0;0;0) znajduje się sześcian, który 
się rozrasta o kolejne tworząc nową bryłę w zależności od kierunków współrzędnych podanych na wejściu np.:

- 'X' czyli x+1, dając bryłę (0;0;0)+(1;0;0)
- 'x' czyli x-1, dając bryłę (0;0;0)+(-1;0;0)
- 'Y' czyli y+1, dając bryłę (0;0;0)+(0;1;0)
- 'y' czyli y-1, dając bryłę (0;0;0)+(0;-1;0)
- 'Z' czyli z+1, dając bryłę (0;0;0)+(0;0;1)
- 'z' czyli z-1, dając bryłę (0;0;0)+(0;0;-1)

Przykładowo mając startowy sześcian o współrzędnych (0;0;0) dołączymy do niego kolejne o kierunkach "XYZ" otrzymamy bryłę o współrzędnych (0;0;0)+(1;0;0)+(1;1;0)+(1;1;1), co daje nam pole równe 18, a objętość równą 4 jednostkom.

Sześciany mogą na siebie nachodzić, nie powodując żadnych zmian w wielkości bryły.
Maksymalna ilość jednostek, w których bryła może się rozrosnąć to 45 w każdym z 6 kierunków.

Wejście:

W pierwszym wierszu znajduje się liczba t (t<=105), oznaczająca liczbę testów do zadania.
W kolejnych t wierszach znajdują się ciągi znaków określające kierunki tworzenia bryły.
Ciąg zawiera maksymalnie 1000 znaków.

Wyjście:

Pole poprzedzone literą 'P' oraz znakiem równości ("P = ").
Objętość poprzedona literą 'V' oraz znakiem równości ("V = ").

Przykład

Wejście:
3
XYZ
XXxx
XyxYXyxYXyxY
Wyjście:
P = 18
V = 4
P = 14
V = 3
P = 16
V = 4

FR_08_16 - Ciekawy czworokąt

 

W okrąg o środku O i promieniu R wpisany jest czworokąt ABCD. Wyznaczyć pole danego czworokąta jeśli ∠ AOB = α, ∠ BOC = β oraz ∠ COD = γ.

Autor zadania: Mateusz Ławicki ( Unmi )

Wejście

Cztery niewielkie liczby naturalne dodatnie: Rαβ i γ oraz αβ + γ  < 360°.

Wyjście

Jedna liczba rzeczywista z dokładnością do 4 miejsc po przecinku reprezentująca pole czworokąta ABCD.

Przykład

Wejście:
6 30 45 135

Wyjście:
43.4558

FR_08_17 - Zjazd koordynatorów

 

Co kilka lat, główna siedziba Kryptografii i Kryptoanalizy w Bajtocji organizuje zjazd koordynatorów opiekujących się pracownikami na ściśle przydzielonych obszarach. Głównemu koordynatorowi Jakubowi zależy, aby nikt nie był poszkodowany i chce zorganizować spotkanie w mieście, które będzie miastem centralnym, tzn. że najbardziej oddalony koordynator od tego miasta, będzie miał do niego drogę o długości i jednocześnie nie będzie istniało takie miasto centralne, aby najbardziej oddalony koordynator znajdowałby się w odległości d - 1 od niego. Niestety zadanie okazało się bardzo skomplikowane, a więc zatrudniono najlepszego specjalistę w mieście (ciebie), żeby napisał program, który wyznaczy numery miast, które mogą być centralne. Zakładamy, że jeśli istnieje połączenie między dwoma miastami, to odległość między nimi wynosi 1

Wejście

W pierwszym wierszu dwie liczby całkowite n i p określające odpowiednio liczbę miast oraz liczbę połączeń między nimi (3 < n < 1001, 2 < p < 5001).

W kolejnych p wierszach po dwie liczby a i b oznaczające, że istnieje bezpośrednie połączenie drogą dwukierunkową między miastami b (0 < ab ≤ n, a  b oraz nie istnieją dwa identyczne połączenia).

Następnie jedna liczba k określająca liczbę koordynatorów. Liczba ta mieści się w przedziale [1..50].

W ostatnim wierszu k miast, w których mieszkają koordynatorzy. W jednym mieście może mieszkać kilku koordynatorów.

Gwarantuje się, że z dowolnego miasta a można dotrzeć do dowolnego miasta b.

Wyjście

Numery miast, w których można zorganizować spotkanie koordynatorów uporządkowane rosnąco.

Przykład

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

Wyjście:
2 5


FR_08_18 - parkrun Działdowo II

 

Jest sobota, jest parkrun! W ponad 1300 miejscach na całym świecie, w każdą sobotę o godzinie 9 rano, aktywni ludzie spotykają się, aby wspólnie przebiec, przemaszerować, przebiec z psem, z wózkiem lub nordic walking, pokonać pięć kilometrów. Działdowo jest jednym z kilkudziesięciu miast w Polsce, gdzie takie biegi się odbywają. Za organizację odpowiedzialni są wolontariusze, którzy pełnią różne role. Niektórzy robią zdjęcia, inni skanują uczestników biegu, jeszcze inni mierzą czas. Jest także osoba, która zamyka stawkę. Pewnej soboty okazało się, że zawiódł stoper. Bez tego urządzenia koordynator biegu nie będzie wstanie wprowadzić wyników z biegu. Okazało się jednak, że każdy z uczestników tego dnia posiadał zegarek z GPS-em, który odmierzał tempo biegu. Dzięki temu, biegacze podawali koordynatorowi swoje tempa (nie koniecznie uporządkowane), a koordynator podawał ich pozycję na mecie na podstawie do tej pory podanych informacji. Niestety, ta czynność stawała się coraz trudniejsza gdy liczba uczestników wzrastała. Pomóż działdowskim koordynatorom i napisz program, który będzie w stanie odpowiadać, jaką aktualnie pozycję zajmuje biegacz na podstawie dotychczasowych danych. 

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę biegaczy (nie więcej niż 300001).

W kolejnych n wierszach tempa biegaczy (min/km) podane z dokładnością do sześciu miejsc po przecinku. Każde tempo mieści się w przedziale [3..8]. Gwarantuje się, że liczby są unikatowe.

Wyjście

Dla każdego podanego tempa, aktualna pozycja uczestnika.

Przykład

Wejście:
6
3.123333
4.000000
3.500000
5.000000
4.300000
5.445000

Wyjście:
1
2
2
4
4
6

FR_08_19 - Tysiące talii kart

 

Załóżmy, że dysponujesz bardzo dużą ilością talii kart (nawet 100 000). Każdą z nich przetasowujemy, następnie kładziemy je obok siebie numerując kolejno począwszy od 1. Początkowe ustawienie każdej z talii  jest znane.

Teraz wykonujemy szereg czynności. Oto opis pojedynczej z nich: podajemy przedział [a..b], nakazujący, że w każdej z talii od numeru a do numeru b, bierzemy kartę z wierzchu i kładziemy ją pod spód. Twoim zadaniem jest wypisanie porządku kart po wykonaniu tych operacji.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę talii (liczba n należy do przedziału [1..100 000].

W kolejnych n wierszach po 24 karty otrzymane w wyniku tasowania. Dla ułatwienia, karty numerujemy od 1 do 24.

Następnie jedna liczba q określająca ilość zapytań (nie więcej niż milion).

Każde zapytanie składa się z dwóch liczb a i b, oznaczające początkowy numer talii i końcowy numer talii.

Wyjście

Wypisanie ustawienia kart każdej z talii po wykonaniu wszystkich zapytań.

Przykład

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

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

FR_08_20 - Lider w macierzy

 

Def. Lider w zbiorze, to taka wartość, która występuje więcej razy niż połowa wszystkich jego elementów. Np. dla liczb 1, 1, 2, 1 liderem jest liczba 1, natomiast zbiór 1, 2, 2, 1, 3, 1 nie posiada lidera.

Wyobraźmy sobie macierz prostokątną n x m wypełnioną liczbami całkowitymi. Twoim zadaniem jest odpowiedzenie na pytanie, czy w podmacierzy kwadratowej o wymarach p x p znajduje się lider (0 < p ≤ min(nm)). 

Wejście

W pierwszym wierszu trzy liczby całkowite n, i p, określające wymiary macierzy. Liczby n i m mieszczą się w przedziale [2..1000].

W kolejnych n wierszach po liczb całkowitych. Każda mieści się w przedziale [1..1 000 000].

Następnie jedna liczba q określająca liczbę zapytań (nie więcej niż 105).

Każde zapytanie składa się z dwóch liczb x i y, wyznaczające współrzędne lewego górnego rogu podmacierzy (0 < x ≤ n - x, 0 < y ≤ m - y)

Wyjście

Dla każdego zapytania liczba, która jest liderem, jeśli lider istnieje w podmacierzy lub 0, gdy lidera nie ma.

Przykład

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

Wyjście:
1
0
2