Codeforces Round 954 (Div. 3) |
---|
Закончено |
Вам дана строка $$$s$$$ длины $$$n > 1$$$, состоящая из цифр от $$$0$$$ до $$$9$$$. Вы должны вставить в эту строку ровно $$$n - 2$$$ знака $$$+$$$ (сложение) или $$$\times$$$ (умножение), чтобы получилось корректное арифметическое выражение.
В этой задаче нельзя, чтобы знаки были перед первым или после последнего символа строки $$$s$$$, а также не может быть записано два каких-либо знака подряд. Также обращаем ваше внимание на то, что вы не меняете порядок цифр в строке. Рассмотрим $$$s = 987009$$$:
Результат математического выражения считается по правилам математики — сначала выполняются все операции умножения, затем сложения. Вам нужно найти минимальный результат, который можно получить, вставив в данную строку $$$s$$$ ровно $$$n - 2$$$ знака сложения или умножения.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 20$$$) — длина строки $$$s$$$.
Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из цифр от $$$0$$$ до $$$9$$$.
Для каждого набора входных данных выведите минимальный результат математического выражения, который можно получить, вставив в данную строку ровно $$$n - 2$$$ знака сложения или умножения.
182102742002013901310152331169870097111111120999999999999999999992000000000000000000000402121805723528362134539541112201981167848732178412141121422213011
10 74 0 1 9 1 19 0 11 261 0 0 0 12 93 12 24 0
В первых четырех наборах входных данных мы не можем добавлять знаки, поэтому ответом будет исходное число.
В пятом наборе входных данных оптимальный ответ выглядит следующим образом $$$9 \times 01 = 9 \times 1 = 9$$$.
В шестом наборе входных данных оптимальный ответ выглядит следующим образом $$$1 \times 01 = 1 \times 1 = 1$$$.
В седьмом наборе входных данных оптимальный ответ выглядит следующим образом $$$2 + 3 + 3 + 11 = 19$$$.
В восьмом наборе входных данных один из оптимальных ответов выглядит следующим образом $$$98 \times 7 \times 0 + 0 \times 9 = 0$$$.
Название |
---|