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: 4875
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 
 Schemat Hornera I Algorytmy Iteracyjne
Witam. Mam pewien problem związany z schematem Hornera. Bowiem przerabiamy na lekcji algorytmy iteracyjne, co jest mi zupełnie obce. Nie byłoby mnie tutaj, gdyby nauczyciel umiał to dobrze wytłumaczyć - ale mniejsza z tym. Dokładnie chodzi mi o alg...
 dominus21  1
 [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] struktura danych + operacje na parach
Witam, Zaprojektować s. danych, w której wszystkie operacje można wykonać w czasie O \left( \log \left( n \right) \right). \textbf{init} \left( S \right) ; [tex:2z8r...
 matematyka464  11
 [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 itp..
Znowu coś łatwego, znowu macie powód by uważać, że jestem głupia. Trudno;) Pewnie będzie to dla was łatwe;) Więc jakby ktoś mi napisał: 1.4 przykłady algorytmu. 2.Jakie znasz działania niealgorytmiczne.? 3.Jaki musi być algorytm (opis) 4.Co to jest i...
 joas_ia  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
 Potrzebne algorytmy do wyznaczania pochodnych i całek.
Zna może ktoś jakieś działające algorytmy które potrafią wyznaczać pochodne albo całki funkcji? Program wyznaczający pochodną ma dostać ciąg znaków, np. taki: "sin(a)/cos(a)" i ma zwrócić jako wynik taki ciąg: "1/((cos(a))^2)". An...
 barytek  7
 [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
 [Algorytmy] Dobieranie argumentów funkcji zależnie od kąta
Otóż załóżmy, że mamy pewną liczbę funkcji, które wyznacza drogę poruszającym się obiektom. Pytanie jest, jak dobierać argument x dla funkcji, tak aby obiekty poruszały się z taką samą szybkością?...
 edaro  2
 [Algorytmy] Sumowanie nieparzystych kolumn, parzystych wiers
W pseudojęzyku można to tak zrobić: suma = 0; for i:=1 to m do step 2 for j:=2 to n do step 2 suma := suma + A[i,j] (zależy też trochę, który indeks traktujesz jako wiersz, a który jako kolumnę)...
 kobi55  14
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com