C++
FRAKTAL

Omówienie zadań z VIII rundy

Drzewo binarne II
To zadanie można rozwiązać na wiele sposobów. Nasza propozycja jest taka. Tworzymy wyzerowaną tablicę na 64 elementy. Następnie każdą wczytaną liczbę skracamy przez dwa, aż otrzymamy 0. Każde takie skrócenie powoduje przejście o poziom wyżej na drzewie. Liczba skróceń tej liczby, to poziom na której ona pierwotnie się znajdowała. Do zliczenia ilości liczb na danym poziomie służy podana wcześniej tablica. Żadna liczba mieszcząca się w typie long long nie może znajdować się na poziomie wyższym niż 63.
 
Gra w bańki
To zadanie można w prosty sposób rozwiązać używając struktury stos. Wrzucamy kolejne wartości baniek, które poruszają się w prawą stronę. Napotykając bańkę przesuwającą się w lewym kierunku, do pary pobieramy bańkę ze stosu (jeśli nie jest oczywiście pusty) i dokonujemy konfrontacji.
 
Lider w macierzy
Wykonujemy preprocessing. Przechodzimy od lewej do prawej strony macierzy wyznaczając kolejnych liderów. Gdy znajdziemy się po prawej stronie, obniżamy się o jeden wiersz i poruszamy się w lewo itd. Przy każdym takim przejściu usuwamy tylko jedną kolumnę (wiersz) i dodajemy tylko jedną po prawej stronie. Wartości w macierzy nie przekraczają miliona, więc można stworzyć odpowiednią tablicę do zliczania wartości. Ilość elementów dla lidera jest z góry znana, więc bez problemu możemy na bieżąco określać, czy jest lider w podmacierzy. Na zapytania odpowiadamy w czasie stałym
 
Tysiące talii kart
Wzorcowe rozwiązanie ma złożoność liniową. Tworzymy wyzerowaną tablicę o długości ilości talii + 1. Następnie dla każdego początku przedziału zwiększamy wartość tablicy o 1, a na końcu przedziału zmniejszamy o 1. Następnie poruszamy się przez wszystkie elementy tablicy zwiększając każdą następną o wartość poprzedniej. W ten sposób wiemy, ile razy była położona na spód karta.
To zadanie można było rozwiązać także drzewem przedziałowym.
 
Piq
W tym zadaniu wystarczy odwołać się do twierdzenia o wymiernych pierwiastkach wielomianu.
Zjazd koordynatorów
Algorytm grafowy – przeszukiwanie wszerz.
Parkrun Działdowo II
Można rozwiązać to zadanie wykorzystując drzewo przedziałowe.
 

Edycja VIII

Ósma runda konkursu programistycznego "FRAKTAL" właśnie przeszła do historii. W zawodach wzięło udział 124 zawodników i zawodniczek z całego kraju - jest to oficjalny rekord tego konkursu. Jak można domyśleć się po rozwiązaniach, zadania przypadły wam do gustu. Ten konkurs tworzymy z myślą o osobach z każdego pułapu zaawansowania, napotkaliście zadania zarówno elementarne jak i zaawansowane. Przejdźmy więc do podsumowania.

I miejsce

Wygrał użytkownik, którego nick to Sinister rozwiązując wszystkie 20 zadań - gratulujemy

II miejsce

Jan Ciołek , który rozwiązał także wszystkie zadania

III miejsce

Sebastian Michoń z Poznania rozwiązując także wszystkie zadania.

Nagroda specjalna

Nagrodę specjalną otrzymuje osoba na pozycji (2017 mod 115) + 1 = 63 = Andrzej Kur

Nagrodę specjalną od VI edycji przydzielamy osobie o numerze wygenerowanym wzorem [rok] mod [liczba uczestników, którzy rozwiązali chociaż jedno zadanie] + 1, jeśli wypadnie, na osobę z pierwszej trójki, nagrodę otrzymuje osoba z czwartej pozycji.

Zwycięzcom gratulujemy wytrwałości i wiedzy. Nagrody przydzielane są według tych kryteriów. Proszę o przesłanie adresu mailowego, na który mamy wysłać kartę podarunkową allegro oraz kod źródłowy zadania, które zostało zaakceptowane jako ostatnie pod adres Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript. 
Nagrody zostały ufundowane przez serwisy:

  1. math.edu.pl
  2. algorytm.edu.pl

Podziękowania

Pragnę podziękować osobom, który w ramach wolontariatu poświęcili swój cenny czas na pomoc w zorganizowaniu cieszącego się coraz większym zainteresowaniem konkursu "FRAKTAL", a przede wszystkim

  • Mariuszowi Śliwińskiemu, który od samego początku objął patronat nad konkursem i przygotował 5 bardzo ciekawych zadań
  • Michałowi Sieczczyńskiemu, uczniowi ZSNR1 w Działdowie, uczniowi klasy trzeciej, który przygotował trzy fascynujące zadania: "POMOCY!", "Matematostenes i funkcje trygonometryczne" oraz "Przygody Informatyka Jonesa II"
  • Mikołajowi Dembskiemu - uczniowi klasy 3a I LO w Działdowie, ZSNR1, za ułożenie wymagającego zadania "Bryła"
  • Mateuszowi Ławickiemu - uczniowi klasy 3a I LO w Działdowie, ZSNR1, za przygotowanie świetnego zadania: "Ciekawy czworokąt"

Wielkie dzięki dla Was panowie

Omówienie zadań

Omówienie niektórych zadań pojawi się na stronie facebookowej (i tu proszę o polubienia i komentarze do zadań oraz ciekawe ich rozwiązania)

Kolejna runda

Już dziś zapraszam na koleją rundę „FRAKTALA”, która odbędzie się w kwietniu 2018 roku. 

Zadania

Większość zadań będzie jeszcze dziś dodana na polskiego spoja a wszystkie będzie można testować na stronie spoj.com/WSDOCPP

Do zobaczenia w kwietniu!!!

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

Zadania z VII edycji konkursu FRAKTAL

FR_07_01 - LATKARF

 

Zadanie konkursowe podane jako pierwsze powinno być proste - tzw. elementarne i takie jest. Dla zadanych dwóch liczb określ, która jest większa. Niestety przez nieuwagę, autor zadania podał cyfry liczb w odwrotnej kolejności. Twoim zadaniem jest porównanie ich i wypisanie tej, która jest większa (jeśli liczby są równe, wypisujemy dowolną). Porównanie powinno być przeprowadzone na liczbach zapisanych w oryginale.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zapytań (< 106).

W drugim wierszu po dwie liczby naturalne zapisane w odwrotnej kolejności cyfr. Każda mieści się w 32 bitowym typie danych.

Wyjście

Dla każdego zapytania większa liczba w jej pierwotnej postaci.

Przykład

Wejście:
3
2 0
123 321
231 141

Wyjście:
2
321
141

FR_07_02 - Porównywanie ułamków

 

Porównywanie ułamków

Porównaj dwa ułamki zwykłe. 

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 dane są przypadki testowe. Dla każdego przypadku testowego podane są dwa ułamki zwykłe w formacie a/b c/d, gdzie abcd to liczby całkowite dodatnie spełniające warunki: 1 ≤ abcd, ≤ 104.

Wyjście
Dla każdego przypadku testowego należy wypisać w osobnym wierszu:
1, jeśli pierwszy ułamek jest większy
2, jeśli drugi ułamek jest większy
0, jeśli ułamki mają tę samą wartość


Przykład

Wejście
3
1/2 1/3
2/3 3/4
3/6 1/2

Wyjście
1
2
0

 

FR_07_03 - Register & Login

 

Bajtek tworzy nowy portal randkowy. Aktualnie pracuje nad funkcjami tworzenia oraz logowania się do kont, z których to będą korzystać samotni mieszkańcy Bajtocji. Powszechnie wiadomo, że bazy danych użytkowników rządzą się swoimi prawami: loginy muszą się od siebie różnić, mieć określoną budowę itp. Bajtek powinien się również zatroszczyć o tzw. "Januszy i Grażyny bezpieczeństwa" – ludzi, którzy uważają, że 3-literowe hasła są skuteczną bronią przeciw atakom równie samotnych hakerów. Jako że wiesz, jak dużej liczbie mieszkańców Bajtocji doskwiera samotność, pomóż 8-bitowemu przyjacielowi w napisaniu programu, który przeprowadzi proces rejestracji nowych użytkowników i zweryfikuje próby logowania na konta. Może wymyślisz też nazwę portalu?

 

Wejście

Wejście składa się z nieokreślonej ilości wierszy. W pierwszej kolejności znajduje się jeden z dwóch napisów: "register" lub "login" oznaczających rejestrację i logowanie do konta.
Po określeniu czynności widnieje niewielka ilość x działań do wykonania przez program. W kolejnych xlinijkach, znajdują się login i hasło.

 

Wyjście

W przypadku rejestracji twoim zadaniem jest sprawdzić czy:
1) Login oraz hasło są zgodne z niżej postawionymi kryteriami. Jeśli nie to należy wypisać "Blad".
- login musi zawierać od 3 do 12 znaków, a hasło od 5 do 15
- login może zawierać tylko litery oraz cyfry (wielkość liter nie ma znaczenia)
- hasło musi zawierać conajmniej jedną wielką, małą literę, jedną cyfrę oraz jeden znak specjalny 
2) Login nie został już użyty przez innego użytkownika podczas rejestracji.
Jeśli został już użyty, należy wypisać "Login zajety".
Jeśli wszystko będzie się zgadzać, należy wypisać "Zarejestrowano".
W przypadku logowania twoim zadaniem jest określić czy:
1) Konto istnieje, jeśli nie to należy wypisać "Konto nie istnieje".
2) Login i hasło zgadzają się ze sobą, w innym wypadku należy wypisać "Zle haslo".

W przypadku rejestracji twoim zadaniem jest sprawdzić czy:
1) Login oraz hasło są zgodne z niżej postawionymi kryteriami, jeśli nie to należy wypisać "Blad".
- login musi zawierać od 3 do 12 znaków, a hasło od 5 do 15
- login może zawierać tylko litery oraz cyfry (wielkość liter nie ma znaczenia)
- hasło musi zawierać co najmniej jedną wielką, małą literę, jedną cyfrę oraz jeden znak specjalny 

2) Login nie został już użyty przez innego użytkownika podczas rejestracji.
Jeśli został już użyty, należy wypisać "Login zajety", natomiast jeśli wszystko będzie się
zgadzać należy wypisać "Zarejestrowano".

W przypadku logowania twoim zadaniem jest określić czy:
1) Konto istnieje, jeśli nie to należy wypisać "Konto nie istnieje".
2) Login i hasło zgadzają się ze sobą, w innym wypadku należy wypisać "Zle haslo".
Jeśli wszystko się zgadza należy wypisać "Zalogowano".

Przykład

Wejście:

register 3
bajtek13 Haslo123@
BITEK 123456789
bajtek13 bajteK55%
login 5
bajtek13 bajteK55%
bajtek13 Haslo123@
BITEK 123456789
bajtocjusz haselko49
bitariusz 123haSlo!@#
register 1
BITEK Dobrehaslo1!
login 1
BITEK Dobrehaslo1!

Wyjście:

Zarejestrowano
Blad
Login zajety
Zle haslo
Zalogowano
Konto nie istnieje
Konto nie istnieje
Konto nie istnieje
Zarejestrowano
Zalogowano

FR_07_04 - Przecena

 

Przecena

Cenę pewnego towaru obniżono najpierw o a%, a następnie nową cenę obniżono jeszcze o b%. O ile procent obniżono początkową cenę towaru? 

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 dane są po dwie liczby całkowite a i b (1 ≤ ab ≤ 99), oznaczające kolejne wartości procentowe o jakie obniżono dwukrotnie cenę towaru.

Wyjście
Dla każdego przypadku testowego, w osobnym wierszu, należy wypisać o ile procent (z dokładnością do dwóch cyfr po przecinku) obniżono początkową cenę towaru.


Przykład

Wejście
1
50 50

Wyjście
75.00

 

FR_07_05 - Obraz

 

Załóżmy, że dwa piksele są do siebie podobne wtedy, gdy suma bezwzględnych róznic ich wartości R, G, B jest mniejsza lub równa pięć. Oblicz, jaką część wszystkich pikseli obrazu stanowią piksele podobne do odpowiednich pikseli drugiego obrazu.

Input

Na początku zostaną podane 2 liczby naturalne x i y (x,y<=100), a następnie y linii po x kolorów zapisanych w systemie szesnastkowym. W kolejnej linii znajdzie się liczba t oznaczająca ilość obrazów do porównania z obrazem wyjściowym. Każdy kolejny obraz ma taką samą wielkość jak obraz wyjściowy.

Output

Dla każdego porównanego obrazu należy wypisać w nowej linii stosunek ilość pikseli podobnych do ilości pikseli całego obrazu w formie ułamka dziesiętnego z dokładnością do 2 miejsc po przecinku.

Example

Input:
2 3
#2923BE #84E16C 
#D6AE52 #9049F1 
#F1BBE9 #EBB3A6 
3
#2822BD #83E26B 
#D6AE51 #914AF2 
#F2BAEA #EAB2A6 
#2925BC #86E26B 
#D6AF53 #9248F0 
#F2BCE9 #EDB3A6 
#2920BC #85E36A 
#D6AF4F #8E47F4 
#F1BBE6 #EBB6A8

Output:
1
1
0.83

FR_07_06 - Szachownica vs kwadraty

 

Wyobraźmy sobie szachownicę podzieloną na n x n jednostkowych kwadratów. Zadanie polega na zliczeniu wszystkich kwadratów, które występują na szachownicy.

Wejście

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

W kolejnych wierszach po jednej liczbie n określające wymiar szachownicy (< 106+1).

Wyjście

Dla każdego zapytania liczba kwadratów, które znajdują się na szachownicy o wymiarze n x n.

Przykład

Wejście:
3
1
2
4

Wyjście:
1
5
30

FR_07_07 - Przygody Informatyka Jonesa

 

Nasz tytułowy bohater jest słynnym podróżnikiem, pochodzącym z Programinii. W kraju tym, wszyscy w zależności od regionu czy miasta mówią różnymi językami programowania. Na przykład w Trójmieście Języków C, gdzie miasta to: City, City++ i City#, ludzie mówią odpowiednio w języku C, C++ i C#. Ciekawym regionem jest również Okręg Przemysłowy Brainf*cktory, gdzie mówi się, a jakże, w Brainf*cku. Wróćmy, więc do naszego podróżnika. Król Asemblord – władca Programinii, zlecił mu misję zbadania odległych krain, leżących poza Programinią. Tym razem Informatyk Jones udał się do bardzo dziwnego kraju. Istoty tam żyjące nie mówią językiem programowania, lecz normalnym językiem z gramatyką. Długo zajęło mu poznanie i nauczenie się owej mowy, lecz w końcu udało się i zapragnął stopniowo wysyłać królowi tajniki jej gramatyki, lecz biorąc pod uwagę charakterystykę Programinii, nie pisał on zwykłych listów, lecz programy. Wysyłając „list” opisujący zasady tworzenia liczby mnogiej, napotkał pewne problemy. Oto zasady jej tworzenia:

 

- jeżeli w wyrazie występuje samogłoska –e to –e zmienia się w –i oraz jeżeli w wyrazie występuje samogłoska –a to –a zmienia się w –e,

- jeżeli w wyrazie nie występują samogłoski –a ani –e, ale jeżeli występuje samogłoska –o to –o zmienia się w –e, jeżeli –o, ani –a, ani –e nie występuje, ale występuje –u to –u zamieniamy w –e i jeżeli żadna z wymienionych samogłosek nie występuje to, jeżeli występuje samogłoska –y to –y zmienia się w –e,

- samogłoska –i nie ulega żadnym zmianom.

 

Zasady wydają się proste, lecz język ten charakteryzuje się pewnymi nadrzędnymi regułami:

- w każdym wyrazie musi znajdować się co najmniej jedna samogłoska,

- dwie lub więcej takich samych samogłosek nie mogą występować obok siebie, czyli połączenia typu –aa, -ee, –oo, -uu, -ii -yy są niedozwolone,

- samogłoski nie mogą być używane jako półsamogłoski, czyli –i nie może być używane jako –j, oznacza to, że nie mogą występować takie połączenia jak –ie, -ia, -io, iu, iy, chyba, że przed takim połączeniem występuje spółgłoska –n, wtedy należy to przeczytać jako polskie –ń oraz połączenie może być dozwolone, jeżeli przed połączeniem –ie występuje –k lub –g, ponieważ wtedy czytamy tak jak po polsku np. w wyrazach kiełbasa czy kiełki (połączenia –ei, -ai, –oi -ui, yi są jak najbardziej dozwolone).

 

Wciel się w rolę słynnego podróżnika Informatyka Jonesa i prześlij królowi „list”, w którym zostaną omówione zasady tworzenia liczby mnogiej. Nie trzeba się obawiać, że król nie zrozumie „listu”, ponieważ zna on wszystkie języki programowania. Zważ każde słowo, ponieważ władca Programinii posiada osobistego cenzora SPOJusza, który przedstawia królowi tylko poprawnie napisane „listy”. 

Wejście

W pierwszym wierszu zostanie podana jedna, niewielka liczba naturalna t określająca liczę zestawów danych. Każdy zestaw składa się z jednego wyrazu zawierającego maksymalnie 25 znaków, będących jedynie małymi literami alfabetu łacińskiego (wszystkimi oprócz x i v) (wyrazy mogą, ale nie muszą spełniać zasad tego języka).

Wyjście

Na wyjściu należy podać liczbę mnogą, utworzoną od danego wyrazu (zgodnie z zasadami omówionymi powyżej). Samogłoski -a oraz -e należy zamieniać jednocześnie. Jeżeli w wyrazie pewna samogłoska nie może zostać zamieniona, ponieważ zamiana ta spowodowałaby złamanie którejkolwiek z reguł nadrzędnych, to nie zamieniamy danej samogłoski. Jeżeli w wyrazie pewna samogłoska nie może zostać zamieniona to nie oznacza to, że inne także nie mogą zostać zamienione. Jeżeli wyraz na wejściu nie spełnia którejkolwiek z reguł nadrzędnych należy wypisać: „wyraz niezgodny z zasadami mowy”. 

Przykład

Wejście:
13
bool
sqrt
io
hila
gaur
huo
onge
niea
feal
esa
kear
seanta
eao
Wyjście:
wyraz niezgodny z zasadami mowy
wyraz niezgodny z zasadami mowy
wyraz niezgodny z zasadami mowy
hile
geur
hue
ongi
niea
feal
ise
kier
seante
eao

FR_07_08 - Czerwony proszek

 

Zapewne każdy z nas słyszał o sandboxowej grze, jaką jest Minecraft(coś wspaniałego Cool). Jako że zawsze bardzo interesowała mnie informatyka, najbardziej lubiłem tworzyć różnego rodzaju mechanizmy, bramki logiczne itp. Czerwony proszek — tzw. redstone był jednym z kluczowych dla mnie elementów rozgrywki, który służył do zasilania maszyn, bramek logicznych, ... Zmodyfikujmy trochę zasady gry i przenieśmy tę analogię — napiszmy program, który sprawdzi, czy jesteśmy w stanie przeprowadzić energię przez obszar o wymiarach 10 na 10. Zaczynamy w punkcie (0,0), wprowadzając tu energię na redstone, która musi dotrzeć do punktu (9,9), również na redstone. Wyjaśnijmy zasady. Energia może poruszać się tylko w poziomie i pionie, po czerwonym proszku (oznaczamy 'R'). Energia może przemieszczać się w zasięgu maksymalnie pięciu jednostek, długością tzw. sznura. Jeśli po pięciu jednostkach nie napotka wzmacniacza, tzw. repeatera (oznaczamy 'P'), to nie będzie w stanie pójść dalej. Jeśli zaś napotka wzmacniacz po pięciu jednostkach lub wcześniej, będzie w stanie przemieścić się kolejne pięć jednostek, w każdą następną stronę. Energia nie jest w stanie przenosić się bezpośrednio ze wzmacniacza na wzmacniacz. Drogi nie łączą się oraz nie zapętlają, również nie do chodzi do sytuacji, w której czerwony proszek przebiega bezpośrednio obok drugiego, łącząc się z nim, tworząc tzw. sieci(pola). Całą resztę oznaczamy dowolnymi innymi znakami np. 'O'.

Wejście

Na wejście programu zostanie podana pewna nieokreślona ilość 100-znakowych łańcuchów znaków, reprezentujących zawartość obszaru. Każdy łańcuch oddzielony jest znakiem nowej linii.

Wyjście

Na wyjściu programu ma pojawić się ciąg binarny, odpowiadający wejściu. Jeśli jesteśmy w stanie przeprowadzić energię z punktu (0,0) do punktu (9,9), wypisujemy 1, jeśli nie, to 0.

Przykład

Wejście:
RROOOOOOOOORROOOOOOOOORPOOOOOOOOORROOOOOOOOORROOOOOOOOORPOOOOOOOOORROOOOOOOOORROOOOOOOOORPOOOOOOOOOR
ROOOOOOOOOROOOOOOOOOROOOOOOOOOROOOOOOOOOROOOOOOOOOPOOOOOOOOOROOOOOOOOOROOOOOOOOOROOOOOOOOORRPRRRRRRR

Wyjście:
1 
0

FR_07_09 - System liczbowy inny niż inne

 

Na temat systemów liczbowych można pisać bardzo wiele. Ulubionym system dla ludzi jest system dziesiętny. Wszelkie wartości liczb zapisane za pomocą dziesięciu cyfr są doskonale rozumiane i raczej nie wyobrażamy sobie aby używać innego. Komputery lubują się w systemie dwójkowym, a w Trójkolandii obowiązującym systemem jest system trójkowy. Zaważ, że w każdym wspomnianym systemie podstawa jest stała - w dziesiętnym jest to liczba 10, natomiast w dwójkowym liczba 2. W tym zadaniu zajmiemy się systemem, w którym mnożniki kolejnych pozycji nie są zdefiniowane w postaci potęgi pewnej podstawy tylko przez silnię kolejnych liczb naturalnych dodatnich.

Np. liczba

(100)10 = 4⋅4! + 0⋅3! + 2⋅2! + 0⋅1! = (4020)!

 Zadanie polega na zamianie liczby z systemy dziesiętnego na opisany w treści zadania. Rozpatrujemy cyfry: {0, 1, 3, ..,9, A, B, ...}. 

Wejście

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

W kolejnych t wierszach po jednej liczbie całkowitej a zapisanej w systemie dziesiętnym mieszczącej się w przedziale [0..264-1].

Wyjście

Dla każdego zestawu testowego po jednej liczbie zapisanej w systemie silniowym.

Przykład

Wejście:
3
10
100
0

Wyjście:
120
4020
0

FR_07_10 - Szyfr vs kwadraty

 

Znany kryptograf i doradca prezydencki profesor Algobit opracował kwadratowy system szyfrujący, który będzie chronił wszystkie strategiczne informacje Państwa. Prace nad tym skomplikowanym szyfrem trwały miesiącami. Kryptoanalizą zajmowały się najlepsze specjalistki w tej dziedzinie. Stwierdzono jednoznacznie, że utworzony system jest bezpieczny i bez znajomości podstaw działania systemu nie da się go złamać. Jeśli jednak nie zgadzasz się z tym co tu napisałem, spróbuj obalić tą teorię i odszyfruj szyfrogram dowodząc swojej ogromnej inteligencji :).

Wejście

Pewna nieokreślona liczba wierszy. W każdym wierszu jedno zadanie do odszyfrowania. Liczba znaków jest nie większa niz 1024.

Wyjście

Dla każdego wiersza oryginalna wiadomość.

Przykład

Wejście:
AMO LAT A A  K  
BKLKO O LIL E E 
FKLRT AA 

Wyjścia nie podano celowo.

FR_07_11 - Mieszanie tablicy

 

Przydatną funkcją jest system mieszający elementy tablicy. Poniżej znajduje się opis takiego systemu:

Zasada mieszania:

Wyobraźmy sobie trzy struktury działające w następujący sposób:

  1. Struktura pierwsza (stos): element, który jako ostatni został dodany, jako pierwszy będzie zdjęty i usunięty ze struktury, itd..
  2. Struktura druga (kolejka FIFO): element, który jako pierwszy został dodany, jako pierwszy będzie zdjęty i usunięty ze struktury, itd.
  3. Struktura trzecia (kolejka priorytetowa): element, który ma największą wartość, będzie zdjęty jako pierwszy i usunięty ze struktury, itd.

Elementy tablicy, które chcemy wymieszać dodajemy cyklicznie do struktury nr 1, 2 oraz 3. Następnie w ten sam sposób zdejmujemy ze struktur. 

Na wejściu pojawią się elementy tablicy już pomieszane, twoim zadaniem jest wypisanie kolejnych elementów tablicy w pierwotnym ich ustawieniu. Uwaga! Jeśli istnieje kilka prawidłowych odpowiedzi, wypisujemy dowolną.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę elementów tablicy (nie więcej niż 2 000 000). 

W drugim wierszu n liczb całkowitych. Każda z nich mieści się w przedziale [-109..109].

Wyjście

Na wyjściu wypisujemy przykładowe pierwotne ustawienie elementów tablicy.

Przykład

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

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

FR_07_12 - Czerwone mrówki

 

Czerwone mrówki

Przyrodnik Jasiu postanowił zbadać wścieklice, mrówki popularnie nazywane czerwonymi. W tym celu udał się do pobliskiego lasu, aby je poobserwować. Zdziwił się trochę, gdy zauważył, że kolonia czerwonych mrówek wymieszała się z kolonią rudnic. Postanowił zrobić trochę zdjęć. Po powrocie do domu zabrał się do analizowania zrobionych przez siebie zdjęć. Naszego przyrodnika interesuje, jaka jest liczebność wszystkich mrówek w najmniejszym prostokątnym obszarze, do którego należą wszystkie mrówki czerwone. Boki takiego prostokątnego obszaru muszą być równoległe do osi układu współrzędnych. Każda mrówka na zdjęciu opisana została za pomocą współrzędnych kartezjańskich oraz wartości 1 albo 0, gdzie 1 oznacza mrówkę czerwoną, a 0 oznacza mrówkę czarną. Teraz wystarczy już tylko napisać program, aby zaoszczędzić naszemu przyrodnikowi trochę czasu. 

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych - zdjęć. W pierwszym wierszu każdego zestawu znajduje się liczba całkowita n (2 ≤ n ≤ 105) oznaczająca liczebność mrówek na zdjęciu. W kolejnych n wierszach podane są po trzy liczby całkowite x, yk (0 ≤ xy ≤ 103, k={0,1}), gdzie wartości x, y oznaczają współrzędne kartezjańskie mrówki, a k to jej kolor. Dla k = 1 mrówka jest czerwona, dla k = 0 mrówka jest czarna. Można założyć, że żadna mrówka nie łazi po innej mrówce oraz, że rozmiar plików wejściowych nie przekracza 4 MB. 

Wyjście
Dla każdego zestawu należy wypisać w osobnym wierszu jedną liczbę - liczebność wszystkich mrówek zawierających się w najmniejszym prostokątnym obszarze, do którego należą wszystkie mrówki czerwone.


Przykład

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

Wyjście
6

Rysunek do przykładu
Mrówki czerwone jak i brzeg prostokątnego obszaru został oznaczony kolorem czerwonym. W prostokącie tym znajduje się łącznie sześć mrówek.

FR_07_13 - Strzelec wyborowy

 

Należy określić, czy pozycja strzelca pozwoli trawić w cel. Rozpatrujemy sytuację, gdzie podany jest punkt kartezjański, oznaczający pozycję strzelca, odcinek równoległy do osi OY będący celem oraz odcinek także równoległy do osi OY będący przeszkodą. Należy sprawdzić, czy przeszkoda nie zasłania całkowicie celu, tzn. czy strzelec jest w stanie trafić w dowolny punkt z przedziału obustronnie otwartego (yc1, yc2).

Wejście

W pierwszym wierszu trzy liczby całkowite: yc1, yc2, xc określające współrzędne celu będącego odcinkiem połączonym punktami o współrzędnych (xc, yc1) i (xc, yc2), (-106< yc1 < yc2 < 106, |xc| < 106).

W drugim jedna liczba q określająca liczbę zapytań (conajmniej jedno i nie więcej niż 1000).

Specyfikacja każdego zapytania:

W pierwszym wierszu współrzędne przeszkody, w drugim współrzędne strzelca.

Przeszkoda określona jest w postaci trzech liczb całkowitych yp1, yp2 oraz xp, określającymi przeszkodę będącą odcinkiem połączonym punktami o współrzędnych (xp, yp1) i (xp, yp2), (-106< yp1 < yp2 < 106, |xp| < 106).

Współrzędne strzelca to dwie liczby całkowite x i y, gdzie x > xc oraz |y| < 106. Odcinki ani pozycja celu nie nachodzą na siebie. 

Wyjście

Dla każdego zapytania napis TAK jeśli strzelec ma możliwość trafienia do celu lub NIE, gdy takiej możliwości brak.

Przykład

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

Wyjście:
NIE
TAK

Ilustracja przykładu

 

FR_07_14 - Plaster miodu

 

Plaster miodu

Narysuj plaster miodu złożony z n kolumn, po mkomórek w każdej kolumnie.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu podana jest liczba całkowita k (1 ≤ k≤ 100) oznaczająca liczbę kolumn plastra miodu. W wierszu drugim podanych jest k liczb całkowitych m (1 ≤ m ≤ 100) oznaczających liczebność sześciokątnych komórek w kolejnych kolumnach plastra miodu. 

Wyjście
Dla każdego przypadku testowego należy narysować właściwy plaster miodu używając trzech znaków: _, /, \, znaku spacji i znaku końca linii tak, jak to pokazane jest w przykładowym wyjściu. Każdy rysunek kończy znak końca linii.

Przykład

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

Wyjście
 _   _   
/ \_/ \_ 
\_/ \_/ \
  \_/ \_/
 _   _   _ 
/ \_/ \_/ \
\_/ \_/ \_/
/ \_/ \_/ \
\_/ \ / \_/
/ \_/ \_/ \
\_/ \   \_/
  \_/   / \
  / \   \_/
  \_/      

FR_07_15 - Sfeniczne i nie tylko

 

Miałeś już okazję zapoznać się z liczbami sfenicznymi chociażby rozwiązując jedno z zadań próbnym VII edycji konkursu "FRAKTAL". Przypomnijmy: liczba sfeniczna, to taka liczba naturalna, która rozkłada się na iloczyn dokładnie trzech różnych liczb pierwszych. Utrudnijmy to zadanie i zdefiniujmy liczbę k-sfeniczną. Liczbę k-sfeniczną nazywamy taką, która rozłoży się na iloczyn dokładnie k różnych liczb pierwszych. Zadanie polega na napisaniu programu, który będzie odpowiadać na pytanie, ile podano liczb k-sfenicznych w ciągu liczb naturalnych dodatnich począwszy od indeksu w przedziale [a..b], gdzie a to indeks początkowy przedziału, natomiast b to indeks końcowy (wyrazy ciągu indeksujemy od 1).

Wejście

W pierwszym wierszu jedna liczba naturalna n określająca długość ciągu (nie więcej niż milion).

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

Następnie jedna liczba q określająca liczbę zapytań. Każde zapytanie składa się z trzech liczb całkowitych ak takich, że 1 ≤ a ≤ b ≤ n definiujących przedział [a..b] oraz 1 ≤ k ≤ 20, określająca ilość liczb pierwszych w rozkładzie badanych liczb.

Wyjście

Dla każdego zapytania jedna liczba określająca liczbę liczb sfenicznych o k rozkładzie.

Przykład

Wejście:
7
3 6 8 9 20 13 80
5
1 7 3
1 7 1
2 6 2
5 7 3
1 1 1

Wyjście:
0
2
1
0
1

FR_07_16 - Zawody

 

Zawody

Jasiu i jego robot bierze udział w zawodach. Robot może poruszać się po prostokątnej mapie pól w metryce miasto. Startuje z lewego górnego pola do prawego dolnego i wraca z powrotem do punktu startu. Kiedy idzie na południowy-wschód może poruszać się tylko w prawo lub na dół, a w drodze powrotnej może poruszać się wyłącznie w lewo lub do góry. Robot powinien obrać taką drogę, aby odwiedzić jak najwięcej oznaczonych pól z gwiazdkami, przy czym robot nie może przechodzić przez pola oznaczone znakiem x. Po zbadaniu mapy, Jasiu zdaje sobie sprawę, że zadanie nie jest takie proste i trzeba robota odpowiednio zaprogramować. Dlatego uprzejmie prosi Ciebie o pomoc w napisaniu programu, który pozwoli robotowi optymalnie przejść mapę. Mając do dyspozycji mapę 2D, w której zaznaczone są pola z gwiazdkami oraz pola x, po których robot poruszać się nie może, wyznacz maksymalną liczbę pól z gwiazdkami, do których robot może dotrzeć. Pola z gwiazdkami odwiedzone dwa razy liczone są tylko raz.

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 znajdują się dwie liczby całkowite a, b (2 ≤ ab ≤ 100) oznaczające długość i szerokość mapy. W kolejnych wierszach opisana jest mapa złożona z b wierszy, każdy wiersz po aznaków o następujących oznaczeniach:
. - chodnik, po którym może poruszać się robot
* - pole z gwiazdką 
x - pola, po których robot poruszać się nie może

Należy założyć, że lewe górne pole oraz prawe dolne to pole, w którym nie ma znaku x oraz, że istnieje co najmniej jedna droga łącząca lewe górne pole z polem prawym dolnym.

Wyjście
Na wyjściu, dla każdego przypadku testowego, należy wypisać maksymalną liczbę pól z gwiazdkami, które robot może odwiedzić.

Przykład

Wejście
2
8 6
*.......
....**x.
..**..x*
.*xxx*..
...x*.x*
*.......
5 5
.*...
.xxx.
*.*.*
.xxx.
.*.*.

Wyjście
7
5

FR_07_17 - Bajtogalareta

 

Jak w wielu krajach, również w Bajtocji mieszkańcy wymyślili swój narodowy deser: bajtogalaretę. Są to galaretki zanużone w budyniu. Przysmak jest jednak w fazie testów. Przygotowuje się go w pojemnikach o wymiarach a[dm] x b[dm] x 1 dm. Najpierw do formy wpuszcza się sześcienne galaretki o objętości 1 dm3 każda. Zatrzymują się one w różnych miejscach pojemnika, ale ich odległości od jego dna oraz brzegów wyrażone w decymetrach są zawsze liczbami całkowitymi (specjalna receptura). Następnie od góry zalewa się je budyniem. Ten oczywiście ścieka na dół formy, gdy jednak spotyka na swojej drodze galaretkę, to połowa płynie na lewą stronę, a połowa na prawą. Gdy budyń nie mieści się z jednej strony, to przepływa na drugą. Jako że formy są szybko schładzane, nie działa tu zasada naczyń połączonych. Kucharze pracują jeszcze nad optymalną gęstością bajtogalarety i chcieliby prowadzić statystyki mówiące o tym, ile budyniu zajduje się w każdej kolumnie o szerokości 1 dm. Pomóż im i napisz program, który po prześwietleniu formy odpowie na ich pytanie.

Input

Na początku zostaną podane 4 liczby całkowite: a i b (a,b<=100) oznaczające wymiary formy, w (0<w<=a) mówiąca, na którym decymetrze od lewej strony znajduje się wlew budyniu oraz l oznaczająca ilość budyniu do dyspozycji w dm3.

Następnie do wczytania będzie b wierszy po a znaków "0" lub "1" oznaczających kolejno miejsce puste lub wypełnione galaretą. W każdym przypadku testowym budyń mieści się w pojemniku.

Output

Na wyjściu wypisz a liczb rzeczywistych odpowiadających ilości budyniu w każdej kolumnie pojemnika.

Example

Input:
14 8 6 22
00000000000000
01010110000000
01010100000000
00111101100000
10000101000000
00000111010000
01000001001010
00000001001000


Output:
1 1 3 1 3 1 3 0 2.5 2 0 2 1 1.5

FR_07_18 - Tentaizu

 

Tentaizu

Tentaizu to japońska gra umysłowa, której reguły przypominają trochę reguły popularnego sapera. Tentaizu to diagram 7 × 7, w którym dokładnie 10 spośród 49 pól to ukryte gwiazdy. Na podstawie wskazówek w postaci odkrytych liczb, należy ustalić, w których polach znajdują się gwiazdy. Liczba w polu określa, z iloma polami z gwiazdami sąsiaduje to pole poziomo, pionowo lub skośnie. Żadne pole liczbowe nie zawiera gwiazdy, ale gwiazda może zawierać się w polu, w sąsiedztwie której nie ma pól liczbowych. Jak się zapewne domyślasz, zadaniem Twoim jest napisanie programu, który rozwiąże Tentaizu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. W kolejnych wierszach znajdują się przypadki testowe. Każdy przypadek to początkowe Tentaizu, czyli diagram 7 × 7, na który składa się 7 wierszy po 7 znaków w każdym wierszu. Każe pole diagramu to albo znak kropki, albo liczba z przedziału [0-8]. Pomiędzy przypadkami testowymi znajduje się dodatkowy znak końca linii. 

Wyjście
Na wyjściu wydrukuj rozwiązany diagram Tentaizu w tym samym formacie co diagram wejściowy. Rozwiązany diagram oznacza, że należy zastąpić znakiem gwiazdki dokładnie 10 pól oznaczonych znakiem kropki. Należy założyć, że każdy diagram na wejściu ma dokładnie jedno unikalne rozwiązanie. Między wydrukowanymi diagramami może znajdować się dodatkowy znak końca linii.

Przykład

Wejście
2
.....1.
....22.
.1.....
..231.1
...1...
......3
..3..2.

1....0.
.1.....
1..3...
..23.2.
..3....
.3....2
1.1..2.

Wyjście
....*1.
....22.
.1*.*..
..231.1
..*1..*
.*...*3
.*3*.2*

1....0.
*1.*...
1..3*..
..23*2.
.*3*...
*3*..*2
1.1..2*

FR_07_19 - Sciezka

 

Jasio po godzinach spędzonych z matematyką musi czasem od niej odpocząć. Lubi wtedy grać w gry MMORPG. Królowa nauk jest jednak obecna i tutaj. Jasio w swojej grze ma do wykonana kilka zadań (questów). Aby wykonać każdy z nich, trzeba odwiedzić kilka miejsc. Miejsca są ze sobą połączone, ale żeby dostać się z jednego do drugiego, trzeba zapłacić określoną kwotę. Można jednak wyznaczyć optymalną trasę między nimi, wykonując kilka zadań w jednym czasie. Pomóż Jasiowi i oblicz, jaką najmniejszą kwotę musi przygotować, by wykonać wszstkie zadania.

Input

Na początku zostaną podane dwie liczby: m(m<100) oznaczająca ilość wszystkich miejsc oraz s(s<300) oznaczająca ilość dostępnych ścieżek między nimi. W kolejnych m liniach na wczytanie będą czekać nazwy miejsc (nie występują w nich spacje i nazwa jest krótsza niż 35 znaków). Potem podanych będzie s linii zawierających informacje o  ścieżkach: jakie miejsca łączą oraz jaki jest koszt podróży. W kolejnej linii znajduje się miejsce startowe. Na końcu wejścia do wczytania będzie od 1 do 3 linii. Każda z nich to zadanie złożone z nieokreśclonej liczby miejsc do odwiedzenia, jednak łączna ich ilość nie przekracza 50.

Output

Na wyściu ma znaleźć się jedna liczba oznaczająca kwotę potrzebną do wykonania wszystkich zadań.

Example

Input:
10 31
Town_of_Schuttgart
Town_of_Goddard
Rune_Township
Town_of_Aden
Town_of_Oren
Town_of_Giran
Town_of_Dion
Town_of_Gludio
Gludin_Village
Heine
Town_of_Schuttgart Town_of_Goddard 10000
Town_of_Goddard Rune_Township 10000
Town_of_Goddard Town_of_Aden 8100
Town_of_Goddard Town_of_Schuttgart 10000
Rune_Township Town_of_Goddard 10000
Rune_Township Town_of_Oren 10000
Rune_Township Town_of_Aden 37000
Town_of_Aden Town_of_Goddard 8100
Town_of_Aden Rune_Township 37000
Town_of_Aden Town_of_Oren 6900
Town_of_Aden Hunters_Village 5900
Town_of_Aden Town_of_Oren 6900
Town_of_Aden Town_of_Giran 13000
Town_of_Oren Town_of_Aden 6900
Town_of_Oren Rune_Township 10000
Town_of_Oren Hunters_Village 4100
Town_of_Oren Town_of_Giran 9400
Hunters_Village Town_of_Oren 4100
Hunters_Village Town_of_Aden 5900
Town_of_Giran Town_of_Aden 13000
Town_of_Giran Town_of_Oren 9400
Town_of_Giran Town_of_Gludio 29000
Town_of_Giran Town_of_Dion 6800
Town_of_Giran Heine 7600
Heine Town_of_Giran 7600
Heine Town_of_Dion 12000
Town_of_Dion Heine 12000
Town_of_Dion Town_of_Giran 6800
Town_of_Dion Town_of_Gludio 3400
Town_of_Gludio Gludin_Village 7300
Gludin_Village Town_of_Gludio 7300
Town_of_Goddard
Town_of_Gludio Town_of_Oren Town_of_Schuttgart
Heine Town_of_Oren Gludin_Village Gludin_Village
Rune_Township Town_of_Oren

Output:

100400

 

FR_07_20 - Lider II

 

W Dwójkolandii przyszedł czas na długo wyczekiwane wybory. Okręgi wyborcze wystawiły swoich kandydatów, a wyborcy zapoznali się z ich planami wyborczymi. Dziś jest dzień wyborów, a ty zostałeś powołany na wolontariat polegający na zliczaniu głosów i określeniu, czy w danym okręgu wyborczym jakiś kandydat osiągnął więcej niż 50% głosów. System wyborczy w Dwójkolandii działa następująco. Wyborcy należący do danego okręgu wyborczego są zapisani na spójnej liście, jeden za drugim, itd. Wszystkie listy połączone są w jedną wielką listę. Dodatkowo każdy wyborca ma prawo zmienić swój wybór i zaznaczyć innego kandydata - taki system :). Ty jednak jesteś bardzo sprytną osobą i pojąłeś trudną sztukę programowania. Napisz program, który znacznie ułatwi ci pracę na wolontariacie, wyznaczający lidera w przedziale liczb. Wykonujemy dwie operacje. Pierwsza, to zmiana wyboru kandydata na inny (zmiana decyzji wyborcy), druga to sprawdzenie, czy w okręgu zaczynającym się od wyborcy na pozycji a a kończącym się na wyborcy na pozycji b został wybrany kandydat do rządzenia Dwójkolandią - tzn. liczba oddanych głosów na tę osobę jest większa niż 50%.

Wejście

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

W drugim wierszu n liczb naturalnych określających głosy wyborców. Każdy kandydat jest reprezentowany przez liczbę mieszczącą się w przedziale [0..109]. Jeden kandydat może być wybierany w kilku okręgach (taki system :)).

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

Specyfikacja każdego zapytania:

najpierw jeden znak i lub q, następnie dwie liczby całkowite. Jeśli pojawi się i, zostaną podane dwie liczby całkowite x i y, oznaczające, że należy podmienić decyzję wyborcy z pozycji w ciągu na y, natomiast, gdy pojawi się znak q, to pojawią się dwie liczby a i b, definiujące przedział [a...b], w którym należy określić, czy występuje lider w tym przedziale (1 ≤ ≤ n, 0 ≤ y ≤ 109, 1 ≤  b  n).

Wyjście

Dla każdego zapytania, w którym wystąpiła litera q należy wypisać lidera zbioru w przedziale [a..b], lub napis brak, gdy lider nie występuje.

Przykład

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


Wyjście:
2
2
7
brak