szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 wrz 2011, o 17: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 11: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 16:42 
Gość Specjalny
Avatar użytkownika

Posty: 4674
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 19: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 13: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 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
 Algorytmy - zadanie 2
przykladowe dane ,jekie chcemy przechowywac dla klientow maja postac 2007 ...
 dark1309@o2.pl  2
 [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] Zbieranie monet po drodze
Cześć, chciałbym rozwiązać następujący problem: mamy prostokątną planszę o wysokości h i szerokości w, składa się z w*h pól, na niektórych polach są monety, startujemy z lewego górnego rogu i kończymy na prawym dolnym. Można poruszać się tylko w pra...
 calmosc  3
 [Algorytmy] Suma zbiorów jako BST
Mam problem z takim zadaniem: Dane są dwa zbiory A i B, reprezentowane jako drzewa binarnych poszukiwań. Zaproponuj algorytm, który znajduje sumę tych zbiorów w postaci drzewa BST. Koszt algorytmu powinien być liniowy względem liczby elementów w dan...
 piter1389  5
 [Algorytmy] Graf skierowany - wszystkie drogi
Witam, Mam graf skierowany, acykliczny i planarny. W jaki sposób mogę policzyć wszystkie drogi z wierzchołka s do wierzchołka v? Nic mi do głowy nie przychodzi....
 matinf  13
 [Algorytmy] Wypisywanie kombinacji
Witam, ze zbioru 6 elementów np. A, B, C, D, E, F muszę wypisać wszystkie kombinacje trzy elementowe ABC, ACD itd. z tym, że kombinacja ABC = CBA itd. Macie jakieś pomysły jak to zrobić? Pozdrawiam...
 lodilirian  3
 [Algorytmy] Bankiet - zadanie z OIG I
Witam wszystkich matematyków Od jakiegoś czasu siedzę sobie nad takim jednym zadankiem z 2 etapu I Olimpiady Informatycznej Gimnazjalistów. Oczywiście Olimpiada ta...
 spammer  3
 [Algorytmy] Niezmiennik petli - zadanie 3
Niech n \ge 0 bedzie liczba calkowita. Podaj najsilniejszy warunek, ktory jest niezmiennikiem ponizszej petli. 1: x \leftarrow 0 2: y \leftarrow 0 3: While [tex...
 valverde12345  0
 [Algorytmy] schematy blokowe
Witam! Otóż dopiero zaczynamy schematy blokowe, a już dostaliśmy zadanie. Próbowałem je jakoś rozwiązać, lecz nic mi nie wychodzi. Mam nadzieje, że może Wy mi pomożecie. Przedstaw algorytm w postaci schematu blokowego - wprowadza N liczb - jako wyni...
 krzychurra24  8
 [Algorytmy] Rzędy funkcji
Mam takie zadanie do zrobienia 1.Jakiego rzędu będzie funkcja h(n)=g(n), jeżeli f(n)=\Theta (n ^{2}) a g(n)=\Theta (n ^{2} +\log n&#...
 marcinek118  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com