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
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: 4621
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] Czy da się poprawić złożoność czasową?
To narazie wychodzi na to że napisałem heure ; >. Jak przyjde do domu to jeszcze pomyśle ....
 Marcinek665  16
 [Algorytmy] Wyznaczenie wartości sinusa
Oblicz przybliżoną wartość funkcji sinus dla kąta x _{r} podanego w radianach jako liczba rzeczywista. Przybliżenie wartości funkcji wyznacz na podstawie jej rozwinięcia w szereg potęgowy: \sin(x _{r} &#...
 angel10  6
 [Algorytmy]Czas działania algorytmu.
Witam, bardzo prosiłbym o przedstawienie sposobu rozwiązywania takiego zadania: Zadanie 21: Nieefektywne sortowanie Rozważmy następujący algorytm sortowania. STOOGE-SORT(A,i,j) 1 if A(i)>A(j) 2 then zm...
 lisio  2
 [Algorytmy] Przekształcenie wektora inwersji permutacji
Witam , muszę znaleźć sposób na przekształcenie wektora inwersji permutacji w orginalny ciąg przy pomocy drzewa przedziałowego. Potrzebuje jakiegoś hinta , wskazówki, zupełnie nie mam pomysłu na to . Dziękuję za wszystkie sensowne odpowiedzi ...
 Rjiuk  0
 [Algorytmy] Wzór na odległość między punktami
Witam, od dłuższego już czasu borykam się z pewnym problemem a forum to zawsze było mi pomocne i do tej pory nie miałem potrzeby się rejestrować, gdyż zawsze znajdowałem to, czego szukałem. Dziś jest jednak inaczej. Sytuacja wygląda tak, że gram so...
 G4rcU  9
 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] Średnia długość ciągu Collatza
Cóż, wyniki jednak różnią się nieco od moich, szczególnie dla potęg większych niż 7. Co jeszcze nie oznacza, że zbieżności do wzoru który zaproponowałem nie ma... Przewidywania obliczone z mojego wzoru są następujące: 9,751 25,133 41,078 57,080 73...
 matemix  4
 [Algorytmy] Suma wyrazów ciągu
Witam wszystkich forumowiczów Mam przed sobą dość ciekawe zadanie, które zafundował nam wykładowca na egzaminie. Otóż mam coś takiego: Obliczyć za pomo...
 80Wieta08  8
 [Algorytmy] Zliczenie elementów tablicy
Mam problem! Chcę znaleźć metodę na policzenie liczby elementów w tablicy, aby koszt w najgorszym przypadku był \log n. Dokładniej: w zadaniu mam posortowaną tablicę (załóżmy, że rosnąco) i np. dla tablicy o elementach: [...
 fly92  2
 [Algorytmy] Zadania Selekcja turniejowa i losowe drzewo BST
Witam, mam problem z dwoma zadaniami, prowadząca powiedziała że ich nie przyjmie bo są źle ale nie powiedziała co jest źle. Pierwsze: Przedstawiony algorytm wykorzystywany jest w turniejach ewolucyjnych do wyboru lepiej przystosowanych osobników (...
 henry900  0
 [Algorytmy] Zlicz liczby parzyte
A mógłbys zapisać w pseudojezyku?...
 kalik  8
 [C++][Algorytmy] Wojsko Napoleona - V OIG
Witam. Chciałbym, żeby ktoś wyjaśnił mi zadanie "Wojsko Napoleona" z V OIG: Wojsko szykuje się na wizytację Napoleona. Oczywiście wszyscy chcieliby wypaść jak najlepiej. Żołnierze muszą podzielić się na oddziały, które kole...
 alu675  3
 [Algorytmy] Największy indeks - minimum
Hej, mam napisać algorytm znajdującego największy indeks elementu najmniejszego. Spróbowałem go sam napisać: ALGORYTM(A[1..n],min) i<--1 i<--min min<--A[n] while i<=n do if A[i]<min ...
 midek  1
 [Algorytmy] Transformacja harmoniczna
Hej, mam algorytm na transformację harmoniczną i chciałbym się was zapytać czy dobrze rozumiem "co autor miał na myśli". Treść algorytmu: For x \in (\frac{1}{1+q}, \frac{1}{q}] where [...
 Anthil  0
 [Algorytmy] Wyznaczanie pozycji dla rysowania krzywej
Witam, mam wyznaczone pozycje dla punku: s, p0, p1, p2, k. Potrzebuję wzór do obliczenia przesunięcia punktów: p0, p1, p2. Podejrzewam, że będzie to jakaś proporcja x/y. Nowe pozycje dla punktów p0, p1, p2 muszą uwzględniać przesunięcie 5, 7 i 5. Pr...
 bert1223  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com