시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB228640.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.

예제 입력 1


3

1

0

예제 출력 1

? 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$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.