[ 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 Online
PostNapisane: 1 paź 2011, o 17:42 
Gość Specjalny
Avatar użytkownika

Posty: 4513
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] Algorytm dla systemu dziesietnego
1) Znajdz algortym dla (dodawanie, odejmowanie, mnozenie, dzielenie, potęgownie) dla systemu dziesietnego o dowolnej podstawie. Potrzebuję pomocy jak rozwiązać to zadanie ...
 Madeleinke  4
 [Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
Mamy dany zbiór 1-10. Program losuje jedną liczbę z tego przedziału. Zadaniem użytkownika jest odgadnąć tą liczbie przy jak najmniejszej liczbie prób. Po wytypowaniu liczby program może udzielić następujących odpowiedzi: -Odgadłeś! -Nie udało się us...
 kaki2308  8
 Algorytmy - schemat blokowy
Mam problem ze zrobieniem dwóch zadań ( z informatyki nie jestem zbyt dobra): 1) Narysuj schemat blokowy algorytmu, który zlicza sumę wszystkich liczb całkowitych z przedziału , gdzie a,b są liczbami całkowitymi podanymi na wejściu. Uwaga: musi...
 kmyszka17  1
 [Algorytmy] Zmodyfikowana metoda siecznych
Witam, czy jest ktoś w stanie mi powiedzieć jak można zmodyfikować metodę siecznych szukającą miejsc zerowych funkcji tak, aby służyła do szukania przybliżonej wartości pierwiastka kwadratowego ze znaną dokładnością? Nie mam pomysłu... Pozdrawiam....
 silk94  2
 [Algorytmy] Dwa najbardziej oddalone od siebie punkty
Mam taki problem: danych jest n punktów. Ponumerujmy je od 0 do n-1. Trzeba znaleźć taką parę punktów: (x_{i} ; \ y_{i}) oraz ...
 adambak  17
 [Algorytmy][Java] Paproć Barnsleya
Mam do napisania w javie kod do tegoż fraktala... moim problemem jest to, że za bardzo nie wiem na jakiej zasadzie ma być generowany obraz, bo z pewnością nie odbywa się to tak, jak przy Mandelbrocie... Prosiłabym o wskazówki, jak mam się do tego zab...
 Magdalena160  1
 [Algorytmy] Koszt realizacji algorytmów
Pokaż jak to liczysz. i napisz co to znaczy, że algorytm ma złożoność 2^n....
 elethorn  8
 [Sieci][Algorytmy][C#] Obliczenia na IP i masce sieci
Zadanie: Napisz aplikację umożliwiającą wczytanie adresu oraz maski podsieci. Adres oraz maska składa się z 4 pól, w których możliwe jest podanie wartości z zakresu <0-255>. Następnie w zależności od wyboru pozycji w menu, op...
 karpiq  1
 [Algorytmy] programowanie, drzewa BST AVL
Napisz algorytm uzupełnienia n-elementowej tablicy A wszystkimi liczbami ze zbioru Z=\left\{1,2,...,n \right\} tak aby startując od pustego drzewa kolejno wykonywane operacje wstawdoBST(t[i])[/i...
 matfka  0
 [Algorytmy] Odejmowanie liczb binarnych
Mam problem z takim odejmowaniem liczb w systemie dwójkowym : 1000 - 111 nie wiem co zrobić z pierwszą cyfrą gdyż nie mogę zrealizować pożyczki bo na drugiej i trzeciej pozycji są zera ....
 nwa2pac  2
 [Algorytmy] Wyprowadź stwierdzenie w logice Hoare'a
Wyprowadź stwierdzenie w logice Hoare'a następujące stwierdzenia: a) { n < 0 } while ( n != 0 ) do n := n - 2 { n = -1 } b) { x > 0 } y := x - y; x := 1 + y { y < x}[/code:1hgt7n...
 smakubaku  0
 [Algorytmy] Punkt przecięcia prostych - zadanie 8
Dokładnie z obliczeniem pkt - tzn obliczałem ,ale nigdy nie wychodzi mi taki wzór , że gdy podstawię przykładowe wejście to wyjdzie dobry wynik....
 Baridiusz  10
 [Algorytmy] Najmniejsza wspólna wielokrotność (NWW).
Proszę Was, kochani, strasznie potrzebna jest mi pomoc. Musze zrobić algorytm - Najmniejszej Wspólnej Wielokrotności w schemacie blokowym. Byłabym niezmiernie wdzięczna, gdybyście mi pomogli. Błagam ...
 karolaaaaaa  10
 [Algorytmy] schemat blokowy
Nie potrafię zrobić algorytmu iteracyjnego, a dokładniej chodzi mi o schemat blokowy, który jest iloczynem liczb spełniających te warunki: - tylko liczby parzyste - ...
 nodohx  2
 [Algorytmy] Złożoność średnia
WYSZ_SEKW(A[1..n],x) i <-- 1 A[n+1] <-- x while A[i] <> x do i <-- i+1 if i <= n then return i else return 0 Przyjmijmy, że operacjami dominującymi są oba porówna...
 midek  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com