Witam,
mam problem z następującym zadaniem . 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 \(\displaystyle{ 10^{17}}\). Może ktoś tutaj by opisał w łatwy sposób rozwiązanie.
Z góry dziękuje za pomoc
[Algorytmy] Materiały wybuchowe. Proserwy
-
- Użytkownik
- Posty: 53
- Rejestracja: 21 lut 2011, o 20:49
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice
- Pomógł: 10 razy
[Algorytmy] Materiały wybuchowe. Proserwy
Witam,
nie znam oficjalnego rozwiązania jednak mogę przedstawić to co wymyśliłem przed chwilą.
Oznaczmy przez \(\displaystyle{ a}\) największą z liczb \(\displaystyle{ y}\). Idea rozwiązania opiera się na sprowadzeniu naszego \(\displaystyle{ x}\) dzięki mniejszym materiałom wybuchowym do liczby podzielnej przez \(\displaystyle{ a}\).
Dla każdej reszty \(\displaystyle{ r}\) znajdźmy takie przydzielenie materiałów o sumie równej \(\displaystyle{ b \cdot a+r}\), aby ich liczba użytych materiałów odjąć \(\displaystyle{ b}\) była jak najmniejsza i oznaczy tą wartość \(\displaystyle{ w[r]}\). Można to zrobić lekko zmodyfikowanym bfs'em w złożoność \(\displaystyle{ O(ak)}\).
Wyznaczmy również nwd wszystkich liczb \(\displaystyle{ y}\). \(\displaystyle{ O(k~log~a)}\)
Sprawdzając dane \(\displaystyle{ x}\) po pierwsze sprawdzamy czy \(\displaystyle{ x}\) jest podzielne przez to nwd.
Jeśli nie odpowiedz brzmi oczywiście "NIE", jeśli tak odpowiedzią jest równa \(\displaystyle{ w[ x \% a ] + x / a}\) (nie musimy się przy tym martwić, że przy obliczaniu naszego \(\displaystyle{ w[r]}\) wartość \(\displaystyle{ b}\) jest zbyt duża ponieważ \(\displaystyle{ x>a^2}\))
Reasumując całe zadanie da się zrobić w złożoności \(\displaystyle{ O(ak+n)}\).
nie znam oficjalnego rozwiązania jednak mogę przedstawić to co wymyśliłem przed chwilą.
Oznaczmy przez \(\displaystyle{ a}\) największą z liczb \(\displaystyle{ y}\). Idea rozwiązania opiera się na sprowadzeniu naszego \(\displaystyle{ x}\) dzięki mniejszym materiałom wybuchowym do liczby podzielnej przez \(\displaystyle{ a}\).
Dla każdej reszty \(\displaystyle{ r}\) znajdźmy takie przydzielenie materiałów o sumie równej \(\displaystyle{ b \cdot a+r}\), aby ich liczba użytych materiałów odjąć \(\displaystyle{ b}\) była jak najmniejsza i oznaczy tą wartość \(\displaystyle{ w[r]}\). Można to zrobić lekko zmodyfikowanym bfs'em w złożoność \(\displaystyle{ O(ak)}\).
Wyznaczmy również nwd wszystkich liczb \(\displaystyle{ y}\). \(\displaystyle{ O(k~log~a)}\)
Sprawdzając dane \(\displaystyle{ x}\) po pierwsze sprawdzamy czy \(\displaystyle{ x}\) jest podzielne przez to nwd.
Jeśli nie odpowiedz brzmi oczywiście "NIE", jeśli tak odpowiedzią jest równa \(\displaystyle{ w[ x \% a ] + x / a}\) (nie musimy się przy tym martwić, że przy obliczaniu naszego \(\displaystyle{ w[r]}\) wartość \(\displaystyle{ b}\) jest zbyt duża ponieważ \(\displaystyle{ x>a^2}\))
Reasumując całe zadanie da się zrobić w złożoności \(\displaystyle{ O(ak+n)}\).
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Algorytmy] Materiały wybuchowe. Proserwy
Gdzie można taką książeczkę zdobyć?satre pisze:Kompletnie nie rozumiem rozwiązania tego zadania zawartego w oficjalnej książeczce z obozu.
-
- Użytkownik
- Posty: 17
- Rejestracja: 26 mar 2010, o 15:36
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
[Algorytmy] Materiały wybuchowe. Proserwy
Nie wiem czy dobrze zrozumiałem ale według tego co napisałeś wynika że w rozwiązaniu optymalnym występuje zawsze \(\displaystyle{ x/a}\) elementów \(\displaystyle{ a}\) co jest nieprawdą kontrprzykład:marcin_smu pisze: Jeśli nie odpowiedz brzmi oczywiście "NIE", jeśli tak odpowiedzią jest równa \(\displaystyle{ w[ x \% a ] + x / a}\)
dla materiałów \(\displaystyle{ 10, 9, 1}\) i \(\displaystyle{ x=108}\) optymalnym rozwiązaniem jest \(\displaystyle{ 11 (9*10+2*9)}\) a nie \(\displaystyle{ 18 (10*10+8*1)}\)
Na oficjalnej stronie obozu.Zordon pisze:Gdzie można taką książeczkę zdobyć?satre pisze:Kompletnie nie rozumiem rozwiązania tego zadania zawartego w oficjalnej książeczce z obozu.
-
- Użytkownik
- Posty: 53
- Rejestracja: 21 lut 2011, o 20:49
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice
- Pomógł: 10 razy
[Algorytmy] Materiały wybuchowe. Proserwy
Przy liczeniu danego \(\displaystyle{ w[r]}\) bierzemy pod uwagę, to że możemy użyć mniej elementów \(\displaystyle{ a}\). W przykładzie, który przytoczyłeś mamy \(\displaystyle{ w[8]=1}\), dla przydzielenia dwóch materiałów o wielkości \(\displaystyle{ 9}\). \(\displaystyle{ 2 \cdot 9 = 1 \cdot 10+8}\), czyli \(\displaystyle{ b=1}\), więc ilość użytych materiałów odjąć \(\displaystyle{ b}\) wynosi właśnie \(\displaystyle{ 1}\). \(\displaystyle{ w[8]+\lfloor \frac{108}{10} \rfloor=11}\).