Omówienie zadania Suma cyfr (II etap XXIV OI)

Rozwiązanie zadania rozpoczniemy od obliczenia liczby liczb spełniających założenia zadania, tzn. liczb:

• o ustalonej długości zapisu dziesiętnego (co najwyżej 200 cyfr),
• o sumie cyfr równej \(s\),
• podzielnych przez \(m\).

Robimy to w szczególności dlatego, że jest to niezbędne do rozpoznania czy odpowiedź, która ma być wypisana na wyjście powinna być NIE. Jak się też okaże, jest to kluczowe również przy wyznaczeniu pełnego rozwiązania zadania także w przypadku odpowiedzi pozytywnej.

Obliczanie liczby rozwiązań

Do rozwiązania problemu zastosujemy metodę programowania dynamicznego. Niech \(L_{n,s,r}\) określa liczbę liczb \(n\)-cyfrowych (być może z zerami wiodącymi) o sumie cyfr równej \(s\), dla których reszta z dzielenia przez \(m\) (podane w zadaniu) wynosi \(r\).

Wartość \(L_{n,s,r}\) może być teraz obliczona rekurencyjnie z następującego wzoru:

\[ L_{n,s,r} = \begin{cases} 1 & n = 0,\ s = 0,\ r = 0 \\ 0 & n = 0,\ s \neq 0 \vee r \neq 0 \\ 0 & n < 0 \vee s < 0 \\ \displaystyle\sum_{i=0}^{9} L_{n-1,s-i,r_i} & n \geq 1 \end{cases} \]

gdzie: \(r_i = (r - 10^{n-1} \cdot i) \bmod m\).

Idea tego wzoru jest następująca: ustalamy pierwszą cyfrę (tzn. tę na najbardziej znaczącej pozycji dziesiętnej) jako \(i\). Chcąc uzyskać liczbę \(n\)-cyfrową, która ma sumę cyfr równą \(s\) oraz resztę \(r\) z dzielenia przez \(m\), wystarczy za ustaloną cyfrą \(i\) napisać dowolną liczbę \((n-1)\)-cyfrową o sumie cyfr równej \(s-i\) oraz reszcie z dzielenia równej \(r_i\). Wyboru tego można dokonać na \(L_{n-1,s-i,r_i}\) sposobów. Każda uporządkowana para: najbardziej znacząca cyfra \(i\) oraz wybrany \((n-1)\)-cyfrowy dopisek daje w efekcie inną liczbę wynikową, więc obliczenie sumy wartości \(L_{n-1,s-i,r_i}\) dla każdego wyboru cyfry \(i\) jest podejściem właściwym do obliczenia wartości \(L_{n,s,r}\).

Wartości początkowe w tej metodzie także łatwo wytłumaczyć: trudno uzyskać liczbę inną niż \(0\) nie mając do dyspozycji żadnych cyfr. Dopisanie jakiejkolwiek cyfry do takiej „pustej" liczby ma (w kontekście uzyskanej sumy cyfr i reszty z dzielenia przez \(m\)) taki sam efekt, jak dopisanie tej samej cyfry do liczby \(0\), a skoro jedno jest zero — to jest i tylko jedna „pusta" liczba.

Aby uniknąć operacji na dużych liczbach, wystarczy zauważyć, że w treści zadania podane zostało, że \(k \leq 10^{18}\), a zatem nie jest konieczne rozróżnianie wartości \(L_{n,s,r}\) większych niż \(10^{18}\) — wszystkie je można zastąpić odpowiednio dobraną w programie stałą liczbową większą niż \(10^{18}\), która jeszcze mieści się w dostępnym 64-bitowym typie liczb całkowitych.

Ostatecznie, algorytm obliczania wartości \(L\) dla interesujących nas (potrzebnych w dalszych obliczeniach) indeksów \(n\), \(s\), \(r\), wygląda następująco:

Odzyskanie wyniku na podstawie tablicy \(L\)

Jeśli wartość \(L_{200,s,0}\) jest mniejsza niż podane na wejściu \(k\), wówczas na wyjściu powinno się znaleźć słowo NIE i możemy zakończyć — liczba liczb co najwyżej \(200\)-cyfrowych jest za mała, by znaleźć wśród nich szukaną \(k\)-tą liczbę. W przeciwnym razie — można znaleźć najmniejszą długość liczby \(n\), że zachodzi warunek: \(L_{n,s,0} \geq k\). Od teraz wiemy już, że wypisany na wyjściu wynik powinien być \(n\)-cyfrowy. Pozostaje jedynie ustalić te cyfry.

Cyfry wyniku będą ustalane od lewej do prawej (tzn. rozpoczynając od najbardziej znaczącej w zapisie dziesiętnym). Wśród wszystkich liczb, które spełniają warunek odpowiedniej sumy cyfr \(s\) oraz odpowiedniej reszty \(r\) (na początku 0) z dzielenia przez \(m\), ustalmy ile jest rozpoczynających się cyfrą 0, 1, 2, …, 9. Jeśli wiadomo ile ich jest, to wiadomo jaka powinna być pierwsza cyfra szukanej \(k\)-tej liczby:

\(r_i\) oznacza tutaj, tak jak wcześniej, resztę z dzielenia jaką musi mieć pozostały dopisek \((n-1)\)-cyfrowy, aby wraz z cyfrą \(i\) na początku zapisu dziesiętnego uzyskać oczekiwaną resztę z dzielenia \(r\) przy dzieleniu przez \(m\).

Niech teraz \(S_{n,s,r,d} = \sum_{i=0}^{d} L_{n-1,s-i,r_i}\) będzie liczbą liczb \(n\)-cyfrowych o sumie cyfr równej \(s\), reszcie z dzielenia \(r\) przy dzieleniu przez \(m\), rozpoczynających się cyfrą ze zbioru \(\{0, 1, \dots, d\}\). Poszukiwany wynik rozpoczyna się cyfrą \(d\), gdy \(d\) jest największe możliwe, żeby: \(S_{n,s,r,d} \leq k\). Co więcej, po ustaleniu tego, wiadomo jaki powinien być dopisek za cyfrą \(d\): należy go poszukiwać na pozycji \(k - S_{n,s,r,d-1}\) (zakładamy tutaj, że \(S_{n,s,r,-1} = 0\)) wśród liczb \((n-1)\)-cyfrowych z sumą cyfr \(s-d\), o reszcie z dzielenia \(r_d\). W analogiczny sposób można zatem wyznaczyć pierwszą cyfrę tego dopisku (a zatem drugą cyfrę całego wyniku) i każdą kolejną:

W powyższym algorytmie Write wypisuje pojedynczą cyfrę wyniku, a \(p_{10}[x]\) oznacza \(10^x \bmod m\). Tablicę tę można obliczyć w czasie \(O(n)\).

Cały algorytm działa w czasie \(O(n \cdot s \cdot m)\), gdzie \(n\) oznacza długość liczby wynikowej (w przypadku tego zadania była ona nie większa niż \(200\)). Główny czas zużywany jest na obliczenie tablicy \(L\).

Inne rozwiązania

Rozwiązanie uproszczone dla \(m = 1\)

Nieco łatwiejsze rozwiązanie można uzyskać, gdyby pominąć trzeci wymiar tablicy \(L\) (resztę z dzielenia przez \(m\)). Rozwiązanie nie będzie w stanie wyznaczać wtedy liczby liczb podzielnych przez \(m\) (a jedynie znajdzie liczbę wszystkich liczb spełniających pozostałe warunki). Rozwiązanie otrzymywało na zawodach 60% maksymalnej punktacji.

Rozwiązanie dla \(m = 1\) oraz mniejszych wartości \(k\)

Stosunkowo łatwo można wyznaczyć najmniejszą liczbę o ustalonej sumie cyfr (przy warunku \(m = 1\)) — musi mieć ona \(\lceil \frac{s}{9} \rceil\) cyfr: pierwszą równą \(s \bmod 9\), a wszystkie pozostałe cyfry \(9\).

Jeśli chcemy uzyskać kolejną liczbę (najmniejszą liczbę większą od aktualnej) o tej samej sumie cyfr, należy znaleźć w aktualnej liczbie najpóźniejszą cyfrę (być może zero wiodące), która nie jest równa \(9\) i zwiększyć ją o \(1\). Następnie należy za tą cyfrą znaleźć najwcześniejszą niezerową cyfrę i zmniejszyć ją o \(1\). Suma cyfr pozostaje więc niezmieniona, a liczba została zwiększona o najmniejszą możliwą wartość. Powtórzenie tego procesu \(k-1\) razy pozwoli uzyskać \(k\)-tą liczbę o sumie cyfr równej podanemu \(s\). W zależności od jakości implementacji, rozwiązanie oparte o ten pomysł mogło uzyskiwać nawet 30% maksymalnej punktacji.

Rozwiązanie dla \(k = 1\)

O problemie można też myśleć na sposób grafowy. Stwórzmy graf wierzchołków-stanów \((n, s, r)\) opisujący możliwość uzyskania liczby \(n\)-cyfrowej o sumie cyfr \(s\) i reszcie z dzielenia \(r\) przy dzieleniu przez \(m\). Krawędzie mogą reprezentować dopisanie pojedynczej cyfry (tym razem łatwiej dopisywać cyfry na najmniej znaczących pozycjach), a zatem ze stanu \((n, s, r)\) istnieje krawędź etykietowana cyfrą \(i\) do stanu \((n+1, s+i, (10 \cdot r + i) \bmod m)\).

W wariancie zadania dla \(k = 1\) zadanie sprowadza się do znalezienia najkrótszej ścieżki ze stanu \((0, 0, 0)\) do dowolnego stanu \((n, 0, 0)\) dla \(n \geq 1\). Spośród wszystkich ścieżek tej samej długości należy wybrać taką, w której odczytanie kolejnych etykiet utworzy liczbę najmniejszą (innymi słowy — napis będzie najmniejszy leksykograficznie). Standardowa implementacja algorytmu przeszukiwania wszerz, w którym przeglądanie sąsiadujących stanów będzie wykonywane zawsze zgodnie z kolejnością etykiet od najmniejszej do największej, pozwoli łatwo znaleźć taką ścieżkę. Rozwiązanie warte było na zawodach 10% maksymalnej punktacji.

Rozwiązanie dla małych odpowiedzi

W podzadaniu pierwszym dopuszczalne było przetestowanie każdej liczby naturalnej w celu bezpośredniego sprawdzenia czy spełnia ona warunki zadania. Rozwiązanie oparte na tym pomyśle warte było zaledwie 5% maksymalnej punktacji.