Karmienie śledziami

Co prawda już po świętach, ale jako już ostatnie w tym roku proponuję zadanie o śledziach z zawodów CTU Open 2015. Interesuje nas w nim policzenie sposobów, na jakie można przedstawić podaną liczbę n jako a+b+c tak, żeby a,b,c\geq L oraz żadna z liczb a,b,c nie zawierała cyfry 3 w swoim zapisie dziesiętnym.

Oryginalną treść można zobaczyć tutaj. Co pewnie nie zaskakuje, limit na n jest dość spory — 10^{10000} i w związku z tym jesteśmy proszeni o wypisanie liczby sposobów modulo 12345647. O L wiemy tylko tyle, że L \leq \frac{n}{3}.

Naturalnym podejściem jest równoległe zgadywanie cyfr w zapisie dziesiętnym liczb a,b,c. Skoro interesuje nas ich suma, a liczby dodajemy zwykle zaczynając od najmniej znaczącej cyfry, spróbujmy zacząć zgadywanie też w taki sposób. Oczywiście zgadywanie tak naprawdę oznacza tutaj programowanie dynamiczne. Jaka wiedza wystarczyłaby nam do uzupełnienia pozostałych cyfr po zgadnięciu k najmniej znaczących cyfr liczb a,b,c?

Wyobraźmy sobie, że wyliczamy a+b+c i załóżmy, że wybraliśmy już k najmniej znaczących cyfr liczb a,b,c tak, że k najmniej znaczących cyfr a+b+c zgadza się z k najmniej znaczącymi cyframi n. Na pewno istotne jest przeniesienie, które (ponieważ dodajemy do siebie trzy liczby) jest liczbą z zakresu [0,2]. Co jeszcze musimy wiedzieć o tych już wybranych najmniej znaczących cyfrach?

Na samym końcu musimy sprawdzić, czy a,b,c \geq L. Żeby sprawdzić, czy x \geq L, wystarczy upewnić się, że x = L lub najbardziej znacząca cyfra różniąca obydwie liczby jest większa w x. Ten warunek jest dla nas o tyle niewygodny, że wymaga przejrzenia x zaczynając od najbardziej znaczącej cyfry, podczas gdy nasza konstrukcja najpierw wybiera najmniej znaczącą cyfrę. Nie jest to jednak duży problem. Powiedzmy bowiem, że wiemy, czy najbardziej znacząca cyfra różniąca k najmniej znaczących cyfr x oraz L jest większa w x. Po wybraniu kolejnej (czyli (k+1)-szej) cyfry x możemy wtedy łatwo zaktualizować taką informację, to znaczy wyliczyć, czy najbardziej znacząca cyfra różniąca k+1 najmniej znaczących cyfr x oraz L jest większa w x.

Wystarczy więc oprócz przeniesienia przechowywać jeden bit informacji dla każdej z liczb a,b,c. Po wybraniu (k+1)-tych cyfr a,b,c (zgodnie z treścią zadania, różnych od 3) sprawdzamy, czy po dodaniu ich do przeniesienia uzyskamy (k+1)-szą cyfrę n. Jeśli tak, wyliczamy nowe przeniesienie i aktualizujemy bity informacji przechowywane dla każdej z liczb. Jeśli wybraliśmy już tyle cyfr, ile jest w zapisie dziesiętnym n, wynik to 1 jeśli przeniesienie oraz wszystkie bity informacji są równe zeru oraz 0 w przeciwnym wypadku.

Czyli rozwiązanie całego zadania sprowadza się do wyliczenia 10000 \cdot 3 \cdot 2^3 wartości w programowaniu dynamicznym. Wyliczenie każdej z nich może być wykonane przez naiwne przejrzenie wszystkich 10^3 możliwych kombinacji kolejnych cyfr. Ponieważ wiemy jednak, jaka powinna być suma tych kolejnych liczb modulo 10, możemy zmniejszyć liczbę kombinacji do 10^2, co pozwala na rozwiązanie całego zadania z dość dużym zapasem.

Reklamy

Jedna myśl nt. „Karmienie śledziami

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s