Pieni kaupunki, jossa asut, suunnittelee uuden sosiaaliturvatunnusjärjestelmän (SSN) käyttöönottoa. Jokainen kaupunkilainen tunnistetaan viisinumeroisella SSN-tunnuksella. Sen neljä ensimmäistä numeroa ilmaisevat perus-ID-numeron (0000–9999), ja viimeinen numero on virheiden havaitsemiseen tarkoitettu tarkistusnumero.
Tarkistusnumeroiden laskemiseksi kaupunki on päättänyt käyttää laskutoimitustaulua. Laskutoimitustaulu on kymmenjärjestelmän numeroista koostuva $10 \times 10$ -taulu, jonka kaikki lävistäjäalkiot ovat $0$. Alla on kaksi esimerkkitaulua.
Laskutoimitustaulu 1
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | |
|---|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $3$ | $1$ | $7$ | $5$ | $9$ | $8$ | $6$ | $4$ | $2$ |
| $1$ | $7$ | $0$ | $9$ | $2$ | $1$ | $5$ | $4$ | $8$ | $6$ | $3$ |
| $2$ | $4$ | $2$ | $0$ | $6$ | $8$ | $7$ | $1$ | $3$ | $5$ | $9$ |
| $3$ | $1$ | $7$ | $5$ | $0$ | $9$ | $8$ | $3$ | $4$ | $2$ | $6$ |
| $4$ | $6$ | $1$ | $2$ | $3$ | $0$ | $4$ | $5$ | $9$ | $7$ | $8$ |
| $5$ | $3$ | $6$ | $7$ | $4$ | $2$ | $0$ | $9$ | $5$ | $8$ | $1$ |
| $6$ | $5$ | $8$ | $6$ | $9$ | $7$ | $2$ | $0$ | $1$ | $3$ | $4$ |
| $7$ | $8$ | $9$ | $4$ | $5$ | $3$ | $6$ | $2$ | $0$ | $1$ | $7$ |
| $8$ | $9$ | $4$ | $3$ | $8$ | $6$ | $1$ | $7$ | $2$ | $0$ | $5$ |
| $9$ | $2$ | $5$ | $8$ | $1$ | $4$ | $3$ | $6$ | $7$ | $9$ | $0$ |
Laskutoimitustaulu 2
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | |
|---|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ |
| $1$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
| $2$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
| $3$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $4$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
| $5$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ |
| $6$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ |
| $7$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ |
| $8$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ |
| $9$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ |
Laskutoimitustaulua käyttäen nelinumeroisen perus-ID-numeron $abcd$ tarkistusnumero $e$ lasketaan seuraavalla kaavalla. Tässä $i \otimes j$ tarkoittaa taulun rivillä $i$ ja sarakkeessa $j$ olevaa alkiota.
$$e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$$
Esimerkiksi Laskutoimitustaulua 1 käytettäessä perus-ID-numeron $abcd = 2016$ tarkistusnumero $e$ lasketaan seuraavasti.
$$\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}$$
Näin ollen SSN on $20166$.
Huomaa, että tarkistusnumero riippuu käytetystä laskutoimitustaulusta. Laskutoimitustaulua 2 käytettäessä samalle perus-ID-numerolle $2016$ saadaan $e = 3$, jolloin koko SSN on $20163$.
$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+tarkistusnumero Laskutoimitustaululla 2} \\ 20163 & \\ \Downarrow & \; \text{inhimilliset virheet} \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{Yhden numeron muuttuminen}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{Kahden vierekkäisen numeron vaihtuminen keskenään}} \end{array}} \end{array}$$
Kuva B.1. Kahdenlaisia yleisiä inhimillisiä virheitä
Tarkistusnumeron lisäämisen tarkoituksena on havaita inhimilliset virheet SSN-tunnuksia kirjoitettaessa tai näppäiltäessä. Seuraava check-funktio pystyy havaitsemaan tiettyjä inhimillisiä virheitä. Viisinumeroiselle luvulle $abcde$ funktio check määritellään seuraavasti.
$$\operatorname{check}(abcde) = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e$$
Tämä funktio palauttaa arvon $0$ virheettömälle SSN-tunnukselle. Tämä johtuu siitä, että laskutoimitustaulun jokainen lävistäjäalkio on $0$ ja virheettömälle SSN-tunnukselle pätee $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.$$
Toisaalta funktion check palauttama nollasta poikkeava arvo osoittaa, ettei annettu luku voi olla virheetön SSN. Huomaa, että käytetystä laskutoimitustaulusta riippuen funktio check saattaa palauttaa arvon $0$ myös virheelliselle SSN-tunnukselle. Se, millaisia virheitä havaitaan, riippuu käytetystä laskutoimitustaulusta; taulu määrää virheiden havaitsemisen laadun.
Kaupungin viranomaiset haluavat havaita kahdenlaisia yleisiä inhimillisiä virheitä numerosarjoissa: yhden yksittäisen numeron muuttumisen sekä kahden vierekkäisen numeron vaihtumisen keskenään, kuten kuvassa B.1 on esitetty.
Laskutoimitustaulu on hyvä, jos se pystyy havaitsemaan kaikki molempien tyyppien yleiset virheet kaikissa nelinumeroisista perus-ID-numeroista 0000–9999 muodostetuissa SSN-tunnuksissa. Huomaa, että tarkistusnumerossa tapahtuvat virheet on havaittava siinä missä neljässä perus-ID-numerossakin tapahtuvat virheet. Esimerkiksi Laskutoimitustaulu 1 on hyvä. Laskutoimitustaulu 2 ei ole hyvä, koska luvulle $20613$, joka saadaan vaihtamalla virheettömän SSN-tunnuksen $20163$ kolmas ja neljäs numero keskenään, $\operatorname{check}(20613)$ on $0$. Itse asiassa $10000$ perus-ID-numeron joukosta Laskutoimitustaulu 2 jää havaitsematta yhden tai useamman yleisen virheen peräti $3439$ perus-ID-numeron kohdalla.
Annetulle laskutoimitustaululle päättele, kuinka hyvä se on, laskemalla niiden perus-ID-numeroiden lukumäärä, joiden kohdalla annettu taulu ei pysty havaitsemaan yhtä tai useampaa yleistä virhettä.
Syöte
Syöte koostuu yhdestä testitapauksesta seuraavassa muodossa.
$$\begin{array}{cccc} x_{00} & x_{01} & \cdots & x_{09} \\ \vdots & & & \\ x_{90} & x_{91} & \cdots & x_{99} \end{array}$$
Syöte kuvaa laskutoimitustaulun, jossa $x_{ij}$ on rivillä $i$ ja sarakkeessa $j$ oleva kymmenjärjestelmän numero. Jokainen syötteen rivi vastaa yhtä taulun riviä, ja rivin alkiot on erotettu toisistaan yhdellä välilyönnillä. Lävistäjäalkiot $x_{ii}$ ($i = 0, \ldots, 9$) ovat aina $0$.
Tuloste
Tulosta niiden perus-ID-numeroiden lukumäärä, joiden kohdalla annettu taulu ei pysty havaitsemaan yhtä tai useampaa yleistä inhimillistä virhettä.
Esimerkit
Syöte 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
Tuloste 1
0
Syöte 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
Tuloste 2
3439
Syöte 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
Tuloste 3
9995
Syöte 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
Tuloste 4
10000