szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 wrz 2011, o 18:16 
Użytkownik

Posty: 17
Lokalizacja: Polska
Witam,
mam problem z następującym zadaniem http://main.edu.pl/pl/archive/proserwy/2010/mat. Kompletnie nie rozumiem rozwiązania tego zadania zawartego w oficjalnej książeczce z obozu. Jest tam napisane że należy użyć BFS do wyznaczenia wyniku jednak x może być rzędu 10^{17}. Może ktoś tutaj by opisał w łatwy sposób rozwiązanie.

Z góry dziękuje za pomoc
Góra
Mężczyzna Offline
PostNapisane: 1 paź 2011, o 12:27 
Użytkownik

Posty: 53
Lokalizacja: Skierniewice
Witam,
nie znam oficjalnego rozwiązania jednak mogę przedstawić to co wymyśliłem przed chwilą.
Oznaczmy przez a największą z liczb y. Idea rozwiązania opiera się na sprowadzeniu naszego x dzięki mniejszym materiałom wybuchowym do liczby podzielnej przez a.
Dla każdej reszty r znajdźmy takie przydzielenie materiałów o sumie równej b  \cdot  a+r, aby ich liczba użytych materiałów odjąć b była jak najmniejsza i oznaczy tą wartość w[r]. Można to zrobić lekko zmodyfikowanym bfs'em w złożoność O(ak).
Wyznaczmy również nwd wszystkich liczb y. O(k~log~a)
Sprawdzając dane x po pierwsze sprawdzamy czy x jest podzielne przez to nwd.
Jeśli nie odpowiedz brzmi oczywiście "NIE", jeśli tak odpowiedzią jest równa w[ x \% a ] + x / a (nie musimy się przy tym martwić, że przy obliczaniu naszego w[r] wartość b jest zbyt duża ponieważ x>a^2)
Reasumując całe zadanie da się zrobić w złożoności O(ak+n).
Góra
Mężczyzna Offline
PostNapisane: 1 paź 2011, o 17:42 
Gość Specjalny
Avatar użytkownika

Posty: 4608
Lokalizacja: Wrocław
satre napisał(a):
Kompletnie nie rozumiem rozwiązania tego zadania zawartego w oficjalnej książeczce z obozu.

Gdzie można taką książeczkę zdobyć?
Góra
Mężczyzna Offline
PostNapisane: 1 paź 2011, o 20:11 
Użytkownik

Posty: 17
Lokalizacja: Polska
marcin_smu napisał(a):
Jeśli nie odpowiedz brzmi oczywiście "NIE", jeśli tak odpowiedzią jest równa w[ x \% a ] + x / a

Nie wiem czy dobrze zrozumiałem ale według tego co napisałeś wynika że w rozwiązaniu optymalnym występuje zawsze x/a elementów a co jest nieprawdą kontrprzykład:
dla materiałów 10, 9, 1 i x=108 optymalnym rozwiązaniem jest 11 (9*10+2*9) a nie 18  (10*10+8*1)

Zordon napisał(a):
satre napisał(a):
Kompletnie nie rozumiem rozwiązania tego zadania zawartego w oficjalnej książeczce z obozu.

Gdzie można taką książeczkę zdobyć?

Na oficjalnej stronie obozu.
Góra
Mężczyzna Offline
PostNapisane: 2 paź 2011, o 14:52 
Użytkownik

Posty: 53
Lokalizacja: Skierniewice
Przy liczeniu danego w[r] bierzemy pod uwagę, to że możemy użyć mniej elementów a. W przykładzie, który przytoczyłeś mamy w[8]=1, dla przydzielenia dwóch materiałów o wielkości 9. 2 \cdot 9 = 1 \cdot 10+8, czyli b=1, więc ilość użytych materiałów odjąć b wynosi właśnie 1. w[8]+\lfloor \frac{108}{10} \rfloor=11.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Algorytmy] Własność stopu
Czy program: while (x < y) do if (x * 2 < y) then x := x * 2 else y := y - 1 ma własność stopu dla x oraz y typu integer spełniających warunek?:...
 smakubaku  1
 [Algorytmy] Drzewo AVL
Proszę o pomoc w następującym zadaniu: Zaproponuj algorytm badania, czy dane etykietowane drzewo binarne jest drzewem AVL. Koszt algorytmu powinien być liniowy względem liczby wierzchołków w drzewie....
 fly92  2
 [Algorytmy] Skrzaty z OIG VI
Czy podpowie ktoś jak rozwiązać poprawnie zadanie Skrzaty z VI Oig? Zadanie dostępne na: MAIN Na razie z tego co widzę przyda się przeszukiwanie grafu wszerz, i będzie s...
 mwl4  0
 Algorytmy problem kolejny
Hej Wam Mam takie śmieszne zadanko i nie wiem jak zwykle jak je zagryźć Dana ...
 gizmo1985  10
 [Algorytmy] Metoda iteracji prostejukład sprzeczny - zadanie 2
Witam. Mam takie pytanie. Czy istnieje jakaś możliwość sprawdzenia czy układ N równań liniowych z N niewiadomymi jest nieoznaczony albo sprzeczny? Oprócz liczenia wyznacznika, bo jeśli wyznacznik jest różny od zera to układ ma jedno rozwiązanie, w pr...
 lovesensation  1
 [Algorytmy] Cykle hamiltona w grafie skierowanym
Tyle wiem, tylko jak to zapisać ; )...
 MathNoob  2
 [Algorytmy] Przekształcanie drzewa binarnego w kopiec
Witam! W jaki sposób możemy przekształcić dane drzewo binarne w kopiec ? Oczywiście nie możemy zmienić kształtu drzewa....
 matinf  0
 [Algorytmy] Poprawność semantyczna - Fibonacci
Witam. Zrobiłam częściowo zadanie o poprawności semantycznej n-tego ciągu Fibonacciego. Wygląda ono następująco: algorytm: fibonacci (int n) { int fibb=0; int i =2; int w0=0; int w1=1; int n; if ( n==0 ) { fib...
 Modery  0
 [Algorytmy][C] Kolorowanie krawędzi grafu
2. Dany jest skończony graf niezorientowany. Zaproponuj algorytm kolorowania krawędzi tego grafu, w taki sposób, by krawędzie incydentne miały przyporządkowane różne kolory. Zastosuj metodę zachłanną konstrukcji algorytmu i postaraj się aby algorytm ...
 adams1604  0
 [Algorytmy] Znajdowanie par liczb
Witajcie, mam takie zdanie, jak sobie z nim poradzic? Zaproponuj algorytm, który dla danego ciągu A_1,...,A_n różnych liczb naturalnych i danej liczby x, drukuje wszystkie pary liczb [tex:1w52...
 malwina18  1
 [Algorytmy] Sortowanie przez wstawianie - przykład - zadanie 2
Rozważmy następujący ciąg liczb całkowitych: 10 3 7 2 1 71 9. Opisać poszczególne kroki (wraz z rezultatami) algorytmu sortowania przez wstawianie (INSERTION-SORT), zastosowanego do powyższego ciągu. Bardzo proszę o pomoc...
 Teano  1
 Algorytmy - wczytywanie liczb i pętle
Witam , mam za zadanie przedstawić algorytm : Przedstaw algorytm programu, który wczytuje liczby całkowite dopóki: A)ich suma nie przekroczy wartości 21. Bez względu na wartość sumy należy jednak wczytać przynajmniej trzy l...
 anika91  1
 [Algorytmy] Algorytm rozwiązywania sudoku.
Witam, Piszę właśnie projekt na zaliczenie z programowania mobilnego, który rozwiązuje sudoku. Napisałem sobie własny algorytm, który działa, ale na słabszych telefonach te najtrudniejsze sudoku rozwiązuje kilkanaście sekund, to mnie trochę denerwuj...
 matma17  0
 [Algorytmy] Całkowanie w Pascalu
Witam! Czy ktoś mógłby mnie naprowadzic na rozwiązanie, dac podpowiedz, bo mam do napisania program w Pascalu obliczający dwie całki z dwóch różnych funkcji liniowych. Napisałam program obliczjący 1 całkę z 1 funkcji liniowej, ale jak mam napisac pro...
 KatrinxDDD  1
 [Algorytmy][Grafy] Liczby Ramseya R(3,3)
Hejka! Muszę napisać program w c++ który dla podanej liczby osób n = 4, 5, 6, 7 ... sprawdzi czy wśród tych n osób znajdą się takie 3 osoby że każda z każdą się znają lub żadna nie zna żadnej. Znalazłam na wikipedi, że chodzi tu o liczby ramseya dla...
 asiunia92  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com