[Algorytmy] Materiały wybuchowe. Proserwy

[satre]

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

[marcin_smu]

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)}\).

[Zordon]

Kompletnie nie rozumiem rozwiązania tego zadania zawartego w oficjalnej książeczce z obozu.

Gdzie można taką książeczkę zdobyć?

[satre]

Jeśli nie odpowiedz brzmi oczywiście "NIE", jeśli tak odpowiedzią jest równa \(\displaystyle{ 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 \(\displaystyle{ x/a}\) elementów \(\displaystyle{ a}\) co jest nieprawdą kontrprzykład:
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)}\)

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.

[marcin_smu]

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}\).