Kontrollsumma

문제

Kontrollsummad aitavad tuvastada vigu andmete edastamisel või sisestamisel. Selleks on leiutatud palju erinevaid algoritme. Siin ülesandes vaatame ühte lihtsaimat neist: arvujada $(A_1,A_2,\dots )(A\_1,\; A\_2,\; \backslash ldots)$ kontrollsumma on $$(A_1\cdot K_1+A_2\cdot K_2+\dots +A_N\cdot K_N+A_{N+1}\cdot K_1+\dots )10,(A\_1\; \backslash cdot\; K\_1\; +\; A\_2\; \backslash cdot\; K\_2\; +\; \backslash ldots\; +\; A\_N\; \backslash cdot\; K\_N\; +\; A\_\{N+1\}\; \backslash cdot\; K\_1\; +\; \backslash ldots)\; \backslash bmod\; 10,$$ kus $K_1,K_2,\dots ,K_{N}K\_1,\; K\_2,\; \backslash ldots,\; K\_N$ on mingid konstandid. Pane tähele, et jada $KK$ käsitletakse perioodilisena: kui $AA$ pikkus ületab $KK$ pikkust, kasutatakse $KK$ elemente algusest peale uuesti. Kui $AA$ on lühem, siis jäävad mõned $KK$ elemendid lihtsalt kasutamata.

Juku leidis süsteemi, mis kasutab eelkirjeldatud kontrollsummat. Aga ta ei tea, milline on selles süsteemis jada $KK$ pikkus $NN$ või selle elementide $K_{i}K\_i$ väärtused. Ta teab ainult, et $N\le 1000N\; \backslash le\; 1\backslash ,000$ ja $1\le K_i\le 91\; \backslash le\; K\_i\; \backslash le\; 9$. Juku saab teha süsteemile päringuid. Iga päring on mingi arvujada ja süsteem annab vastuseks selle jada kontrollsumma. Juku klaviatuuril on klahv 0 natuke katki ja seetõttu on seda numbrit raskem sisestada. Sellepärast sooviks ta päringutes numbrit 0 mitte kasutada.

Kirjuta Jukule programm, mis leiab jada $KK$ pikkuse ja selle elementide väärtused. $KK$ perioodilisuse tõttu on võimalike vastuseid lõpmata palju; väljastada neist kõige lühem.