Omówienie zadania Podzielność (I etap XXIV OI)
Rozważamy system pozycyjny o podstawie \(B\). Mając dany pewien multizbiór cyfr (o którym wiemy, że każda cyfra występuje w nim co najmniej raz), chcemy z niektórych cyfr tego multizbioru stworzyć największą liczbę, która dzieli się przez \(B-1\). Liczba ta może być bardzo duża, więc zamiast wypisać ją w całości, musimy odpowiadać na zapytania o konkretne cyfry tej liczby.
Wstępne rozważania
Zastanówmy się, jak rozwiązać zadanie w znanym nam dobrze systemie dziesiątkowym (tj. systemie o podstawie \(B=10\)). Liczba, której szukamy, winna dzielić się w takim razie przez \(B-1 = 9\). Cecha podzielności przez dziewięć jest powszechnie znana, ale zastanówmy się chwilę nad dowodem tej własności.
Lemat 1. Liczba jest podzielna przez \(9\) wtedy i tylko wtedy, gdy suma jej cyfr jest podzielna przez \(9\).
Dowód. Niech rozważana liczba \(x\) ma zapis dziesiętny \(c_m \ldots c_{2} c_{1} c_{0}\), tzn.: \[ x = 10^0 c_0 + 10^1 c_1 + 10^2 c_2 + \ldots + 10^m c_m. \] Wystarczy spojrzeć na resztę z dzielenia (operacja modulo) tej liczby przez \(9\) i skorzystać z faktu, że dla \(\diamond \in \{ +, \cdot \}\): \[ (a \diamond b) \bmod c = ((a \bmod c) \diamond (b \bmod c)) \bmod c. \] Tak więc, zamiast brać resztę z dzielenia sumy/iloczynu, możemy wziąć resztę z dzielenia sumy/iloczynu reszt z dzielenia poszczególnych składników/czynników.
Dla dowolnego \(k \geq 0\) mamy zatem: \[ 10^k = 10 \cdot 10 \cdot \ldots \cdot 10 \equiv 1 \cdot 1 \cdot \ldots \cdot 1 = 1 \pmod{9}, \] skąd: \[ x \equiv c_0 + c_1 + c_2 + \ldots + c_m \pmod{9}. \quad \square \]
Uważny Czytelnik zauważy, że udowodniliśmy tak naprawdę ciekawszy fakt.
Lemat 2. Reszta z dzielenia dowolnej liczby \(x\) przez \(9\) jest równa reszcie z dzielenia przez \(9\) sumy cyfr tej liczby.
Kluczową obserwacją w tym zadaniu jest fakt, że w istocie dokładnie taki sam dowód działa dla liczby w dowolnym systemie pozycyjnym \(B\) przy sprawdzaniu podzielności przez \(B-1\).
Lemat 3. W systemie pozycyjnym o podstawie \(B\) liczba jest podzielna przez \(B-1\) wtedy i tylko wtedy, gdy suma jej cyfr jest podzielna przez \(B-1\).
Sprawdzenie, że powyższy dowód działa dla dowolnego \(B\), pozostawiamy Czytelnikowi.
Szukana liczba
Zastanówmy się teraz, jak znaleźć szukaną liczbę podzielną przez \(B-1\).
Aby uzyskać jak największą liczbę, chcemy przede wszystkim użyć jak najwięcej cyfr (jako że liczba o mniejszej liczbie cyfr musi być mniejsza). Zastanówmy się, kiedy możemy użyć wszystkich cyfr danych na wejściu. Rozważmy zatem sumę tych wszystkich cyfr, którą możemy obliczyć jako \(\sum_{i=0}^{B-1} a_i \cdot i\). Jeżeli suma ta dzieli się przez \(B-1\), to największa liczba jest po prostu liczbą złożoną ze wszystkich cyfr. Wśród wszystkich takich liczb największą będzie ta, w której wszystkie te cyfry będą posortowane nierosnąco (tj. największa cyfra będzie najbardziej znacząca).
W przeciwnym wypadku, liczba ta daje pewną resztę \(r\) (\(0 < r < B\)) z dzielenia przez \(B-1\). Jako że nie możemy ułożyć liczby złożonej ze wszystkich cyfr, musimy usunąć pewne cyfry, przy czym chcemy ich usunąć jak najmniej, aby liczba była jak największa. Zauważmy, że możemy usunąć dokładnie jedną cyfrę: \(r\). Wiemy, że taka cyfra istnieje, z założenia, że dysponujemy każdą cyfrą co najmniej raz.
Zapytania
Wiemy zatem, jak wygląda szukana największa liczba. Ostatnim problemem, z jakim musimy poradzić sobie w tym zadaniu, jest to, że liczba ta może być strasznie duża. Konkretnie, długość jej zapisu wynosi \(A = \sum_{i=0}^{B-1} a_i\) lub \(A-1\), co przy ograniczeniach z zadania może wynosić nawet do \(10^{12}\). W szczególności, nie możemy sobie pozwolić na to, aby trzymać tę liczbę w pamięci.
W zadaniu musimy jedynie odpowiadać na zapytania o \(k\)-tą kolejną cyfrę tej liczby, co powinno być dużo łatwiejsze, jako że nasza liczba ma dość prostą strukturę: te same cyfry znajdują się w spójnych blokach liczby, które następują po sobie w kolejności malejących cyfr.
Interesuje nas zatem jedynie, jaka jest liczba cyfr w danym bloku (czyli liczba cyfr danego rodzaju). Na wejściu mamy już podane liczby wszystkich cyfr, dodatkowo posortowane tak jak chcemy (od pozycji najmniej znaczących), dane jako tablica \(a\). Nas będzie interesowała tablica \(a'\), powstała z tablicy \(a\) poprzez ewentualne usunięcie jednej cyfry (z warunku powyżej).
Aby odpowiedzieć, jaka cyfra stoi na \(k\)-tym miejscu, wystarczy odpowiedzieć, w bloku jakich cyfr znajdzie się \(k\)-ta cyfra.
Na takie zapytania możemy odpowiadać na dwa sposoby.
Algorytm online
Zauważmy, że możemy obliczyć nową tablicę sum częściowych, która dla każdego bloku liczby pamięta, ile cyfr znajduje się w prefiksie liczby kończącym się na tym bloku, tj. jak wiele cyfr znajduje się do tego bloku włącznie.
Mamy:
- \(\mathit{pref}_{0} = a'_{0}\),
- \(\mathit{pref}_{1} = a'_{0} + a'_{1}\),
- \(\ldots\)
- \(\mathit{pref}_{B-1} = a'_{0} + a'_{1} + \ldots + a'_{B-2} + a'_{B-1}\).
W ogólnym przypadku, dla \(1 \leq i < B\): \(\mathit{pref}_{i} = \mathit{pref}_{i-1} + a'_i\).
Teraz możemy odpowiadać na kolejne zapytania, przeglądając tablicę \(\mathit{pref}\). Mianowicie odpowiedzią na zapytanie o \(k\)-tą cyfrę jest najmniejszy indeks \(i\), taki że \(k \leq \mathit{pref}_i\), bądź \(-1\), jeżeli taki indeks nie istnieje.
Aby uzyskać rozwiązanie o dobrej złożoności, zamiast przeszukiwać tę tablicę wprost, możemy użyć wyszukiwania binarnego, jako że wartości w tablicy \(\mathit{pref}\) stanowią ciąg niemalejący.
Rozwiązanie to działa w czasie \(O(B + q \log B)\) i pamięci \(O(B)\).
Algorytm offline
Możemy podejść do tego problemu z drugiej strony i najpierw zapamiętać wszystkie zapytania, a następnie je posortować. Teraz możemy użyć np. metody dwóch wskaźników, aby poruszać się po posortowanej tablicy z zapytaniami i tablicy sum częściowych.
Rozważając konkretny blok (złożony z tych samych cyfr), zapisujemy odpowiedzi na wszystkie zapytania, które leżą w jego obrębie, po czym przechodzimy do kolejnego bloku. Dla wszystkich zapytań, dla których w ten sposób nie przydzielimy odpowiedzi, wynikiem jest \(-1\).
Rozwiązanie to działa w czasie \(O(B + q \log q)\) i pamięci \(O(B + q)\).