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][C] Etykiety drzewa BST
Zaproponuj algorytm, który bada czy dany skończony ciąg, o elementach należących do pewnego zbioru liniowo uporządkowanego Et, może być ciągiem etykiet drzewa BST zapisanych w porządku preorder i jeśli jest to możliwe, tworzy takie drzewo BST. Ro...
 adams1604  6
 [Algorytmy] Znajdowanie najdłuższej drogi w grafie.
Czy może ktoś zna takie algorytmy (znajdowania najdłuższej ścieżki w grafie). Jest to jeden z problemów w informatyce, ale są aproksymacyjne algorytmy, które rozwiązują ten problem. Proszę o wymienianie nazw algorytmów, bądź opisanie znanej metody....
 lukaszokaj  4
 [Algorytmy] Liczba punktów wspólnych okręgów - funkcja
chodzi mi o napisanie algorytmu do tego zadania...
 mistrz23  7
 [Algorytmy] Podaj algorytm, narysuj schemat blokowy
proszę o pomoc w rozwiązaniu następujących zadań, ja jestem w tym 'zielona" a musze miec podstawy do nauki Zad.1. a) Dla danego n-elementowego zbioru liczboweg...
 klaudekk  2
 [Algorytmy] Koszt czasowy, czas rozwiązywania zadania
Mam takie zadanko do zrobienia 1.Niech A będzie algorytmem o koszcie czasowym T(A,n)= \frac{2n}{3}. Jeśli A wykonuje na komputerze K[/tex:3...
 marcinek118  1
 [Algorytmy] Najbliższy mniejszy element
Witam! Proszę o pomoc w następującym zadaniu. Dany ciąg A_1, A_2, \ldots ,A_n. Znaleźć metodę, która wyznaczy pozycję najbliższego z lewej elementu mniejszego od A_i. Chcę poznać Wasze pomysł...
 fly92  4
 Algorytmy sortowania
Szukam, szukam i nie znajduje, dlatego pytam: Jaka zlozonosc pamieciowa i jaka zlozonosc czasowa ma algorytm sortowania przez wstawianie z wyszukiwaniem binarnym. Dzieki z gory. Licze na szybka odpowiedz Pozdrawiam, Piotrek...
 Anonymous  0
 [Algorytmy][C++] Warcaby czlowiek-komputer
jeśli używasz funkcji ale nie używasz klas to de facto nie używasz obiektowości tylko stawiasz na programowanie proceduralne. Więc zamiana na obiektowe będzie w sumie polegała na pisaniu od zera. Co do kodu komputera to proste, po wykonaniu ruchu gra...
 dav123  8
 Algorytmy i struktury danych - zadanie 2
Przepraszam, być może nie jest to odpowiedni dział, ale nie mogłem znaleźć nic lepszego.. Mam sobie takie wyrażenie: \sqrt{n + 10} = \Theta \sqrt{n} Muszę podać c_{1}, c_{2} oraz [tex:21b...
 fro  4
 [Algorytmy] Algorytm KMP
Witam Mam do Was pytanie odnośnie tablicy p W algorytmie KMP http://iair.mchtr.pw.edu.pl/~bputz/aisd ... 5/main.htm Dlaczego w ta...
 Rastaman697  1
 [Algorytmy] Oblicz n-tą potęgę liczby 2
Napisałem to w C++, mam nadzieję, że się przyda. Przerobienie na schemat blokowy nie powinno Ci sprawić problemów. #include <iostream> // nie ...
 Jendriu  4
 [Algorytmy] Systemy kanoniczne, wydawanie reszty
Witam. Wiadomo, że algorytm zachłanny nie zawsze daje optymalny wynik w problemie wydawania reszty, jednak istnieją systemy monetarne, zwane kanonicznymi, w którym postępowanie zachłanne zawsze da optymalny wynik (np. dobór nominałów taki, jaki mamy ...
 patry93  1
 [Algorytmy][Rekurencja] Wzór rekurencyjny i jawny
Witam potrzebuję pomocy w rozwiązaniu zadania: Napisac wzór rekurencyjny liczby kroków działania nastepującego algorytmu, gdzie zakładamy, że operacją dominujacą jest operacja print. Metodą funkcji tworzących znaleźć wzór jawny. def ...
 Sourcerer  1
 [Algorytmy] Podróżnik - VI OIG - zadanie 2
UWAGA UWAGA-JEŚLI NIE ROZWIĄZAŁEŚ JESZCZE TEGO ZADANIA I CHCESZ NAD NIM W PRZYSZŁOŚCI POMYŚLEĆ-NIE CZYTAJ TEGO POSTA. MOŻE ZAWIERAĆ ON POPRAWNE ROZWIĄZANIE. Witam!! Mam problem z zadaniem podróżnik z ...
 janek880  0
 [Algorytmy] Złożoność czasowa - definicja
Złożoność czasowa - określa ilość czasu, którą potrzebuje algorytm na rozwiązanie problemu. Napisałem tak na egzaminie. Niestety profesor, powiedział, że jeżeli tak napisałem nie powinienem być w ogóle informatykiem i nie uznał mi tego pojęcia co z...
 Quaerens  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com