1986D.md (2933B)
1 Source: https://codeforces.com/problemset/problem/1986/D 2 3 D. Mathematical Problem 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a string $s$ of length $n \gt 1$, consisting of digits from $0$ to $9$. You must insert exactly $n - 2$ symbols $+$ (addition) or $\times$ (multiplication) into this string to form a valid arithmetic expression. 22 23 In this problem, the symbols cannot be placed before the first or after the last character of the string $s$, and two symbols cannot be written consecutively. Also, note that the order of the digits in the string cannot be changed. Let's consider $s = 987009$: 24 25 * From this string, the following arithmetic expressions can be obtained: $9 \times 8 + 70 \times 0 + 9 = 81$, $98 \times 7 \times 0 + 0 \times 9 = 0$, $9 + 8 + 7 + 0 + 09 = 9 + 8 + 7 + 0 + 9 = 33$. Note that the number $09$ is considered valid and is simply transformed into $9$. 26 * From this string, the following arithmetic expressions cannot be obtained: $+9 \times 8 \times 70 + 09$ (symbols should only be placed between digits), $98 \times 70 + 0 + 9$ (since there are $6$ digits, there must be exactly $4$ symbols). 27 28 The result of the arithmetic expression is calculated according to the rules of mathematics — first all multiplication operations are performed, then addition. You need to find the minimum result that can be obtained by inserting exactly $n - 2$ addition or multiplication symbols into the given string $s$. 29 30 Input 31 32 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follows their description. 33 34 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 20$) — the length of the string $s$. 35 36 The second line of each test case contains a string $s$ of length $n$, consisting of digits from $0$ to $9$. 37 38 Output 39 40 For each test case, output the minimum result of the arithmetic expression that can be obtained by inserting exactly $n - 2$ addition or multiplication symbols into the given string. 41 42 Example 43 44 Input 45 46 ``` 47 18 48 49 2 50 51 10 52 53 2 54 55 74 56 57 2 58 59 00 60 61 2 62 63 01 64 65 3 66 67 901 68 69 3 70 71 101 72 73 5 74 75 23311 76 77 6 78 79 987009 80 81 7 82 83 1111111 84 85 20 86 87 99999999999999999999 88 89 20 90 91 00000000000000000000 92 93 4 94 95 0212 96 97 18 98 99 057235283621345395 100 101 4 102 103 1112 104 105 20 106 107 19811678487321784121 108 109 4 110 111 1121 112 113 4 114 115 2221 116 117 3 118 119 011 120 ``` 121 122 Output 123 124 ``` 125 10 126 74 127 0 128 1 129 9 130 1 131 19 132 0 133 11 134 261 135 0 136 0 137 0 138 12 139 93 140 12 141 24 142 0 143 ``` 144 145 Note 146 147 In the first four test cases, we cannot add symbols, so the answer will be the original number. 148 149 In the fifth test case, the optimal answer looks as follows: $9 \times 01 = 9 \times 1 = 9$. 150 151 In the sixth test case, the optimal answer looks as follows: $1 \times 01 = 1 \times 1 = 1$. 152 153 In the seventh test case, the optimal answer looks as follows: $2 + 3 + 3 + 11 = 19$. 154 155 In the eighth test case, one of the optimal answers looks as follows: $98 \times 7 \times 0 + 0 \times 9 = 0$.