codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.