Runda 13 - omówienie zadań

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

Runda 13 - omówienie zadań

Postautor: mario » 22 gru 2013, 16:13

Dzień dobry,

tutaj, po 20.00 pojawią się omówienia i wskazówki do zadań z tej rundy.
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 13 - omówienie zadań

Postautor: kaspro » 22 gru 2013, 20:49

Szkice rozwiązań do moich zadań będą pod adresem:
http://algorytm.edu.pl/algoliga.html
Najpóźniej jutro pojawią się wszystkie omówienia.
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 13 - omówienie zadań

Postautor: mario » 22 gru 2013, 21:54

Dobry wieczór
Dziękuję wszystkim za udział.

Karciana sztuczka
W treści zadania pojawiło się słowo "stos", ale nie było potrzeby tutaj używać tej struktury, wystarczyło cyklicznie uzupełniać w tablicy co drugą niezajętą dotąd komórkę.
Poniżej rekurencyjne rozwiązanie zadania
http://www.math.edu.pl/rozwiazanie.php?dzial=rozne&id=287
Ale dla tak dużych danych, to rozwiązanie nie zmieści się w czasie.

//-------------------------------------------------------------------------------------------

Prezenty
To zadanie jest łatwe i nie wymagające większego komentarza :)

//-------------------------------------------------------------------------------------------

Łańcuszek choinkowy
Rozwiązanie: http://www.math.edu.pl/rozwiazanie.php?dzial=rozne&id=288
Dla każdego przypadku testowego należy policzyć resztę z dzielenia przez 1000000007 liczb Fibonacciego z przesunięciem o 2.
Aby zmieścić się w limitach czasowych można wykorzystać własności przystawania lub potęgowanie macierzy.

//-------------------------------------------------------------------------------------------

Nadmiar trudu
Najprościej dla małych wartości wyznaczyć takie ciągi i wyciągnąć wnioski. Rozwiązanie jest zależne od parzystości liczby punktów widokowych.
I tak dla nieparzystej liczby punktów najdłuższa droga wynosi (n^2 +2n-2)/2, a dla parzystej liczby taka droga ma długość (n^2 +2n-1)/2.
Wyprowadzenie jednego ze wzorów: http://www.math.edu.pl/rozwiazanie.php?dzial=rozne&id=286
Aby taką drogę teraz zaplanować należy rozpocząć w przypadku nieparzystej liczby punktów w (n-2)/2, a skończyć w punkcie n/2, a dla parzystej liczby rozpocząć w (n-1)/2, a skończyć w (n+1)/2. Drogę tę możemy odbywać rozmaicie poruszając się pomiędzy dwoma podciągami, zatem pozostałe punkty przydzielamy naprzemiennie tak, aby relacja mniejszości była zachowana.

//-------------------------------------------------------------------------------------------

Szyfr matematyczny
Rozwiązanie: http://www.math.edu.pl/rozwiazanie.php?dzial=rozne&id=289
Należało zatem wyznaczyć punkty stałe i użyć reguły mnożenia dla wygenerowanych wcześniej liczb Fibonacciego.
W zadaniu trzeba także było zwrócić uwagę, że są takie przypadki wejściowe, dla których wynik przekracza 2^63, ale nie przekracza 2^64.

//-------------------------------------------------------------------------------------------

Problem ośmiu hetmanów

Potrzeba jest zapoznania się z problemem ośmiu hetmanów. Poniżej 12 rozwiązań nieuwzględniających symetrii i obrotów
http://www.math.edu.pl/rozwiazanie-hetman-8#tabela
Razem są 92 ustawienia rozwiązujące problem.
Program powinien za pomocą najmniejszej liczby ruchów doprowadzić do jednego z takich ustawień.
Można to zrobić na kilka sposobów:
- wykorzystując przeszukiwanie grafu, korzystając z rekurencji lub też przeprowadzając symulację.
Z obserwacji i zabawy na szachownicy wynika, że z dowolnego ustawienia jesteśmy w stanie osiągnąć szukane ustawienie w co najwyżej 7 ruchach. Fakt ten pozwala na optymalizację algorytmu, tzn, skoro nie mogę osiągnąć dowolnego ustawienia w 6 ruchach, to wypisz 7.

Należy także zwrócić uwagę na test, w którym piony są skupione w jednym miejscu, ponieważ przeskakiwanie jest niedozwolone, np. taki przypadek
Kod: Zaznacz cały
HHH.....
HHH.....
HH......
........
........
........
........
........

gdzie minimum wynosi 7.
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 13 - omówienie zadań

Postautor: flashion » 29 gru 2013, 23:19

Można prosić o zarys implementacji do hetmanów?
flashion
 
Posty: 8
Rejestracja: 24 lis 2013, 22:50

Re: Runda 13 - omówienie zadań

Postautor: rr_ » 31 gru 2013, 05:03

W omówieniu zadania "Liczby doskonałe" jest mały błąd.
Przy wypełnianiu tablicy tab zamiast:
tab[j] += j;
powinno być:
tab[j] += i;
rr_
 
Posty: 4
Rejestracja: 31 gru 2013, 04:56

Re: Runda 13 - omówienie zadań

Postautor: kaspro » 31 gru 2013, 22:17

Dzięki, poprawione.
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 13 - omówienie zadań

Postautor: adam_bak » 01 sty 2014, 16:54

Będą może jeszcze omówiania AL_13_07 oraz AL_13_12 za jakiś czas? ;)
adam_bak
Koordynator AlgoLigi
 
Posty: 68
Rejestracja: 20 wrz 2012, 09:44

Re: Runda 13 - omówienie zadań

Postautor: mario » 01 sty 2014, 18:36

Hetmany
W tego typu zadaniach nie ma jednego dobrego szablonu na implementację, wszystkie wysłane kody bardzo różnią się w implementacji. Ogólnie tablicę tab[92][8] należy uzupełnić wszystkimi rozwiązaniami ogólnego problemu hetmanów, można to wklepać choćby ręcznie. Dla każdego przypadku testowego należy użyć pewnego przeszukiwania, aby po skończonej, jak najmniejszej liczbie kroków osiągnąć każde z rozwiązań w tab[i], lub też odwrotnie, dla każdego rozwiązania tab[i] przeprowadzić przeszukiwanie lub symulację przypadku testowego aby osiągnąć tab[i] w minimum. Szukanie można zaimplementować na wiele sposobów, w zależności od tego kto co preferuje. Można to zrobić iteracyjnie z symulacją lub skojarzeniem, rekurencyjnie, można użyć grafu. Cała trudność w tym zadaniu polega właśnie na implementacji tej funkcji i każdy zrobi to na swój sposób.
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 13 - omówienie zadań

Postautor: kaspro » 02 sty 2014, 21:37

W ten weekend opiszę te zadania. Zmora zwana brakiem czasu mnie ostatnio bardzo prześladuje. :)
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 13 - omówienie zadań

Postautor: rozana » 29 kwie 2014, 17:33

Witam! Możesz mi przedstawić ten problem za pomocą stosu chodzi mi o sztuczną inteligencję?
rozana
 
Posty: 1
Rejestracja: 29 kwie 2014, 17:29


Wróć do Zadania

Kto jest online

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

cron