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 E10Bringing Order to Disorder</h2>11 12<p>13A sequence of digits usually represents a number, but we may define an alternative interpretation. In this problem we define a new interpretation with the order relation $\prec$ among the digit sequences of the same length defined below.14</p>15 16<p>17Let $s$ be a sequence of $n$ digits, $d_1d_2 ... d_n$, where each $d_i$ $(1 \leq i \leq n)$ is one of 0, 1, ... , and 9. Let sum($s$), prod($s$), and int($s$) be as follows:<br>18<br>19sum($s$) = $d_1 + d_2 + ... + d_n$<br>20prod($s$) = $(d_1 + 1) \times (d_2 + 1) \times  ... \times (d_n + 1)$<br>21int($s$) = $d_1 \times 10^{n-1} + d_2 \times 10^{n-2} + ... + d_n \times 10^0$<br>22<br>23 24int($s$) is the integer the digit sequence $s$ represents with normal decimal interpretation.25</p>26 27<p>28Let $s_1$ and $s_2$ be sequences of the same number of digits. Then $s_1 \prec s_2$ ($s_1$ is less than $s_2$) is satisfied if and only if one of the following conditions is satisfied.29</p>30 31<ol>32<li> sum($s_1$) $<$ sum($s_2$)</li>33<li> sum($s_1$) $=$ sum($s_2$) and prod($s_1$) $<$ prod($s_2$)</li>34<li> sum($s_1$) $=$ sum($s_2$), prod($s_1$) $=$ prod($s_2$), and int($s_1$) $<$ int($s_2$)</li>35</ol>36 37<p>38For 2-digit sequences, for instance, the following relations are satisfied.<br>39<br>40 41$00 \prec 01 \prec 10 \prec 02 \prec 20 \prec 11 \prec 03 \prec 30 \prec 12 \prec 21 \prec ... \prec 89 \prec 98 \prec 99$<br>42</p>43 44<p>45Your task is, given an $n$-digit sequence $s$, to count up the number of $n$-digit sequences that are less than $s$ in the order $\prec$ defined above.46</p>47 48 49<h3>Input</h3>50 51<p>52The input consists of a single test case in a line.<br>53<br>54$d_1d_2 ... d_n$<br>55<br>56 57$n$ is a positive integer at most 14. Each of $d_1, d_2, ...,$  and $d_n$ is a digit.58</p>59 60 61<h3>Output</h3>62 63<p>64Print the number of the $n$-digit sequences less than $d_1d_2 ... d_n$ in the order defined above.65</p>66 67 68<h3>Sample Input 1</h3>69 70<pre>20</pre>71 72<h3>Sample Output 1</h3>73 74<pre>4</pre>75 76 77 78<h3>Sample Input 2</h3>79 80<pre>020</pre>81 82<h3>Sample Output 2</h3>83 84<pre>5</pre>85 86 87 88<h3>Sample Input 3</h3>89 90<pre>118</pre>91 92<h3>Sample Output 3</h3>93 94<pre>245</pre>95 96 97 98 99<h3>Sample Input 4</h3>100 101<pre>11111111111111</pre>102 103<h3>Sample Output 4</h3>104 105<pre>40073759</pre>106 107 108 109<h3>Sample Input 5</h3>110 111<pre>99777222222211</pre>112 113<h3>Sample Output 5</h3>114 115<pre>23733362467675</pre>