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, \ldots)$ kontrollsumma on $$(A_1 \cdot K_1 + A_2 \cdot K_2 + \ldots + A_N \cdot K_N + A_{N+1} \cdot K_1 + \ldots) \bmod 10,$$ kus $K_1, K_2, \ldots, K_N$ on mingid konstandid. Pane tähele, et jada $K$ käsitletakse perioodilisena: kui $A$ pikkus ületab $K$ pikkust, kasutatakse $K$ elemente algusest peale uuesti. Kui $A$ on lühem, siis jäävad mõned $K$ elemendid lihtsalt kasutamata.

Juku leidis süsteemi, mis kasutab eelkirjeldatud kontrollsummat. Aga ta ei tea, milline on selles süsteemis jada $K$ pikkus $N$ või selle elementide $K_i$ väärtused. Ta teab ainult, et $N \le 1\,000$ ja $1 \le K_i \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 $K$ pikkuse ja selle elementide väärtused. $K$ perioodilisuse tõttu on võimalike vastuseid lõpmata palju; väljastada neist kõige lühem.