Runda 16 - omówienie zadań

Tutaj możesz uzyskać pomoc w rozwiązywaniu zadań dostępnych w ramach AlgoLigi

Runda 16 - omówienie zadań

Postautor: witman » 28 maja 2014, 16:28

1. Jasia problemy z zegarem http://www.spoj.com/ALGOLIGA/problems/AL_16_01/
Potrzebna wiedza: elementarna arytmetyka

Jak okazało się podczas konkursu, to zadanie można rozwiązać na wiele sposobów (symulacja ruchu wskazówek, zliczanie wcześniej wygenerowanych wartości). Najprościej jest jednak, gdy zauważy się, że wskazówki zegara pokrywają się w regularnych odstępach 11 razy w ciągu 12 godzin. Można więc łatwo obliczyć ile razy taka sytuacja występuje od godziny 00:00 do danej minuty m. Oczywiście trzeba uwzględnić pewne szczególne przypadki.


2. Enigma w wersji light po raz kolejny http://www.spoj.com/ALGOLIGA/problems/AL_16_02/
Prosty szyfr przestawieniowy. Nic więcej nie napiszę.


3. Liczby własne http://www.spoj.com/ALGOLIGA/problems/AL_16_03/
Potrzebna wiedza: Arytmetyka

Zauważmy najpierw, że maksymalna różnica pomiędzy liczbą własną a jej generatorem może wynosić 9*n, gdzie n to liczba cyfr generatora złożonego z samych dziewiątek. Dla danego zakresu [a,b] wystarczy więc wyznaczyć pewną wartość p, od której generator liczby a nie może być mniejszy i rozpocząć od niej generowanie liczb własnych. Uzyskane liczby własne odnotowujemy w tablicy. Zakładając dla uproszczenia, że wszystkie liczby z badanego zakresu, mają tyle samo cyfr (przyjmijmy d), każdorazowe obliczanie sumy cyfr kolejnych generatorów da algorytm o złożoności O(d*(a–b)). Aby zmniejszyć złożoność trzeba zauważyć, że jeśli mamy obliczoną sumę cyfr liczby n, to sumę cyfr liczby n+1 można obliczyć szybciej. Wystarczy określić iloma zerami kończy się ta kolejna liczba, i poprzednią sumę cyfr zmniejszyć o 9*liczba_zer_końcowych oraz zwiększyć o 1. Takie podejście da złożoność niezależną od długości badanych liczb wynoszącą O(1.(1)*(a–b)). Limity czasowe w zadaniu są jednak tak dobrane, że można je zaliczyć, jeśli będziemy sumę cyfr obliczać od nowa tylko dla liczb kończących się zerem, a w pozostałych przypadkach do poprzedniej sumy będziemy dodawać 1.


4. Trzy posągi króla http://www.spoj.com/ALGOLIGA/problems/AL_16_04/
Potrzebna wiedza: symbol Newtona, arytmetyka modularna, zasada włączeń i wyłączeń

Potraktujmy skrzyżowania jako punkty w prostokątnym układzie współrzędnych. Z punktu (0,0) do punktu (x,y) można dojść na Newton(x+y,x)=Newton(x+y,y) sposobów. Ułóżmy trzy wyróżnione posągami skrzyżowania według rosnącej wartości x i oznaczmy (x1,y1), (x2,y2), (x3,y3). Spacer przez pierwsze skrzyżowanie można odbyć na Newton(x1+y1,x1) * Newton(N-x1+M-y1,N-x1) sposobów (oznaczmy to jako spacer(1) ). Analogicznie można obliczyć liczbę spacerów, w których przejdziemy przez jedno z dwóch pozostałych skrzyżowań, a podobnie liczbę spacerów przez dwa lub trzy skrzyżowania. Stosując zasadę włączeń i wyłączeń można znaleźć rozwiązanie obliczając: spacer(1)+spacer(2)+spacer(3)-spacer(1,2)-spacer(2,3)-spacer(1,3)+spacer(1,2,3).
Do szybkiego obliczania symbolu Newtona, należy wstępnie obliczyć wartości silni z potrzebnego zakresu oraz ich odwrotności. Oczywiście wszystkie obliczenia wykonujemy modulo 1000000007.


5. Zagubiony w czasie http://www.spoj.com/ALGOLIGA/problems/AL_16_05/
Potrzebna wiedza: algorytm zamiatania

Na podstawie informacji o skokach wykonanych przez Franka możemy wyznaczyć odcinki czasu, w których Franek żył sobie spokojnie nie wykonując skoków. Zapisujemy w tablicy zdarzenia, którymi są początki i końce tych odcinków, a następnie sortujemy tę tablicę rosnąco. W następny etapie przeglądamy po kolei te zdarzenia i jeśli trafimy na początek odcinka, to wrzucamy go do pewnego zbioru, a jeśli na koniec, to go z tego zbioru usuwamy. W wymienionym zbiorze powinniśmy odcinki przechowywać uporządkowane wg wieku Franka. Zawsze gdy dodajemy odcinek do zbioru, porównujemy go z dwoma sąsiednimi (aby znaleźć minimalną różnicę) oraz obliczamy różnicę pomiędzy skrajnymi odcinkami (aby znaleźć maksymalną).


6. Znaki dymne http://www.spoj.com/ALGOLIGA/problems/AL_16_06/
Potrzebna wiedza: algorytm Dijkstry, twierdzenie cosinusów, arytmetyka zmiennoprzecinkowa

Budujemy graf, w którym wioski są wierzchołkami, a waga krawędzi to czas przekazania wiadomości. Z uwagi na to, że posłańcem można przekazać wiadomość pomiędzy dwiema dowolnymi wioskami, mamy graf pełny. Jeśli z jakiejś wioski do innej można przesłać informację znakami dymnymi, mamy dodatkową krawędź skierowaną. Dla każdego zapytania uruchamiamy algorytm Dijkstry wyszukiwania najkrótszej ścieżki. Graf jest bardzo gęsty, dlatego nie warto implementować kolejki priorytetowej. Lepiej “naiwnie” sprawdzać odległość do pozostałych wierzchołków ,wybierając najmniejszą.
Ponieważ współrzędne wiosek podane są prawie we współrzędnych biegunowych, do obliczania odległości najlepiej wykorzystać twierdzenie cosinusów. Trzeba mieć też na uwadze niedokładność obliczeń zmiennoprzecinkowych i uwzględnić to przy liczeniu wagi krawędzi oraz przy sprawdzaniu, czy jakaś wioska leży w zasięgu znaków dymnych.


7. Kwadratura działek http://www.spoj.com/ALGOLIGA/problems/AL_16_07/
Potrzebna wiedza: algorytm obliczania pierwiastka kwadratowego, arytmetyka dużych liczb

W językach, w których jest gotowa funkcja obliczania pierwiastka kwadratowego z dużych liczb zadanie jest trywialne.
W językach, w których są “bignumy”, ale nie ma funkcji wyznaczającej pierwiastek, wystarczy zaimplemetować jeden ze znanych algorytmów: http://pl.wikipedia.org/wiki/Metody_obl ... adratowego
W językach, w których nie ma “bignumów” jest najtrudniej, bo trzeba przede wszystkim zaimplementować wykonywanie na dużych liczbach kilku podstawowych operacji arytmetycznych.


8. Gra w wieże po raz drugi http://www.spoj.com/ALGOLIGA/problems/AL_16_08/
Potrzebna wiedza: strategia gry Red-Blue Hackenbush

Problem można sprowadzić do gry w uproszczoną wersję Czerwono-niebieskiego Hackenbusha, w której występują tylko “łodygi”. Wystarczy, dla każdej wieży obliczyć jej wartość, a następnie zsumować otrzymane wyniki. Na podstawie tak obliczonej wartości gry można stwierdzić, kto wygra. W szczególności, gdy wartość gry wynosi zero, rozpoczynający przegrywa. O obliczaniu potrzebnych wartości można przeczytać tu w rozdziale 11.1


9. Finał ligi mistrzów http://www.spoj.com/ALGOLIGA/problems/AL_16_09/
Potrzebna wiedza: prawdopodobieństwo całkowite

Można rekurencyjnie wyznaczać prawdopodobieństwa wszystkich możliwych nieremisowych wyników i sumować je. Jeśli komuś tak wygodniej, może obliczyć prawdopodobieństwo remisów i odjąć od jedynki.
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Google [Bot] i 1 gość

cron