KONKURSY › Informatyczne

Potyczki algorytmiczne (XI)

Data ostatniej modyfikacji:
2016-01-22
Autor: 
Paweł Świątkowski
student informatyki i filologii fińskiej UAM w Poznaniu
Organizator: 

Wydział Matematyki, Informatyki i Mechaniki
Uniwersytetu Warszawskiego
Advanced Digital Broadcast z Zielonej Góry
Entellico z Poznania

http://potyczki.mimuw.edu.pl

 

Terminy: 

zapisy: od 1 X 2015, godz. 12:00
runda próbna - zadania zwykłe: 22-25 IX 2015
runda próbna - zadania rozproszone: 25-26 IX 2015
rundy zdalne: 28, 29, 30 IX, 1, 2 X 2015
wyniki rund zdalnych: 6 X 2015
finały: 12-13 XII 2015 Warszawa

 

Celem tego konkursu jest umożliwienie każdemu informatykowi, bez względu na wiek i wykształcenie, sprawdzenia swoich umiejętności w rozwiązywaniu problemów algorytmicznych, układaniu wydajnych algorytmów i pisaniu dobrej jakości programów. Rekordowa z dotychczasowych edycji zgromadziła około 4000 uczestników. Wśród nich znajdowali się zarówno uczniowie samodzielnie zgłębiający tajniki sztuki efektywnego programowania, jak i studenci informatyki.

Dotychczasowi zwycięzcy "Potyczek" zdobywali czołowe miejsca na tak prestiżowych zawodach, jak choćby TopCoder, Google Code Jam czy Międzynarodowa Olimpiada Informatyczna, jest to więc szansa na zmierzenie się z naprawdę najlepszymi. Mimo ostrej konkurencji konkurs jest jednak świetną zabawą dla każdego, nawet jeśli nie rozwiąże się wszystkich zadań na maksymalną liczbę punktów.

Zadania konkursowe przygotowują pracownicy i studenci Uniwersytetu Warszawskiego, niejednokrotnie laureaci poprzednich edycji. Dodatkową motywacją dla zawodników są nagrody - laptopy firmy Dell oraz oferta zatrudnienia w firmie ADB z Zielonej Góry i Entellico z Poznania.

 

Historia: 

Zawody organizowane są od 2005 roku. W VII edycji wzięło udział ponad 1300 uczestników.

 

Skrót regulaminu: 
  • W zawodach może wystartować każdy, z wyjątkiem organizatorów, jurorów i autorów zadań. Rejestracja odbywa się internetowo na stronie konkursu.
  • W sesji zdalnej każdego dnia publikowane jest od jednego do sześciu zadań w dwóch grupach - łatwiejszej i trudniejszej.
  • Rozwiązaniem zadania jest jednoplikowy kod źródłowy programu w jednym z języków C, C++, Pascal oraz Java. W każdej turze można zgłosić maksymalnie 10 rozwiązań jednego zadania. Rozwiązania oceniane są automatycznie. Jedynymi kryteriami są poprawność oraz szybkość wykonania programu.
  • Do finału kwalifikuje się 20 pierwszych osób z listy rankingowej po 6 rundach zdalnych, pod warunkiem, że dana osoba uczestniczyła w dotychczasowych finałach mniej niż dwa razy.

 

Przykładowe zadania: 

Palindromy

Mały Jasio dostał do rozwiązania trudne zadanie. Ma podaną listę słów i musi policzyć, ile z nich zawiera palindrom dłuższy niż jeden znak. Palindrom to słowo, które czytane zarówno od początku, jak i od końca, jest takie samo. Palindromem jest więc na przykład słowo  "ala". Natomiast słowo "kot" nie jest palindromem, gdyż czytane od końca brzmi inaczej: "tok". Słowo "foo" zawiera palindrom o długości większej niż jeden: jest to ciąg "oo", natomiast słowo "ftof" nie zawiera palindromu o długości co najmniej dwa.
Pojawił się pewien problem. Ponieważ Jasio nie potrafi jeszcze za dobrze czytać, nie odróżnia liter "i" i "j" oraz "p", "b" i "d". Gdy w wyrazie pojawi się litera "i" lub "j", Jasio traktuje je tak, jakby to był ten sam znak. To samo dotyczy liter "p", "b" i "d". W związku z tym Jasio uzna za palindrom również słowo "pod". Potrzebny jest program, który pomoże zweryfikować rozwiązanie, które podał mały Jasio.

Napisz program, który:

  • wczyta listę słów do przetworzenia,
  • obliczy liczbę słów na wejściu, które zawierają w sobie jakikolwiek palindrom o długości większej niż jeden znak,
  • obliczy liczbę słów na wejściu, które Jasio uznałby za zawierające jakikolwiek palindrom o długości większej niż jeden znak,
  • wypisze obie liczby.

Wejście
W pierwszym wierszu znajduje się jedna liczba naturalna n (1<n<10 000) - liczba słów do przetworzenia, następnie jest n wierszy, z których każdy zawiera dokładnie jedno słowo. Słowa składają się wyłącznie z małych liter alfabetu angielskiego. Długość żadnego słowa nie przekracza 200 znaków.

Wyjście
Program powinien wypisać dokładnie dwa wiersze, każdy zawierający jedną liczbę całkowitą. Pierwszy wiersz pierwszy powinien zawierać liczbę słów zawierających palindrom o długości co najmniej dwóch znaków, a drugi - wynik, który uzyskał mały Jasio.

 

Wielomian

Dla danego wielomianu W oraz zadanej liczby x, wyznacz trzy ostatnie cyfry (cyfrę setek, dziesiątek i jedności) wartości wyrażenia W(x).

Napisz program, który:

  • wczyta opis wielomianu W oraz liczbę x,
  • wyznaczy trzy ostatnie cyfry wartości wyrażenia W(x),
  • wypisze wynik.

Wejście
Pierwszy wiersz zawiera dwie liczby całkowite: s (1 ? s ? 20 000) oraz x (-1 000 000 ? x ? 1 000 000). Drugi wiersz zawiera s liczb całkowitych w1, w2, ..., ws (-1 000 000 ? wk ? 1 000 000) pooddzielanych pojedynczymi odstępami. Liczby te to kolejne współczynniki wielomianu: W(x) = w1xs-1 + w2xs-2 + w3xs-3 +...+ ws-2x2 + ws-1x +ws.

Wyjście
Program powinien wypisać słowo zbudowane z trzech ostatnich cyfr liczby równej wartości wyrażenia W(x), w kolejności od cyfry setek do cyfry jedności.

 

Powrót na górę strony