== include(page="template/taskheader" task_id="div") ==
http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=488
Se citesc două numere naturale M și N.
Se consideră numerele naturale N și K și cifrele nenule și distincte $c[~1~], c[~2~], ..., c[~N~]$.
h2. Cerință
Să se elimine o secvență de cifre din numărul N pentru a obține un număr divizibil cu M de valoare maximă.
Să se determine câte numere de K cifre formate doar cu cifrele $c[~1~], c[~2~], ..., c[~N~]$ sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4 001.
h2. Date de intrare
Fișierul de intrare div.in conține pe prima linie numărul natural nenul M iar pe a doua linie numărul natural N.
Fișierul de intrare $div.in$ conține pe prima linie numerele naturale N și K separate printr-un spațiu, iar pe linia a doua cele N cifre distincte $c[~1~], c[~2~], ..., c[~N~]$ separate prin câte un spațiu.
h2. Date de ieșire
Fișierul de ieșire div.out va conține două numere întregi i1 și i2 separate prin câte un spațiu, reprezentând indicii primei, respectiv ultimei cifre care vor fi șterse. Cifrele lui N se indexează de la 1, de la stânga la dreapta. Dacă sunt mai multe soluții se va scrie cea pentru care primul indice este cel mai mic. Dacă nu trebuie eliminată nici o cifră se vor scrie două cifre de 0.
Fișierul de ieșire $div.out$ va conține o singură linie pe care va fi scris un singur număr natural, reprezentând numărul (modulo [$4001$]) de numere de K cifre formate doar cu cifrele $c[~1~], c[~2~], ..., c[~N~]$ și divizibile cu [$3$].
h2. Restricții
* 2 <= M <= 30000.
* N are cel mult 5000 cifre.
* prima cifră a lui N este nenulă.
* o secvență este formată din cifre aflate pe poziții consecutive în numărul N.
* $1 ≤ N ≤ 9$
* $2 ≤ K ≤ 1 000$
* $1 ≤ c[~1~], c[~2~], ..., c[~n~] ≤ 9$
* Definim $x modulo 4 001$ ca fiind restul împărțirii întregi a lui $x$ la $4 001$. De exemplu, $4 002 modulo 4 001 = 1$.
* $Proprietăți:$
** $(a + b) modulo 4 001 = (a modulo 4001 + b modulo 4 001) modulo 4 001$
** $(a * b) modulo 4 001 = (a modulo 4001 * b modulo 4 001) modulo 4 001$
h2. Exemplu
table(example).
|_. div.in |_. div.out |
| 2
3333333333
| 1 10
| 3 2
1 3 2
| 3
|
|7
33332222
|0 0
|
|7
3333322222
|5 6
|
h2. Explicație
Trebuie determinat numărul de numere de $K = 2$ cifre formate doar din cifrele [$1$], $2$ și $3$ și care sunt divizibile cu [$3$]. Acestea sunt în număr de [$3$], și anume: [$12$], [$21$], [$33$]. Rezultatul $3$ împărțit la $4001$ furnizează restul [$3$].
== include(page="template/taskfooter" task_id="div") ==
