[ 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: 4578
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] 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
 [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
 Algorytmy - pseudokod
Mam tutaj kilka przykładowych algorytmów zapisanych w pseudokodzie (nie mojego autorstwa), pytanie jest nastepujące... co oznacza L ? Pr...
 spec_u  2
 [Algorytmy] Interpolacja Lagrange'a na węzłach Czebyszewa - zadanie 2
Szukam algorytmu lub pseudo kodu bo mam problem z węzłami czybyszewa...
 przemo255  1
 [Algorytmy] Algorytm Boyera-Moore'a - tablica 'BMNext'
Witam. Mam problem ze zrozumieniem części artykułu: http://edu.i-lo.tarnow.pl/inf/alg/001_search/0050.php#tw_bmnext Pod pierwszą tabelką-przykładem jest opisany wzór, którym tworzy się tablicę BMNext...
 patry93  0
 [Algorytmy][PHP] Dopasowanie mnożnika do danych
Witam. Właśnie tworzę managera piłkarskiego. Zatrzymałem się na ustalaniu wartości graczy. Chodzi o wzrastanie wartości w zł wraz ze wzrastaniem umiejętności. To ma wzrastać w taki sposób, że 60 um to 0,4[/t...
 pawlo1334  1
 [Algorytmy] Wylączanie czynnika spod pierwiastka
Witam, czy mógłby ktoś zaproponować w pseudokodzie, algorytm wyciągania liczby z pod pierwiastka.. Mianowicie np : mam wyrażenie \sqrt{18}, chce uzyskać odpowiedz w stylu 3 \cdot \sqrt{2} ......
 mario5046  1
 [Algorytmy] Liczby Stirlinga
Witam , szukam algorytmu kombinatorycznego liczb stirlinga, napisałem już algorytm liczby stirlinga II rodzaju (proszę o sprawdzenie poprawności) 1. Mamy n liczb 2. Stwórz tablicę T[b] , która ma n elementów....
 wojtekjaskula  2
 [Algorytmy] Dowód poprawności algorytmu.
Jak dowieść poprawność poniższego algorytmu metodą niezmienników? Z góry dziękuję za pomoc. i = 1; s = 1; while(i<=n) { s = s * i; i++; }...
 peterek  1
 [Algorytmy] Wypisz liczbe par
Witam, Potrzebuje koncepcji na wyznaczanie liczby par nieuporzadkowanych w zbiorze, tak ze: mamy zbior np 5, 3, 4, 2, 1,6, wiec pary nieuporzadkowane to (5, 3), (5,4), (5,2), (5,1...
 paewel  4
 [algorytmy], liczba pierwsza
b) Sito Eratostenesa, opisane na początku zadania, służy do wyznaczania wszystkich liczb pierwszych z zadanego przedziału . Podaj w wybranej przez siebie notacji (lista kroków, schemat blokowy lub język programowania) inny algorytm, który spr...
 kejkun7  4
 [Algorytmy] N-ty wyraz ciągu
Michał rozłożył sieć n- routerów w jednej linii. Po jakimś czasie zauważył ciekawą prawidłowość: do pierwszego routera był podłączony jeden komputer, do dwóch kolejnych po dwa komputery, do trzech następnych po 3 komputery, itd. Ile komputerów było p...
 panczo12d  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com