| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 22 | 8 | 6 | 40.000% |
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.
See on interaktiivne ülesanne, kus programm võib testimissüsteemile päringuid esitada. Päringu esitamiseks tuleb väljastada rida kujul
? $A_1$ $A_2$ $A_3$ $\ldots$ $A_M$
kus $1 \le M \le 5\,000$ ja $0 \le A_i \le 9$ on programmi valitud. Testimissüsteem väljastab selle peale eraldi reale ühe täisarvarvu: jada $A$ kontrollsumma $(A_1 \cdot K_1 + A_2 \cdot K_2 + \ldots + A_M \cdot K_M) \bmod 10$.
Lõpuks peab programm esitama leitud $K$. Selleks tuleb väljastada rida kujul
! $K_1$ $K_2$ $K_3$ $\ldots$ $K_N$
ja seejärel programmi töö lõpetada.
3 1 0
? 7 1 6 ? 5 6 4 ? 1 2 3 ! 3 4
Selles näites on $N = 2$ ja $K = (3,4)$. Jada $A = (7,1,6)$ kontrollsumma on siis $(A_1 \cdot K_1 + A_2 \cdot K_2 + A_3 \cdot K_1) \bmod 10 = (7 \cdot 3 + 1 \cdot 4 + 6 \cdot 3) \bmod 10 = 43 \bmod 10 = 3$. (Pane tähele, et $K$ kordub, kuna see on lühem kui $A$.)
Jada $A = (5,6,4)$ kontrollsumma on $(A_1 \cdot K_1 + A_2 \cdot K_2 + A_3 \cdot K_1) \bmod 10 = (5 \cdot 3 + 6 \cdot 4 + 4 \cdot 3) \bmod 10 = 51 \bmod 10 = 1$.
Viimases päringus tuleb summa väärtuseks $20$ ja seega kontrollsummaks $0$.