|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie B - Przedszkole |
W sklepach brakuje pieluch. Bajdocja jest już największym importerem smoczków, a wózki dziecięce drożeją szybciej niż mieszkania. W tempie dotąd niespotykanym rośnie nam nowe pokolenie. A wszystko to przez zarządzenia wprowadzone przez charyzmatycznego Ministra Dedukcji Bajdockiej:
W pierwszym wierszu wejścia znajduje się liczba następujących testów. W pierwszym wierszu każdego testu jest słowo napisane przez przedszkolankę, składające się z liter alfabetu angielskiego. Maksymalna długość słowa wynosi 15 liter. W kolejnym wierszu jest dodatnia liczba całkowita N - liczba dzieci w klasie. Klasy nie przekraczają 1000 osób. W kolejnych N wierszach znajdują się słowa napisane przez kolejne dzieci (1-wsze, 2-gie, n-te). Słowa składają się z maksymalnie 15 liter alfabetu angielskiego. Kolejne testy są oddzielone pojedynczą pustą linią.
Wejście2 Odgrzybiacz 3 Odbrzybiacz Odgrzybiacz odgrzybiacz Ministerstwo 4 Ninisterstwo Mimisterstwo inisterstwom inisterstwoo |
Wyjście2 3 1 2 1 4 3 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie C - Trasy |
Bolek jest wiochmenem. Każdego roku, odbywa on wycieczkę rowerową pomiędzy dwoma wioskami. Jest wiele różnych tras, które może on obrać, lecz jest pewna maksymalna długość trasy, której nie chce przekroczyć. Mając dane informacje o wioskach, drogach oraz ich długościach, Bolek chciałby mieć listę różnych tras pomiędzy dwoma wybranymi wioskami, których długość nie przekracza jego możliwości, tak aby spokojnie wybrać sobie, którąś z nich. Twoim zadaniem jest napisanie programu, który wypisze listę tych tras od najkrótszej do najdłuższej.
Przyjmujemy następujące założenia:
W pierwszej linii wejścia znajduje się liczba testów D. Dalej następują opisy testów. Pierwsza linia każdego testu składa się z dwóch liczb całkowitych V i R (2 ≤ V ≤ 20, 0 ≤ R ≤ 40). V oznacza liczbę wiosek, a R liczbę dróg pomiędzy nimi. W każdym z kolejnych R wierszy znajduje się opis i-tej drogi w postaci trzech liczb Ci, Di, Oi. Pierwsze dwie oznaczają numery wiosek połączonych drogą, a Oi oznacza odległość między nimi. Wioski numerowane są od 1 do V, a 1 ≤ Oi ≤ 10000. W kolejnej linii znajdują się 2 różne liczby X i Y, oznaczające, odpowienio, numer wioski początkowej oraz numer wioski docelowej. W ostatniej linii występuje jedna liczba całkowita M (1 ≤ M ≤ 10000), oznaczająca maksymalną długość trasy, która Bolek jest gotów pokonać.
Dla każdego testu z wejścia, w oddzielnych liniach wypisz trasy spełniające wymagania Bolka poprzedzone długością danej trasy i dwukropkiem. Trasy powinny być wypisane w kolejności od najkrótszych do najdłuższych. W przypadku tras o takiej samej długości wypisz je w kolejności leksykograficznej. Wyniki kolejnych testów oddziel pustymi liniami.
W przypadku, gdy żadna trasa nie spełnia ograniczeń Bolka, wypisz słowo NIE
Wejście3 4 5 1 2 2 2 3 2 1 4 1 3 4 4 1 3 3 1 3 4 4 5 1 2 2 2 3 2 1 3 3 3 4 4 1 4 1 1 4 10 5 7 1 2 2 2 4 2 1 4 5 3 4 3 2 5 3 3 5 2 2 3 1 1 3 8 |
Wyjście3: 1 3 4: 1 2 3 1: 1 4 7: 1 3 4 8: 1 2 3 4 3: 1 2 3 7: 1 2 4 3 7: 1 2 5 3 8: 1 4 2 3 8: 1 4 3 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie D - Ulotki |
Denerwują Cię ludzie, którzy na przystankach autobusowych wręczają Ci setki głupich ulotek? Mnie też. Too bad, bo Twoim zadaniem jest napisanie programu, który pomoże firmie, dla której pracują...
W pewnym mieście zatrudniono studentów do rozdawania ulotek. Każdemu z nich został przypisany dokładnie jeden przystanek autobusowy, na którym spędza on cały dzień, rozdając ulotki spotkanym tam ludziom.
System transportowy w tym mieście jest dość specyficzny. Linie autobusowe są jednokierunkowe i każda łączy dokładnie dwa przystanki, autobusy nie zatrzymują się pomiędzy przystankami. Opłata za przejazd daną linią (tj. pomiędzy dwoma przystankami) jest określona w specjalnych tablicach. Połączenia autobusowe są rozplanowane w ten sposób, że każda trasa w dwie strony (tj. trasa, która zaczyna się i kończy na tym samym przystanku) musi przebiegać przez dworzec centralny.
Zatrudnieni studenci każdego ranka wyruszają z dworca centralnego. Każdy z nich musi dotrzeć do przydzielonego mu przystanku autobusowego. Każdy student ma przydzielony dokładnie jeden przystanek i każdy przystanek ma przydzielonego dokładnie jednego studenta. Wieczorem studenci muszą wrócić na dworzec centralny.
Twoim zadaniem jest napisanie programu, który pomoże zminimalizować sumaryczny koszt przejazdów, który firma ponosi każdego dnia, opłacając przejazdy zatrudnionych studentów.
Pierwsza linia wejścia zawiera pojedynczą liczbę, oznaczającą liczbę testów. W kolejnych liniach opisane są kolejne testy. Każdy test rozpoczyna się linią zawierającą dwie liczby całkowite A i B, (1 ≤ A,B ≤ 1000000). A jest liczbą przystanków autobusowych (licząc również dworzec centralny), a B jest liczbą linii autobusowych. W każdej z kolejnych B linii znajduje się opis jednej linii autobusowej. Linia składa się z trzech liczb - numeru przystanku początkowego, numeru przystanku docelowego i ceny biletu. Dworzec centralny ma numer 1. Ceny są dodatnimi liczbami całkowitymi. Ich suma nie przekracza 1000000000. Możesz założyć, że z każdego przystanku można dotrzeć do każdego innego.
Dla każdego testu, wypisz jedną linię, zawierającą minimalną kwotę pieniędzy potrzebną każdego dnia na przejazdy zatrudnionych studentów.
Wejście2 2 2 1 2 5 2 1 17 5 7 2 1 65 5 1 30 1 2 20 3 4 10 1 3 20 2 4 10 4 5 20 |
Wyjście22 320 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie E - Stringi |
W tym zadaniu słowo stringi odnosi się do łańcuchów DNA, a nie do części garderoby. Sorry. Zadanie jest następujące:
Mamy dane N łańcuchów DNA. Wiemy że wszystkie łańcuchy oprócz maksymalnie jednego są poprawne. Natomiast możliwe jest, iż wśród nich znajduje się jeden łańcuch zmutowany. Mutant różni się tym od łańcucha poprawnego, iż ma inną zasadowość. Aby znaleźć mutanta przeprowadzamy szereg doświadczeń. Doświadczenie polega na wrzuceniu pewnej liczby łańcuchów, którymi dysponujemy do dwóch naczyń z roztworem. Kolor naczynia będzie odzwierciedlał sumaryczną zasadowość łańcuchów DNA tam się znajdujących. Dysponując bardzo dokładnymi przyrządami pomiarowymi jesteśmy w stanie powiedzieć, który roztwór ma większą zasadowość lub stwierdzić, że oba mają identyczną zasadowość. Niestety mamy ograniczony budżet i wolno nam wykonać tylko K doświadczeń. Czy to wystarczy, aby w każdym przypadku znaleźć mutanta?
Uwaga: Każdy, kto troche zna się na biologii wie, że nie ma problemu, żeby po doświadczeniu wyjąć nasze łańcuchy DNA z roztworów. Jak ktoś nie wierzy, to niech sobie w domu sprawdzi.
W pierwszym wierszu znajduje się liczba oznaczająca liczbę następujących testów. W każdym kolejnym wierszu znajduje się opis jednego testu w postaci dwóch liczb: N, K (0 ≤ N,K ≤ 2000000000).
Dla każdego testu wypisz TAK, jeśli da się jednoznacznie stwierdzić, czy wśród naszych łańcuchów jest mutant (i jeśli tak, to czy da się go wskazać), bądź też NIE w przeciwnym wypadku.
Wejście2 4 2 3 2 |
WyjścieNIE TAK |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie F - Duchy |
Za górami, za lasami, za głębokimi jeziorami, na bardzo wysokich skałach, w bardzo starym zamczysku żyły sobie bardzo nowoczesne duchy. Każdy z nich miał swoją prywatną komnatę, w której ćwiczył sztukę perfekcyjnego straszenia zabłąkanych turystów. Duchy lubiły swoje własne towarzystwo, więc po długich godzinach ćwiczeń bardzo często odwiedzały się wzajemnie, żeby sobie poplotkować. Ponieważ jednak przechodzenie przez bardzo grube mury w solidnie zbudowanym zamku było bardzo męczące (a duchy miały już swoje lata), więc postanowiły sobie zamówić urządzenia do teleportacji. Z powodu jednak zbyt małej liczby gotówki zostawianej przez nielicznie odwiedzających zamczysko ludzi, nie starczyło im jej na zakup "tuneli teleportacyjnych" z każdej komnaty do wszystkich pozostałych. Dlatego trzeba było wybrać, które komnaty połączyć jednokierunkowym tunelem z innymi. Stało się to przyczyną wielkiej kłótni, ponieważ każdy duch miał swoje własne ulubione ścieżki pomiędzy komnatami. W końcu postanowiono, że będą losowały dwa numery komnat a i b, a następnie połączą komnatę a-tą z b-tą jednokierunkowym tunelem (którym można się teleportować z komnaty a do b). Całą operację powtarzały dopóki miały pieniądze na zakup kolejnego tunelu. Wszystko byłoby dobrze, ale po pilotażowym zainstalowaniu okazało się, ze teleportacja tak się duchom spodobała, że zamiast ćwiczyć trudną sztukę straszenia ludzi, ciągle teleportowały się w kółko z jednej komnaty do drugiej. Aby temu zapobiec postanowiono, że nie będą instalowały tuneli, które umożliwiałyby niekończące się teleportacje - konieczność "zwykłego" przechodzenia przez ściany była wystarczająco męcząca i powodowała, że duchy nie teleportowały się bez celu.
Twoim zadaniem, jako pracownika dystrybutora "tuneli teleportacyjnych" jest wskazanie, których tuneli z listy podanej przez duchy nie należy instalować.
W pierwszej linii znajduje się liczba komnat w zamku (1 ≤ K ≤ 1000). W drugiej linii znajduje się liczba wylosowanych przez duchy tuneli (1 ≤ T ≤ 300000). W następnych T liniach znajdują się kolejno wylosowane liczby a oraz b (1 ≤ a,b ≤ K).
W kolejnych liniach należy podać opis tuneli których nie należy instalować. Muszą być one wypisane w takiej samej kolejności w jakiej znajdowały się na liście dostarczonej przez duchy. Wyjście należy zakończyć linią zawierającą dwa zera odzielone spacją.
Wejście4 5 2 4 4 3 3 2 1 2 3 1 |
Wyjście3 2 3 1 0 0 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Poznań, 26 maja 2007 |
Zadanie G - Podróże pana Jana - wycieczka na wschód |
Podczas swoich ostatnich wojaży pan Jan usłyszał legendy, że na wschodzie istniała kiedyś wspaniała cywilizacja. W związku z tym, jako cel swojej następnej podróży obrał właśnie wschód. Postanowił zaplanować tak swoją podróż, aby odwiedzić jak najwięcej miast. Pan Jan ma jednak wrodzoną awersję do kierunku zachodniego, dlatego nie chce nigdy przemieszczać się w tym kierunku (zakładamy, że zachód jest w kierunku malejących x-ów). Każdego dnia pan Jan przemieszcza się z jednego miasta do drugiego. W ciągu jednego dnia nie może jednak przebyć więcej niż k kilometrów. Zaplanuj tak podróż pana Jana, aby odwiedził jak najwięcej miast pamiętając o tym, by nocleg nigdy nie odbył się dwa razy w tym samym mieście (wtedy wycieczka stałaby się nudna). Przez pojedyncze miasto może przejechać dowolną liczbę razy (ale zatrzymać się w nim na nocleg może tylko raz). Wycieczka może skończyć się w dowolnym mieście.
W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.
W pierszwej linii każdego zestawu danych będą podane 2 liczby: N (1 ≤ N ≤ 1000) określająca liczbę miast oraz k (1 ≤ k ≤ 107). W kolejnych N liniach podane są współrzędne i-tego miasta: xi, yi (0 ≤ xi, yi ≤ 108). W ostatniej linii wejścia będzie podana liczba M określająca numer miasta, z którego pan Jan chciałby rozpocząć wędrówkę (1 ≤ M ≤ N).
Dla każdego zestawu danych wypisz maksymalną liczbę miast które pan Jan może odwiedzić w ciągu jednej podróży.
Wejście2 4 1 0 0 1 0 1 1 2 0 1 5 2 0 1 2 2 3 1 2 0 2 1 1 |
Wyjście3 5 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Poznań, 26 maja 2007 |
Zadanie H - Podróże pana Jana - podróż dookoła świata |
Jako ostatnią podróż w swoim życiu pan Jan postanowił odbyć podróż dookoła świata. Jednak jego poznańskie korzenie nie pozwalają mu na taką rorzutność, by wydać oszczędności swojego życia (niemałe zresztą) na wycieczkę. Dlatego też postanowił, że będzie korzystał tylko z tanich środków lokomocji:
Twoim zadaniem jest sprawdzenie, czy istnieje możliwość zaplanowania takiej podróży tanimi przewoźnikami. Spółki oferujące tani transport nie oferują jednak podróży w obie strony (na przykład wyjazd do kraju ogarnietego dżumą jest tanii, jednak za powrót trzeba zapłacić "odrobinę" więcej). Podróż nie musi obejmować wszystkich miejsc i może rozpoczynać się w dowolnym punkcie, ważne tylko, aby kończyła się i zaczynała w tym samym miejscu.
W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.
W pierszwej linii każdego zestawu danych będą podane 2 liczby: N (1 ≤ N ≤ 1000) określająca liczbę miejsc oraz M (0 ≤ M ≤ 3*N*(N-1)), oznaczająca liczbę oferowanych przejazdów. W kolejnych M liniach podane będą oferowane przejazdy w postaci x y s, gdzie x,y będą określały punkt początkowy oraz końcowy transportu (1 ≤ x, y ≤ N, x ≠ y) zaś s będzie jednym z ciągów znaków "TLS", "TLP", "TLL" na oznaczenie środka transportu.
Dla każdego przypadku testowego wypisać TAK, jeśli podróż można zaplanować zgodnie z zachciankami pana Jana (w szczególności, koniecznie ze zniżką!) lub NIE w przeciwnym wypadku.
Wejście3 3 3 1 2 TLS 2 3 TLP 3 1 TLL 3 6 1 2 TLS 2 3 TLP 3 1 TLL 1 2 TLP 2 3 TLL 3 1 TLS 3 3 1 2 TLL 1 3 TLL 2 3 TLL |
WyjścieNIE TAK NIE |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Poznań, 26 maja 2007 |
Zadanie I - Podróże pana Jana - pakowanie |
Pan Jan bardzo lubi podróżować. Ostatnio zaplanował bardzo daleką podróż i ma wiele rzeczy do zabrania ze sobą. Chciałby spakować swoje rzeczy w torby, które sumarycznie kosztują jak najmniej. Sklep oferuje torby różnych typów. Torba danego typu może udźwignąć tylko określony ciężar i ma określoną cenę. Pomóż wybrać panu Janowi zestaw toreb, w które będzie mógł spakować wszystkie potrzebne rzeczy, a którego koszt będzie najmniejszy. Pan Jan może kupić dowolną liczbę toreb danego typu.
W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.
Pierwsza linia każdego zestawu zawiera liczbę N (1 ≤ N ≤ 20), określającą liczbę rzeczy, które pan Jan planuje zabrać w podróż oraz liczbę M (1 ≤ M ≤ 50), określającą liczbę różnych typów toreb. W kolejnych M liniach każdego testu będą znajdować się pary liczby wi, ci (1 ≤ wi, ci ≤ 1000) określające maksymalny udźwig oraz koszt torby danego typu. W ostatniej linii znajduje się N liczb (1 ≤ Ti ≤ 1000), określających wagę poszczególnych elementów. Udźwig co najmniej jednej torby jest niemniejszy niż waga najcięższej rzeczy (na pewno istnieje rozwiązanie).
Dla każdego zapytania wypisać minimalny koszt zestawu toreb.
Wejście3 5 2 5 10 8 20 6 1 2 5 4 5 3 3 2 6 7 10 10 4 5 5 3 2 10 1 10 6 1 7 8 10 6 4 4 3 1 5 |
Wyjście40 19 30 |
_%ЎD佳ho=6}-Nt.E q!PCM29K!ף7 :EwRmɜ]G0Rt2ƒJR ~ )?-KF,GETm{E=^2QVUC'kV\R`;E 団0Čƌ>,*cj:.{/X%3u|J5gvaK[ޏ ef!hצ?ls1AL`3:;uZcM擖U__= @u
KWʏ_| Ȉ
Jasio przyszedł na świat dokładnie sześć lat, trzy miesiące i czternaście dni temu i uczy się już w pierwszej klasie szkoły podstawowej. Teraz właśnie przyszedł czas na naukę tabliczki mnożenia, ale ma z jej nauką pewne problemy. Chciałby, abyś sprawdzał jego wyniki i mówił czy przypadkiem nie zrobił błędu. Jako że Jasio jest o wiele młodszy od Ciebie, to nudzi Cię siedzenie przy nim i ciągłe poprawianie go. Dlatego postanowiłeś napisać dla niego program, który pozwoli Ci wykorzystać Twój cenny czas na coś bardziej pożytecznego i mniej nudnego dla Ciebie.
W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita
D (D ≤ 50),
oznaczająca liczbę mnożeń, które wykonał Jasio i które należy
sprawdzić.
W każdej z następnych D linii znajdą się trzy liczby
całkowite A, B, C
(1 ≤ A, B ≤ 10,
1 ≤ C ≤ 100) i oznaczają one, że Jasio
przemnożył A i B, w wyniku otrzymując liczbę C.
Dla każdego mnożenia należy wypisać pojedyncze słowo TAK lub NIE,
w zależności od tego czy wynik otrzymany przez Jasia jest prawidłowy, czy też nie.
W ostatnich badaniach archeologicznych prowadzonych w Egipcie
natrafiono na szczątki prastarej księgi z X wieku .p.n.e. Niestety
książka ta została zaszyfrowana w jakiś specjalny sposób, który
właśnie uczeni chcą odgadnąć. Według ich najnowszej hipotezy
wynika, że z każdego słowa w tekście należy wybrać symbol, który
występuje w danym słowie największą liczbę razy. Następnie
złożyć wybrane symbole i dopiero wtedy starać się odczytać
treść. Uczeni naliczyli, że różnych symboli używanych
w zaszyfrowanym tekście jest dokładnie tyle samo co liter
w alfabecie angielskim, stąd dla uproszcenia wszystkie
słowa zostaną podane do twojego programu
w postaci słowa składającego się jedynie z liter alfabetu
angielskiego.
Dla każdego słowa musisz podać literę, która w danym słowie
występuje największą liczbę razy. W przypadku gdy liter tych
jest więcej niż jedna należy wypisać je wszystkie w kolejności
alfabetycznej i sprawę do rozstrzygnięcia pozostawić uczonym.
W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita
D (D ≤ 50),
oznaczająca liczbę słów, które za chwilę pojawią się na wejściu.
W każdej z następnych D linii znajdą się jedna liczba
całkowita N (1 ≤ N ≤ 100)
oznaczająca długość danego słowa, następnie jedna spacja oraz ciąg
liter alfabetu angielskiego reprezentujący kolejne słowo.
Dla każdego słowa należy wypisać te litery, które występują
największą liczbę razy w danym słowie. Jeśli jest ich więcej
wypisz je w kolejności alfabetycznej bez rozdzielania spacjami.
W sklepach brakuje pieluch. Bajdocja jest już największym importerem smoczków, a wózki dziecięce drożeją szybciej niż mieszkania. W tempie dotąd niespotykanym rośnie nam nowe pokolenie. A wszystko to przez zarządzenia wprowadzone przez charyzmatycznego Ministra Dedukcji Bajdockiej:
XI Wiosenny Turniej w Programowaniu Zespołowym
Politechnika Poznańska, 26 V 2007
Zadanie X - Jasio
Opis
Zadanie
Zadaniem programu będzie określenie czy wynik podany przez Jasia jest prawidłowy.
Specyfikacja wejścia
Specyfikacja wyjścia
Przykład
y.html 0000644 0001300 0000144 00000005404 10625765054 011616 0 ustar contest users
Wejście
3
2 2 3
1 4 4
1 1 1
Wyjście
NIE
TAK
TAK
XI Wiosenny Turniej w Programowaniu Zespołowym
Politechnika Poznańska, 26 V 2007
Zadanie Y - Szyfr
Opis
Zadanie
Specyfikacja wejścia
Specyfikacja wyjścia
Przykład
a.html 0000644 0001300 0000144 00000000000 10626630751 011545 0 ustar contest users b.html 0000644 0001300 0000144 00000010235 10625773514 011565 0 ustar contest users
Wejście
3
4 aaaa
8 aabbabba
1 z
Wyjście
a
ab
z
XI Wiosenny Turniej w Programowaniu Zespołowym
Politechnika Poznańska, 26 V 2007
Zadanie B - Przedszkole
Opis
Chodzą także plotki, że za zgodą najwyższych władz dokonano sabotażu w fabrykach baloników na terenie całego kraju.
Na prawdziwe oblężenie szykują się przedszkola, dlatego zaczęto opracowywać już programy komputerowe wspomagające panie przedszkolanki. Jeden z nich ma pomagać w ocenie jakości słów pisanych przez dzieci w zeszytach. Pani przedszkolanka zapisuje dane słowo na tablicy, a każde z kilkuset dzieci znajdujących się na sali przepisuje je do zeszytu. Następnie, rozproszony system kamer umieszczonych w suficie przedszkola robi zdjęcia, które poddawana są dalszej obróbce. Jej wynikiem jest słowo w postaci tekstowej odczytane przez OCR. Dziecko otrzymuje ocenę proporcjonalną do tego, jak bardzo słowo odczytane przez OCR jest podobne do słowa napisanego przez panią przedszkolankę.
Reguły oceny podobieństwa słów są następujące. Jeśli słowa mają różną długość, to podobieństwo wynosi 0. Jeśli słowa mają taką samą długość, to podobieństwo słów jest równe sumie podobieństw kolejnych odpowiadających sobie literek. Jeśli literki są takie same, to ich podobieństwo wynosi 1. Jeśli literki różnią się tylko wielkością (np. "k" i "K"), to podobieństwo wynosi 0.7 (wyjątek: podobieństwo pomiędzy "t", a "T" wynosi 0.4). Ponadto, podobieństwo pomiędzy parami małych liter "w", "n", "m", "u", "r" wynosi 0.5. Podobieństwo pomiędzy parami małych liter "b", "d", "g" wynosi 0.45. Podobieństwo pomiędzy małymi "x" i "r" wynosi 0.3. Inne pary liter nie są do siebie podobne (ich podobieństwo wynosi 0).
Twoim zadaniem jest uporządkowanie dzieci zgodnie z oceną otrzymaną za napisanie danego słowa.
W pierwszym wierszu wejścia znajduje się liczba następujących testów. W pierwszym wierszu każdego testu jest słowo napisane przez przedszkolankę, składające się z liter alfabetu angielskiego. Maksymalna długość słowa wynosi 15 liter. W kolejnym wierszu jest dodatnia liczba całkowita N - liczba dzieci w klasie. Klasy nie przekraczają 1000 osób. W kolejnych N wierszach znajdują się słowa napisane przez kolejne dzieci (1-wsze, 2-gie, n-te). Słowa składają się z maksymalnie 15 liter alfabetu angielskiego. Kolejne testy są oddzielone pojedynczą pustą linią.
Wejście2 Odgrzybiacz 3 Odbrzybiacz Odgrzybiacz odgrzybiacz Ministerstwo 4 Ninisterstwo Mimisterstwo inisterstwom inisterstwoo |
Wyjście2 3 1 2 1 4 3 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie C - Trasy |
Bolek jest wiochmenem. Każdego roku, odbywa on wycieczkę rowerową pomiędzy dwoma wioskami. Jest wiele różnych tras, które może on obrać, lecz jest pewna maksymalna długość trasy, której nie chce przekroczyć. Mając dane informacje o wioskach, drogach oraz ich długościach, Bolek chciałby mieć listę różnych tras pomiędzy dwoma wybranymi wioskami, których długość nie przekracza jego możliwości, tak aby spokojnie wybrać sobie, którąś z nich. Twoim zadaniem jest napisanie programu, który wypisze listę tych tras od najkrótszej do najdłuższej.
Przyjmujemy następujące założenia:
W pierwszej linii wejścia znajduje się liczba testów D. Dalej następują opisy testów. Pierwsza linia każdego testu składa się z dwóch liczb całkowitych V i R (2 ≤ V ≤ 20, 0 ≤ R ≤ 40). V oznacza liczbę wiosek, a R liczbę dróg pomiędzy nimi. W każdym z kolejnych R wierszy znajduje się opis i-tej drogi w postaci trzech liczb Ci, Di, Oi. Pierwsze dwie oznaczają numery wiosek połączonych drogą, a Oi oznacza odległość między nimi. Wioski numerowane są od 1 do V, a 1 ≤ Oi ≤ 10000. W kolejnej linii znajdują się 2 różne liczby X i Y, oznaczające, odpowienio, numer wioski początkowej oraz numer wioski docelowej. W ostatniej linii występuje jedna liczba całkowita M (1 ≤ M ≤ 10000), oznaczająca maksymalną długość trasy, która Bolek jest gotów pokonać.
Dla każdego testu z wejścia, w oddzielnych liniach wypisz trasy spełniające wymagania Bolka poprzedzone długością danej trasy i dwukropkiem. Trasy powinny być wypisane w kolejności od najkrótszych do najdłuższych. W przypadku tras o takiej samej długości wypisz je w kolejności leksykograficznej. Wyniki kolejnych testów oddziel pustymi liniami.
W przypadku, gdy żadna trasa nie spełnia ograniczeń Bolka, wypisz słowo NIE
Wejście3 4 5 1 2 2 2 3 2 1 4 1 3 4 4 1 3 3 1 3 4 4 5 1 2 2 2 3 2 1 3 3 3 4 4 1 4 1 1 4 10 5 7 1 2 2 2 4 2 1 4 5 3 4 3 2 5 3 3 5 2 2 3 1 1 3 8 |
Wyjście3: 1 3 4: 1 2 3 1: 1 4 7: 1 3 4 8: 1 2 3 4 3: 1 2 3 7: 1 2 4 3 7: 1 2 5 3 8: 1 4 2 3 8: 1 4 3 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie D - Ulotki |
Denerwują Cię ludzie, którzy na przystankach autobusowych wręczają Ci setki głupich ulotek? Mnie też. Too bad, bo Twoim zadaniem jest napisanie programu, który pomoże firmie, dla której pracują...
W pewnym mieście zatrudniono studentów do rozdawania ulotek. Każdemu z nich został przypisany dokładnie jeden przystanek autobusowy, na którym spędza on cały dzień, rozdając ulotki spotkanym tam ludziom.
System transportowy w tym mieście jest dość specyficzny. Linie autobusowe są jednokierunkowe i każda łączy dokładnie dwa przystanki, autobusy nie zatrzymują się pomiędzy przystankami. Opłata za przejazd daną linią (tj. pomiędzy dwoma przystankami) jest określona w specjalnych tablicach. Połączenia autobusowe są rozplanowane w ten sposób, że każda trasa w dwie strony (tj. trasa, która zaczyna się i kończy na tym samym przystanku) musi przebiegać przez dworzec centralny.
Zatrudnieni studenci każdego ranka wyruszają z dworca centralnego. Każdy z nich musi dotrzeć do przydzielonego mu przystanku autobusowego. Każdy student ma przydzielony dokładnie jeden przystanek i każdy przystanek ma przydzielonego dokładnie jednego studenta. Wieczorem studenci muszą wrócić na dworzec centralny.
Twoim zadaniem jest napisanie programu, który pomoże zminimalizować sumaryczny koszt przejazdów, który firma ponosi każdego dnia, opłacając przejazdy zatrudnionych studentów.
Pierwsza linia wejścia zawiera pojedynczą liczbę, oznaczającą liczbę testów. W kolejnych liniach opisane są kolejne testy. Każdy test rozpoczyna się linią zawierającą dwie liczby całkowite A i B, (1 ≤ A,B ≤ 1000000). A jest liczbą przystanków autobusowych (licząc również dworzec centralny), a B jest liczbą linii autobusowych. W każdej z kolejnych B linii znajduje się opis jednej linii autobusowej. Linia składa się z trzech liczb - numeru przystanku początkowego, numeru przystanku docelowego i ceny biletu. Dworzec centralny ma numer 1. Ceny są dodatnimi liczbami całkowitymi. Ich suma nie przekracza 1000000000. Możesz założyć, że z każdego przystanku można dotrzeć do każdego innego.
Dla każdego testu, wypisz jedną linię, zawierającą minimalną kwotę pieniędzy potrzebną każdego dnia na przejazdy zatrudnionych studentów.
Wejście2 2 2 1 2 5 2 1 17 5 7 2 1 65 5 1 30 1 2 20 3 4 10 1 3 20 2 4 10 4 5 20 |
Wyjście22 320 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie E - Stringi |
W tym zadaniu słowo stringi odnosi się do łańcuchów DNA, a nie do części garderoby. Sorry. Zadanie jest następujące:
Mamy dane N łańcuchów DNA. Wiemy że wszystkie łańcuchy oprócz maksymalnie jednego są poprawne. Natomiast możliwe jest, iż wśród nich znajduje się jeden łańcuch zmutowany. Mutant różni się tym od łańcucha poprawnego, iż ma inną zasadowość. Aby znaleźć mutanta przeprowadzamy szereg doświadczeń. Doświadczenie polega na wrzuceniu pewnej liczby łańcuchów, którymi dysponujemy do dwóch naczyń z roztworem. Kolor naczynia będzie odzwierciedlał sumaryczną zasadowość łańcuchów DNA tam się znajdujących. Dysponując bardzo dokładnymi przyrządami pomiarowymi jesteśmy w stanie powiedzieć, który roztwór ma większą zasadowość lub stwierdzić, że oba mają identyczną zasadowość. Niestety mamy ograniczony budżet i wolno nam wykonać tylko K doświadczeń. Czy to wystarczy, aby w każdym przypadku znaleźć mutanta?
Uwaga: Każdy, kto troche zna się na biologii wie, że nie ma problemu, żeby po doświadczeniu wyjąć nasze łańcuchy DNA z roztworów. Jak ktoś nie wierzy, to niech sobie w domu sprawdzi.
W pierwszym wierszu znajduje się liczba oznaczająca liczbę następujących testów. W każdym kolejnym wierszu znajduje się opis jednego testu w postaci dwóch liczb: N, K (0 ≤ N,K ≤ 2000000000).
Dla każdego testu wypisz TAK, jeśli da się jednoznacznie stwierdzić, czy wśród naszych łańcuchów jest mutant (i jeśli tak, to czy da się go wskazać), bądź też NIE w przeciwnym wypadku.
Wejście2 4 2 3 2 |
WyjścieNIE TAK |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007 |
Zadanie F - Duchy |
Za górami, za lasami, za głębokimi jeziorami, na bardzo wysokich skałach, w bardzo starym zamczysku żyły sobie bardzo nowoczesne duchy. Każdy z nich miał swoją prywatną komnatę, w której ćwiczył sztukę perfekcyjnego straszenia zabłąkanych turystów. Duchy lubiły swoje własne towarzystwo, więc po długich godzinach ćwiczeń bardzo często odwiedzały się wzajemnie, żeby sobie poplotkować. Ponieważ jednak przechodzenie przez bardzo grube mury w solidnie zbudowanym zamku było bardzo męczące (a duchy miały już swoje lata), więc postanowiły sobie zamówić urządzenia do teleportacji. Z powodu jednak zbyt małej liczby gotówki zostawianej przez nielicznie odwiedzających zamczysko ludzi, nie starczyło im jej na zakup "tuneli teleportacyjnych" z każdej komnaty do wszystkich pozostałych. Dlatego trzeba było wybrać, które komnaty połączyć jednokierunkowym tunelem z innymi. Stało się to przyczyną wielkiej kłótni, ponieważ każdy duch miał swoje własne ulubione ścieżki pomiędzy komnatami. W końcu postanowiono, że będą losowały dwa numery komnat a i b, a następnie połączą komnatę a-tą z b-tą jednokierunkowym tunelem (którym można się teleportować z komnaty a do b). Całą operację powtarzały dopóki miały pieniądze na zakup kolejnego tunelu. Wszystko byłoby dobrze, ale po pilotażowym zainstalowaniu okazało się, ze teleportacja tak się duchom spodobała, że zamiast ćwiczyć trudną sztukę straszenia ludzi, ciągle teleportowały się w kółko z jednej komnaty do drugiej. Aby temu zapobiec postanowiono, że nie będą instalowały tuneli, które umożliwiałyby niekończące się teleportacje - konieczność "zwykłego" przechodzenia przez ściany była wystarczająco męcząca i powodowała, że duchy nie teleportowały się bez celu.
Twoim zadaniem, jako pracownika dystrybutora "tuneli teleportacyjnych" jest wskazanie, których tuneli z listy podanej przez duchy nie należy instalować.
W pierwszej linii znajduje się liczba komnat w zamku (1 ≤ K ≤ 1000). W drugiej linii znajduje się liczba wylosowanych przez duchy tuneli (1 ≤ T ≤ 300000). W następnych T liniach znajdują się kolejno wylosowane liczby a oraz b (1 ≤ a,b ≤ K).
W kolejnych liniach należy podać opis tuneli których nie należy instalować. Muszą być one wypisane w takiej samej kolejności w jakiej znajdowały się na liście dostarczonej przez duchy. Wyjście należy zakończyć linią zawierającą dwa zera odzielone spacją.
Wejście4 5 2 4 4 3 3 2 1 2 3 1 |
Wyjście3 2 3 1 0 0 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Poznań, 26 maja 2007 |
Zadanie G - Podróże pana Jana - wycieczka na wschód |
Podczas swoich ostatnich wojaży pan Jan usłyszał legendy, że na wschodzie istniała kiedyś wspaniała cywilizacja. W związku z tym, jako cel swojej następnej podróży obrał właśnie wschód. Postanowił zaplanować tak swoją podróż, aby odwiedzić jak najwięcej miast. Pan Jan ma jednak wrodzoną awersję do kierunku zachodniego, dlatego nie chce nigdy przemieszczać się w tym kierunku (zakładamy, że zachód jest w kierunku malejących x-ów). Każdego dnia pan Jan przemieszcza się z jednego miasta do drugiego. W ciągu jednego dnia nie może jednak przebyć więcej niż k kilometrów. Zaplanuj tak podróż pana Jana, aby odwiedził jak najwięcej miast pamiętając o tym, by nocleg nigdy nie odbył się dwa razy w tym samym mieście (wtedy wycieczka stałaby się nudna). Przez pojedyncze miasto może przejechać dowolną liczbę razy (ale zatrzymać się w nim na nocleg może tylko raz). Wycieczka może skończyć się w dowolnym mieście.
W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.
W pierszwej linii każdego zestawu danych będą podane 2 liczby: N (1 ≤ N ≤ 1000) określająca liczbę miast oraz k (1 ≤ k ≤ 107). W kolejnych N liniach podane są współrzędne i-tego miasta: xi, yi (0 ≤ xi, yi ≤ 108). W ostatniej linii wejścia będzie podana liczba M określająca numer miasta, z którego pan Jan chciałby rozpocząć wędrówkę (1 ≤ M ≤ N).
Dla każdego zestawu danych wypisz maksymalną liczbę miast które pan Jan może odwiedzić w ciągu jednej podróży.
Wejście2 4 1 0 0 1 0 1 1 2 0 1 5 2 0 1 2 2 3 1 2 0 2 1 1 |
Wyjście3 5 |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Poznań, 26 maja 2007 |
Zadanie H - Podróże pana Jana - podróż dookoła świata |
Jako ostatnią podróż w swoim życiu pan Jan postanowił odbyć podróż dookoła świata. Jednak jego poznańskie korzenie nie pozwalają mu na taką rorzutność, by wydać oszczędności swojego życia (niemałe zresztą) na wycieczkę. Dlatego też postanowił, że będzie korzystał tylko z tanich środków lokomocji:
Twoim zadaniem jest sprawdzenie, czy istnieje możliwość zaplanowania takiej podróży tanimi przewoźnikami. Spółki oferujące tani transport nie oferują jednak podróży w obie strony (na przykład wyjazd do kraju ogarnietego dżumą jest tanii, jednak za powrót trzeba zapłacić "odrobinę" więcej). Podróż nie musi obejmować wszystkich miejsc i może rozpoczynać się w dowolnym punkcie, ważne tylko, aby kończyła się i zaczynała w tym samym miejscu.
W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.
W pierszwej linii każdego zestawu danych będą podane 2 liczby: N (1 ≤ N ≤ 1000) określająca liczbę miejsc oraz M (0 ≤ M ≤ 3*N*(N-1)), oznaczająca liczbę oferowanych przejazdów. W kolejnych M liniach podane będą oferowane przejazdy w postaci x y s, gdzie x,y będą określały punkt początkowy oraz końcowy transportu (1 ≤ x, y ≤ N, x ≠ y) zaś s będzie jednym z ciągów znaków "TLS", "TLP", "TLL" na oznaczenie środka transportu.
Dla każdego przypadku testowego wypisać TAK, jeśli podróż można zaplanować zgodnie z zachciankami pana Jana (w szczególności, koniecznie ze zniżką!) lub NIE w przeciwnym wypadku.
Wejście3 3 3 1 2 TLS 2 3 TLP 3 1 TLL 3 6 1 2 TLS 2 3 TLP 3 1 TLL 1 2 TLP 2 3 TLL 3 1 TLS 3 3 1 2 TLL 1 3 TLL 2 3 TLL |
WyjścieNIE TAK NIE |
|
|
XI Wiosenny Turniej w Programowaniu Zespołowym Poznań, 26 maja 2007 |
Zadanie I - Podróże pana Jana - pakowanie |
Pan Jan bardzo lubi podróżować. Ostatnio zaplanował bardzo daleką podróż i ma wiele rzeczy do zabrania ze sobą. Chciałby spakować swoje rzeczy w torby, które sumarycznie kosztują jak najmniej. Sklep oferuje torby różnych typów. Torba danego typu może udźwignąć tylko określony ciężar i ma określoną cenę. Pomóż wybrać panu Janowi zestaw toreb, w które będzie mógł spakować wszystkie potrzebne rzeczy, a którego koszt będzie najmniejszy. Pan Jan może kupić dowolną liczbę toreb danego typu.
W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.
Pierwsza linia każdego zestawu zawiera liczbę N (1 ≤ N ≤ 20), określającą liczbę rzeczy, które pan Jan planuje zabrać w podróż oraz liczbę M (1 ≤ M ≤ 50), określającą liczbę różnych typów toreb. W kolejnych M liniach każdego testu będą znajdować się pary liczby wi, ci (1 ≤ wi, ci ≤ 1000) określające maksymalny udźwig oraz koszt torby danego typu. W ostatniej linii znajduje się N liczb (1 ≤ Ti ≤ 1000), określających wagę poszczególnych elementów. Udźwig co najmniej jednej torby jest niemniejszy niż waga najcięższej rzeczy (na pewno istnieje rozwiązanie).
Dla każdego zapytania wypisać minimalny koszt zestawu toreb.
Wejście3 5 2 5 10 8 20 6 1 2 5 4 5 3 3 2 6 7 10 10 4 5 5 3 2 10 1 10 6 1 7 8 10 6 4 4 3 1 5 |
Wyjście40 19 30 |
_%ЎD佳ho=6}-Nt.E q!PCM29K!ף7 :EwRmɜ]G0Rt2ƒJR ~ )?-KF,GETm{E=^2QVUC'kV\R`;E 団0Čƌ>,*cj:.{/X%3u|J5gvaK[ޏ ef!hצ?ls1AL`3:;uZcM擖U__= @u
KWʏ_| Ȉ
Jasio przyszedł na świat dokładnie sześć lat, trzy miesiące i czternaście dni temu i uczy się już w pierwszej klasie szkoły podstawowej. Teraz właśnie przyszedł czas na naukę tabliczki mnożenia, ale ma z jej nauką pewne problemy. Chciałby, abyś sprawdzał jego wyniki i mówił czy przypadkiem nie zrobił błędu. Jako że Jasio jest o wiele młodszy od Ciebie, to nudzi Cię siedzenie przy nim i ciągłe poprawianie go. Dlatego postanowiłeś napisać dla niego program, który pozwoli Ci wykorzystać Twój cenny czas na coś bardziej pożytecznego i mniej nudnego dla Ciebie.
W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita
D (D ≤ 50),
oznaczająca liczbę mnożeń, które wykonał Jasio i które należy
sprawdzić.
W każdej z następnych D linii znajdą się trzy liczby
całkowite A, B, C
(1 ≤ A, B ≤ 10,
1 ≤ C ≤ 100) i oznaczają one, że Jasio
przemnożył A i B, w wyniku otrzymując liczbę C.
Dla każdego mnożenia należy wypisać pojedyncze słowo TAK lub NIE,
w zależności od tego czy wynik otrzymany przez Jasia jest prawidłowy, czy też nie.
W ostatnich badaniach archeologicznych prowadzonych w Egipcie
natrafiono na szczątki prastarej księgi z X wieku .p.n.e. Niestety
książka ta została zaszyfrowana w jakiś specjalny sposób, który
właśnie uczeni chcą odgadnąć. Według ich najnowszej hipotezy
wynika, że z każdego słowa w tekście należy wybrać symbol, który
występuje w danym słowie największą liczbę razy. Następnie
złożyć wybrane symbole i dopiero wtedy starać się odczytać
treść. Uczeni naliczyli, że różnych symboli używanych
w zaszyfrowanym tekście jest dokładnie tyle samo co liter
w alfabecie angielskim, stąd dla uproszcenia wszystkie
słowa zostaną podane do twojego programu
w postaci słowa składającego się jedynie z liter alfabetu
angielskiego.
Dla każdego słowa musisz podać literę, która w danym słowie
występuje największą liczbę razy. W przypadku gdy liter tych
jest więcej niż jedna należy wypisać je wszystkie w kolejności
alfabetycznej i sprawę do rozstrzygnięcia pozostawić uczonym.
W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita
D (D ≤ 50),
oznaczająca liczbę słów, które za chwilę pojawią się na wejściu.
W każdej z następnych D linii znajdą się jedna liczba
całkowita N (1 ≤ N ≤ 100)
oznaczająca długość danego słowa, następnie jedna spacja oraz ciąg
liter alfabetu angielskiego reprezentujący kolejne słowo.
Dla każdego słowa należy wypisać te litery, które występują
największą liczbę razy w danym słowie. Jeśli jest ich więcej
wypisz je w kolejności alfabetycznej bez rozdzielania spacjami.
XI Wiosenny Turniej w Programowaniu Zespołowym
Politechnika Poznańska, 26 V 2007
Zadanie X - Jasio
Opis
Zadanie
Zadaniem programu będzie określenie czy wynik podany przez Jasia jest prawidłowy.
Specyfikacja wejścia
Specyfikacja wyjścia
Przykład
y.html 0000644 0001300 0000144 00000005404 10625765054 011616 0 ustar contest users
Wejście
3
2 2 3
1 4 4
1 1 1
Wyjście
NIE
TAK
TAK
XI Wiosenny Turniej w Programowaniu Zespołowym
Politechnika Poznańska, 26 V 2007
Zadanie Y - Szyfr
Opis
Zadanie
Specyfikacja wejścia
Specyfikacja wyjścia
Przykład
Wejście
3
4 aaaa
8 aabbabba
1 z
Wyjście
a
ab
z