prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8 9<h2>Problem B10Quality of Check Digits11</h2>12 13<p>14The small city where you live plans to introduce a new social security number (SSN) system. Each citizen will be identified by a five-digit SSN. Its first four digits indicate the basic ID number (0000 - 9999) and the last one digit is a <i>check digit</i> for detecting errors.15</p>16 17<p>18For computing check digits, the city has decided to use an operation table. An operation table is a 10 $\times$ 10 table of decimal digits whose diagonal elements are all 0. Below are two example operation tables.19</p>20 21<center>22<table>23<tr>24<td>25Operation Table 126</td>27<td>&nbsp;&nbsp;&nbsp;&nbsp;</td>28<td>29Operation Table 230</td>31</tr>32<tr>33<td>34<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2016_Table_B1">35</td>36<td>&nbsp;&nbsp;&nbsp;&nbsp;</td>37<td>38<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2016_Table_B2">39</td>40</tr>41</table>42</center>43<br/>44 45<p>46Using an operation table, the check digit $e$ for a four-digit basic ID number $abcd$ is computed by using the following formula. Here, $i \otimes47 j$ denotes the table element at row $i$ and column $j$.<br/>48<br/>49 50$e = (((0 \otimes a) \otimes  b) \otimes c) \otimes d$51 52<br/><br/>53 54For example, by using Operation Table 1 the check digit $e$ for a basic ID number $abcd = $ 2016 is computed in the following way.<br/>55<br/>56 57$e = (((0 \otimes 2) \otimes 0) \otimes 1) \otimes 6$<br/>58$\;\;\;  = (( \;\;\;\;\;\;\;\;\;  1 \otimes 0) \otimes 1) \otimes 6$<br/>59$\;\;\;  = ( \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; 7 \otimes 1) \otimes 6$<br/>60$\;\;\;  =  \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; 9 \otimes 6$<br/>61$\;\;\;  =  \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  6$<br/>62<br/>63 64Thus, the SSN is 20166.65</p>66 67<p>68Note that the check digit depends on the operation table used. With Operation Table 2, we have $e = $ 3 for the same basic ID number 2016, and the whole SSN will be 20163.69</p>70 71 72<center>73<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2016_Figure_B1"><br/>74Figure B.1. Two kinds of common human errors75</center><br/>76 77<p>78The purpose of adding the check digit is to detect human errors in writing/typing SSNs. The following <span>check</span> function can detect certain human errors. For a five-digit number $abcde$, the check function is defined as follows.79</p>80 81<center>82<span>check</span>($abcde$) $ = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e$<br/>83</center>84<br/>85 86<p>87This function returns 0 for a correct SSN. This is because every diagonal element in an operation table is 0 and for a correct SSN we have $e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$:<br/>88</p>89 90<center>91<span>check</span>($abcde$) $ = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e = e \otimes e = 0$<br/>92</center>93<br/>94 95<p>96On the other hand, a non-zero value returned by check indicates that the given number cannot be a correct SSN. Note that, depending on the operation table used, check function may return 0 for an incorrect SSN. Kinds of errors detected depends on the operation table used; the table decides the quality of error detection.97</p>98 99<p>100The city authority wants to detect two kinds of common human errors on digit sequences: altering one single digit and transposing two adjacent digits, as shown in Figure B.1. 101</p>102 103<p>104An operation table is good if it can detect all the common errors of the two kinds on all SSNs made from four-digit basic ID numbers 0000{9999. Note that errors with the check digit, as well as with four basic ID digits, should be detected. For example, Operation Table 1 is good. Operation Table 2 is not good because, for 20613, which is a number obtained by transposing the 3rd and the 4th digits of a correct SSN 20163, <span>check</span>(20613) is 0. Actually, among 10000 basic ID numbers, Operation Table 2 cannot detect one or more common errors for as many as 3439 basic ID numbers.105</p>106 107<p>108Given an operation table, decide how good it is by counting the number of basic ID numbers for which the given table cannot detect one or more common errors.109</p>110 111 112 113 114 115 116 117 118<h3>Input</h3>119 120<p>121The input consists of a single test case of the following format.<br/>122<br/>123$x_{00}$ $x_{01}$ ... $x_{09}$<br/>124...<br/>125$x_{90}$ $x_{91}$ ... $x_{99}$<br/>126</p>127 128<p>129The input describes an operation table with $x_{ij}$ being the decimal digit at row $i$ and column $j$. Each line corresponds to a row of the table, in which elements are separated by a single space. The diagonal elements $x_{ii}$ ($i = 0, ... , 9$) are always 0.130</p>131 132 133 134<h3>Output</h3>135 136<p>137Output the number of basic ID numbers for which the given table cannot detect one or more common human errors.138</p>139 140 141 142<h3>Sample Input 1</h3>143 144<pre>0 3 1 7 5 9 8 6 4 21457 0 9 2 1 5 4 8 6 31464 2 0 6 8 7 1 3 5 91471 7 5 0 9 8 3 4 2 61486 1 2 3 0 4 5 9 7 81493 6 7 4 2 0 9 5 8 11505 8 6 9 7 2 0 1 3 41518 9 4 5 3 6 2 0 1 71529 4 3 8 6 1 7 2 0 51532 5 8 1 4 3 6 7 9 0</pre>154 155<h3>Sample Output 1</h3>156 157<pre>0</pre>158 159<br/>160 161<h3>Sample Input 2</h3>162 163<pre>0 1 2 3 4 5 6 7 8 91649 0 1 2 3 4 5 6 7 81658 9 0 1 2 3 4 5 6 71667 8 9 0 1 2 3 4 5 61676 7 8 9 0 1 2 3 4 51685 6 7 8 9 0 1 2 3 41694 5 6 7 8 9 0 1 2 31703 4 5 6 7 8 9 0 1 21712 3 4 5 6 7 8 9 0 11721 2 3 4 5 6 7 8 9 0</pre>173 174<h3>Sample Output 2</h3>175 176<pre>3439</pre>177 178<br/>179 180<h3>Sample Input 3</h3>181 182<pre>0 9 8 7 6 5 4 3 2 11831 0 9 8 7 6 5 4 3 21842 1 0 9 8 7 6 5 4 31853 2 1 0 9 8 7 6 5 41864 3 2 1 0 9 8 7 6 51875 4 3 2 1 0 9 8 7 61886 5 4 3 2 1 0 9 8 71897 6 5 4 3 2 1 0 9 81908 7 6 5 4 3 2 1 0 91919 8 7 6 5 4 3 2 1 0</pre>192 193<h3>Sample Output 3</h3>194 195<pre>9995</pre>196 197<br/>198 199<h3>Sample Input 4</h3>200 201<pre>0 0 0 0 0 0 0 0 0 02020 0 0 0 0 0 0 0 0 02030 0 0 0 0 0 0 0 0 02040 0 0 0 0 0 0 0 0 02050 0 0 0 0 0 0 0 0 02060 0 0 0 0 0 0 0 0 02070 0 0 0 0 0 0 0 0 02080 0 0 0 0 0 0 0 0 02090 0 0 0 0 0 0 0 0 02100 0 0 0 0 0 0 0 0 0</pre>211 212<h3>Sample Output 4</h3>213 214<pre>10000</pre>215 216 217 218