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
Instytut Matematyczny, Uniwersytet Wrocławski
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: 4837
Lokalizacja: Lozanna
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] Kodowanie - metoda drzewa - zadanie 4
http://imageshack.com/a/img31/8411/zxas.jpg Jest jakiś algorytm, że musimy właśnie tworzyć to drzewo ?? k_{c}= \log _{2} \frac{1}{ \frac{1}{4} }= \log _{2}4=2 k_{e}= ...
 rafals  0
 [Algorytmy] Złożoność obliczeniowa - zadanie 5
Witam proszę o pomoc z zadaniem: Co dla programisty szukającego algorytmu dla rozwiązania problemu P oznacza: a) \Omega(n) < O(n) b) \Omega(n) = O(n) ...
 damian8m  0
 [Algorytmy] Sortowanie Quicksort
Witam czy ktoś może mi pomóc z posortowaniem ciągu ZADQSBCA. Ostatni wyraz ciągu (A) to mój element osiowy dochodzę do tego momentu AADQSBCZ i nie wiem jak podzielić ten ciąg czy AA i DQSBCZ czy może A i ADQSBCZ. proszę o szybką odpowiedz i z góry dz...
 abladi  1
 [Algorytmy] Znajdź najdłuższy ciąg kolejnych rzutów monetą
Bardzo proszę o pomoc w rozwiązaniu tego zadania. Kompletnie nie czaję rachunku prawdopodobieństwa z czego wynikają moje problemy z zadaniem ;/ Treść: Dany jest ciąg orłów i reszek (kolejne rzuty monetą). Należy napisać algorytm, który sprawdzi, jaki...
 karzatyna  1
 [Algorytmy] Metoda Monte Carlo - objętości brył
Witam, Muszę napisać program do obliczania objętości dwóch wybranych brył metodą Monte Carlo. Po kilku godzinach poszukiwań w necie i wskazówkach mojego prowadzącego mam plan programu. Najpierw objętość kuli 1. Użytkownik podaje promień kuli r (prz...
 vip100  0
 [Algorytmy] Algorytm rekurencyjny - wartość dla argumentu
Rozważmy następujący algorytm rekurencyjny: ZROB-TO-SAM(n) if n < 1 then return 0 else return ZROB-TO-SAM(n-2)*(n+1) Jaką wartość zwróci instrukcja ZROB-TO-SAM(12)? Odpowiedź uzasadnić. Uwaga: wszystkie zmienne są li...
 fart411  1
 [Algorytmy] Zbadanie właściwości funkcji - zadanie 3
Proszę o pomoc, zupełnie nie wiem jak się do tego zabrać, zad muszę oddać do poniedziałku. Zadanie Sformułowanie problemu Dana jest funkcja f ze zbioru A w zbiór B[/tex:2pxpdga...
 anka0501  2
 [Algorytmy] Wypisać potęgi liczby 2
Tu zapewne chodzi o potęgi całkowite nieujemne, więc najpierw sprawdzasz warunek N \ge 1 i potem w pętli dla k=0,1,2,... jeśli k<\log _{2}N to piszesz [tex:e6ct...
 robertos18  2
 [Algorytmy] Obliczanie miejsc zerowych - algorytm genetyczny
Witam, mam na zaliczenie zrobić projekt zatytułowany 'Obliczanie miejsc zerowych funkcji wielu zmiennych algorytmami genetycznymi' Mógłby mi ktoś podsunąć jakieś ...
 wawek91  0
 [Algorytmy] Drzewo decyzyjne
Hej. Mam narysować drzewo decyzyjne dla różnych algorytmów oraz dla ciągu złożonego z trzech elementów . Czy jest ktoś, kto zna się na tym? Niech będzie quick sort. Widziałem już w google drzewo decyzyjne s...
 midek  0
 [Algorytmy] Pochodna cząstkowa obrazka, stereo matching
W algorytmie Stereo Matching (http://xurl.pl/stereo-matching) napokałem na konieczność liczenia pochodnej cząstkowej obrazka po osi poziomej X. Ale do liczenia pochodne...
 Borneq  0
 [Algorytmy] Nieosiągalna liczba
Mam do rozwiązania bardzo ciekawy problem, lecz nie mogę wymyślić nic lepszego jak metoda siłowa, która zważywszy na wielkość danych wejściowych, odpada.. Wejście: Liczba testów t<=1000. Dla każdego testu: liczba [tex...
 adambak  3
 [C][Algorytmy] Sortowanie bąbelkowe. Optymalizacja
Witam, ma ktoś pomysł jak przyspieszyć działanie programu? Zadaniem jest posortowanie kilku zestawów liczb. Należy użyc sortowania bąbelkowego. #include <stdio.h> int main () { int tab[100001]; int z,o,k,i,j; int ...
 Lucjan  1
 [Algorytmy] Wyszukiwanie maksimum - zadanie 2
Wczytać ciąg n liczb rzeczywistych i znaleźć element największy. Jak będzie wyglądał schemat blokowy z wykorzystaniem dwóch warunków interacyjnych dopóki? Byłbym wdzięczny za pomoc...
 kalik  5
 [Algorytmy] Obliczenie metodą najmniejszych kwadratów
Witam Mam pewien problem z pewnym zadaniem : Metodą najmniejszych kwadratów dokonaj aproksymacji punktów \left( 0.5,1.54221 \right) \\ \left( 1.5,0.776145 \right) \\ \left( 2.5,0.225604 \right) \\ \left( 3...
 km123nat  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com