Litla borgin þar sem þú býrð áformar að taka upp nýtt kennitölukerfi almannatrygginga (SSN). Hver borgari verður auðkenndur með fimm stafa SSN-númeri. Fyrstu fjórir tölustafirnir gefa til kynna grunn-ID-númerið (0000–9999) og síðasti tölustafurinn er vartala til að greina villur.

Til að reikna út vartölur hefur borgin ákveðið að nota aðgerðatöflu. Aðgerðatafla er $10 \times 10$ tafla af tugakerfistölustöfum þar sem öll hornalínustökin eru $0$. Hér að neðan eru tvö dæmi um aðgerðatöflur.

Aðgerðatafla 1

Aðgerðatafla 2

Með aðgerðatöflu er vartalan $e$ fyrir fjögurra stafa grunn-ID-númer $abcd$ reiknuð með eftirfarandi formúlu. Hér táknar $i \otimes j$ stakið í töflunni í línu $i$ og dálki $j$.

$$e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$$

Til dæmis, ef notuð er Aðgerðatafla 1, er vartalan $e$ fyrir grunn-ID-númerið $abcd = 2016$ reiknuð á eftirfarandi hátt.

$$\begin{aligned} e &= (((0 \otimes 2) \otimes 0) \otimes 1) \otimes 6 \\ &= ((1 \otimes 0) \otimes 1) \otimes 6 \\ &= (7 \otimes 1) \otimes 6 \\ &= 9 \otimes 6 \\ &= 6 \end{aligned}$$

Þannig er SSN-númerið $20166$.

Athugið að vartalan fer eftir því hvaða aðgerðatafla er notuð. Með Aðgerðatöflu 2 fæst $e = 3$ fyrir sama grunn-ID-númer $2016$, og SSN-númerið í heild verður $20163$.

$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+vartala með Aðgerðatöflu 2} \\ 20163 & \\ \Downarrow & \; \text{mannleg mistök} \end{aligned} \\[6pt] \boxed{\begin{array}{c} \overbrace{\mathbf{0}0163 \quad \mathbf{1}0163 \quad \dots \quad \mathbf{9}0163 \quad 2\mathbf{1}163 \quad 2\mathbf{2}163 \quad \dots \quad 2016\mathbf{8} \quad 2016\mathbf{9}}^{\text{Breyting á einum tölustaf}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{Víxlun tveggja samliggjandi tölustafa}} \end{array}} \end{array}$$

Tilgangurinn með því að bæta við vartölunni er að greina mannleg mistök við skrif eða innslátt á SSN-númerum. Eftirfarandi fall check getur greint ákveðin mannleg mistök. Fyrir fimm stafa tölu $abcde$ er fallið check skilgreint sem hér segir.

$$\operatorname{check}(abcde) = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e$$

Þetta fall skilar $0$ fyrir rétt SSN-númer. Það er vegna þess að hvert hornalínustak í aðgerðatöflu er $0$ og fyrir rétt SSN-númer gildir $e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$:

$$\operatorname{check}(abcde) = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e = e \otimes e = 0.$$

Á hinn bóginn gefur gildi frábrugðið núlli frá check til kynna að gefna talan geti ekki verið rétt SSN-númer. Athugið að eftir því hvaða aðgerðatafla er notuð getur fallið check einnig skilað $0$ fyrir rangt SSN-númer. Hvaða tegundir mistaka greinast fer eftir aðgerðatöflunni sem notuð er; taflan ræður gæðum villugreiningarinnar.

Borgaryfirvöld vilja greina tvær tegundir algengra mannlegra mistaka í runum tölustafa: að breyta einum einstökum tölustaf og að víxla tveimur samliggjandi tölustöfum, eins og sýnt er á Mynd B.1.

Aðgerðatafla er góð ef hún getur greint öll algeng mistök af báðum þessum tegundum í öllum SSN-númerum sem mynduð eru úr fjögurra stafa grunn-ID-númerunum 0000–9999. Athugið að greina þarf mistök í vartölunni jafnt sem í grunn-ID-tölustöfunum fjórum. Til dæmis er Aðgerðatafla 1 góð. Aðgerðatafla 2 er ekki góð vegna þess að fyrir $20613$, sem fæst með því að víxla 3. og 4. tölustaf rétts SSN-númers $20163$, er $\operatorname{check}(20613)$ jafnt og $0$. Raunar getur Aðgerðatafla 2, af $10000$ grunn-ID-númerum, ekki greint eitt eða fleiri algeng mistök fyrir allt að $3439$ grunn-ID-númer.

Fyrir gefna aðgerðatöflu skal ákvarða hversu góð hún er með því að telja fjölda grunn-ID-númera sem gefna taflan getur ekki greint eitt eða fleiri algeng mistök fyrir.

Inntak

Inntakið samanstendur af einu prófunartilviki á eftirfarandi sniði.

$$\begin{array}{cccc} x_{00} & x_{01} & \cdots & x_{09} \\ \vdots & & & \\ x_{90} & x_{91} & \cdots & x_{99} \end{array}$$

Inntakið lýsir aðgerðatöflu þar sem $x_{ij}$ er tugakerfistölustafurinn í línu $i$ og dálki $j$. Hver lína í inntakinu samsvarar einni línu í töflunni, þar sem stökin eru aðskilin með einu bili. Hornalínustökin $x_{ii}$ ($i = 0, \ldots, 9$) eru alltaf $0$.

Úttak

Skrifið út fjölda grunn-ID-númera sem gefna taflan getur ekki greint eitt eða fleiri algeng mannleg mistök fyrir.

Dæmi

Inntak 1

0 3 1 7 5 9 8 6 4 2
7 0 9 2 1 5 4 8 6 3
4 2 0 6 8 7 1 3 5 9
1 7 5 0 9 8 3 4 2 6
6 1 2 3 0 4 5 9 7 8
3 6 7 4 2 0 9 5 8 1
5 8 6 9 7 2 0 1 3 4
8 9 4 5 3 6 2 0 1 7
9 4 3 8 6 1 7 2 0 5
2 5 8 1 4 3 6 7 9 0

Úttak 1

0

Inntak 2

0 1 2 3 4 5 6 7 8 9
9 0 1 2 3 4 5 6 7 8
8 9 0 1 2 3 4 5 6 7
7 8 9 0 1 2 3 4 5 6
6 7 8 9 0 1 2 3 4 5
5 6 7 8 9 0 1 2 3 4
4 5 6 7 8 9 0 1 2 3
3 4 5 6 7 8 9 0 1 2
2 3 4 5 6 7 8 9 0 1
1 2 3 4 5 6 7 8 9 0

Úttak 2

3439

Inntak 3

0 9 8 7 6 5 4 3 2 1
1 0 9 8 7 6 5 4 3 2
2 1 0 9 8 7 6 5 4 3
3 2 1 0 9 8 7 6 5 4
4 3 2 1 0 9 8 7 6 5
5 4 3 2 1 0 9 8 7 6
6 5 4 3 2 1 0 9 8 7
7 6 5 4 3 2 1 0 9 8
8 7 6 5 4 3 2 1 0 9
9 8 7 6 5 4 3 2 1 0

Úttak 3

9995

Inntak 4

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Úttak 4

10000