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
Instytut Matematyczny, Uniwersytet Wrocławski
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: 4796
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] BST, sprawdzanie permutacji
Witam Mam jakieś dowolne słowo z którego tworzę drzewo BST. Jak najszybciej sprawdzić które z permutacji danego słowa tworzy identyczne drzewo BST? Można np tworzyć drzewo i porównywać wyjście z inorder ale to raczej czasochłonne dla większego wej...
 mCichy13  0
 [Algorytmy] Znajdowanie najbliższego mniejszego elementu
Proszę o pomoc w rozwiazaniu zadania i wyjaśnienie krok po kroku tego rozwiązania. ...
 diana20  6
 [Algorytmy] Po ilu iteracjach liczby się powtórzą
witam mam problem z obliczeniem lub znalezieniem miejsca w ktorym liczby sie zaczna powtarzac otoz chodzi o gre w ktorej losuje sie liczby od 0-5 (czyli 0,1,2,3,4,5) zaczalem spisywac wystepuj...
 Diabolo89  7
 [Algorytmy] Operacje na listach
Mam takie zadanie: Z listy liczb naturalnych usuń te, które nie są sumą kilku bezpośrednich swoich poprzedników. Generalnie rozwiązanie kwadratowe jest robialne: wystarczy odwrócić listę (co robi się w czasie liniowym) i sprawdzać dla każdego eleme...
 errryk  1
 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] Niezmiennik pętli.
Witam mam do zrobienia zadanie którego treść jest następująca : Ustal jakie jest działanie poniższej funkcji. Następnie sformułuj niezmiennik pętli, który pomoże uzasadnić Twoją odpowiedź int maxS(int n, int a[]) { int ms...
 itus9991  5
 [Metody numeryczne] Materiały do nauki metod numerycznych
Witam. Czy moglibyście mi polecić jakieś dobre książki do nauki metod numerycznych od podstaw? Posiadam już "Metody numeryczne" Z. Fortuny, B. Macukowa i J. Wąsowskiego oraz "Metody numeryczne" G. Dahlquista i A. Bjorcka, jednak ...
 rotasal  3
 [Algorytmy] Wzbogacenie słownika o operację between
Witam, Mamy słownik obsługujący serach, insert. Np, drzewo AVL. Naszym zadaniem jest wzbogacić je o operację: between (x,y) = |\{a\in S: x\le a\le y\}| Każda operacja ma pesymistycznie działać w czasie logarytmicz...
 matematyka464  3
 [Algorytmy] Algorym offsetu (przesunięcia) krzywej
Witam, Tworzę prosty program, którego zadaniem jest wyrysowanie krzywych zapisanych w kodzie programu. Ale poległem na na (wydawałoby się) banalnej rzeczy - otóż nie wiem jak zrobić offset czyli przesunięcie krzywej. Żeby było łatwiej nie będzie k...
 oneiro  2
 [Algorytmy] CYK, postać normalna Chomsky'ego
Stosując algorytm CYK sprawdź, czy podane słowo należy do języka danej gramatyki bezkontekstowej w postaci normalnej Chomsky'ego. Jeżeli tak, to odtwórz przykładowe wyprowadzenie i podaj drzewo tego wyprowadzenia. x = aabaaab S ---&g...
 przem11122  0
 [Algorytmy] najdluzszy rosnacy podciag
Witam Rozważmy problem wyznaczania najdłuższego rosnącego podciągu ciągu n liczb. Elementy podciągu nie muszą występować w oryginalnym ciągu jeden za drugim. Na przykład, obydwa ciągi (1,3,4) i (1,2,...
 buzzek90  0
 [Algorytmy] Ile jest liczb pierwszych na przedziale
Witam. Jest to mój pierwszy post na tym forum. Niedawno zacząłem przygodę z programowaniem w c++. Mam do napisania program, w którym należy podać z klawiatury liczbę testowanych przedziałów, następnie wprowadzić granicę tych przedziałów i na wyjściu...
 mario765i  9
 [Algorytmy] Szybki test liczby koniecznych dzieleń w n!
Rozwiązując problem 148 z projektu Euler... Najpierw spróbowałem brute forcem, ale szybko odkryłem, że jest to metoda zbyt mało wydajna. Próbowałem innych prostych metod, ale ok...
 Ginden  10
 [Algorytmy][C++] Średnia liczb z danego obszaru pamięci
hej, mam obliczyć średnią arytmetyczną pomiędzy 2 elementami tablicy włącznie, posługując się tylko 2 wksaźnikami.Pytanie jak to zrobić ? Tablica jest obszarem ciągłym więc próbowałęm suma = suma / ((k-p)/sizeof(int) +1);[/icode:uoy...
 Ser Cubus  23
 [Algorytmy] Określ największy rozmiar n.
Dla każdej funkcji f(n) i czasu t w poniższej tabeli, określ największy rozmiar n danych dla których algorytm wykona obliczenia w czasie t. Zakładamy, że a...
 informatykmatematyk  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com