Скобки на калькуляторе
На экране старого калькулятора выражение из однозначных чисел и знаков +, − и ×. Скобок нет, и калькулятор считает как положено: 7 − 3 × 2 − 4 × 5 = −19. Вы можете расставить скобки как угодно — порядок чисел и знаков при этом не меняется, а минус по-прежнему только вычитает. Какое наибольшее значение можно получить?
Для этого выражения ответ 65: (7 − 3 × (2 − 4)) × 5. Обратите внимание на середину: чтобы результат был наибольшим, кусок 3 × (2 − 4) должен стать как можно меньше.
Вход
Одна строка без пробелов: цифры от 0 до 9, между соседними цифрами — один знак +, - или *. Цифр от 1 до 15.
Выход
Одно целое число — наибольшее значение выражения при какой-нибудь расстановке скобок.
Примеры
Пример 1
7-3*2-4*5
65
Пример 2
1-9*9-9
1
Ограничения
- Время · Python
- 2000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 13 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Последнее действие при какой-то расстановке скобок делит выражение на левый и правый кусок, и каждый из них вычисляется со своими скобками. Какие куски получаются и сколько их всего?
2Подсказка 2
Чтобы получить наибольшее A − B, правый кусок B должен быть как можно меньше. А произведение двух очень отрицательных чисел — очень положительное. Что тогда хранить для каждого куска?
3Идея
Для каждого куска цифр от i до j храним два числа: наименьшее и наибольшее значение, какое он может принять при какой-нибудь расстановке скобок. Последнее действие делит кусок по какому-то знаку k, и его результат — a op b, где a — значение левой части, b — правой. Для +, − и × экстремум выражения a op b всегда достигается, когда a и b сами экстремальны, поэтому хватает перебрать четыре сочетания «наименьшее или наибольшее слева и справа».
4Разбор
Почему четырёх сочетаний достаточно: при фиксированном знаке выражение a + b, a − b или a · b монотонно по каждому аргументу при фиксированном другом — сложение и вычитание всегда, умножение в зависимости от знака второго множителя. Значит, наибольшее и наименьшее значения достигаются на концах отрезков [lo, hi] обеих частей.
Куски считаем по возрастанию длины — это динамика на отрезках. В первом примере наибольшее значение 65 = (7 − 3 × (2 − 4)) × 5 получается так: для куска «3 × 2 − 4» нужен минимум, −6, его вычитают из 7 и получают 13, а потом умножают на 5. Решение, которое хранит только максимумы, берёт у этого куска максимум 2 и проигрывает.
4+Решение
5Сложность
O(n³) для n цифр: кусков O(n²), у каждого O(n) вариантов последнего действия. Числа помещаются в 64 бита: по модулю значение не больше произведения (di + 1) по всем цифрам, а это меньше 1015.
6Типичные ошибки
- Только максимум куска. Не проходит первый пример: вычитание и умножение отрицательных хотят от части минимум.
- Жадные скобки. «Сначала все плюсы» или «сначала все умножения» — не всегда лучше: во втором примере ответ даёт скобка (9 − 9), которая обнуляет произведение.
- Перебор всех расстановок. Их число Каталана: для 15 цифр — 2 674 440 вариантов, и у каждого своё дерево вычисления; без таблицы кусков это слишком долго.