Задача №115263. Устный счет
Отвлечемся от задач про программистов и перенесемся в совершенно обыкновенные ясли, где мальчик Вова (3 годика) практикуется в устном счете, а если точнее — в вычислении арифметических выражений по модулю \(10^9 + 7\).
Совсем недавно Вова придумал длинное и очень красивое арифметическое выражение. Выражение состяло из \(n\) целых неотрицательных чисел, меньших \(10^9 + 7\), и знаков сложения и умножения между ними. Первым же делом он вычислил это выражение по модулю \(10^9 + 7\), после чего выписал само выражение и результат на лист бумаги. Все числа он выписал без ведущих нулей.
Пока шел тихий час, Вова спал, а хулиганы стерли несколько цифр в выражении и заменили их на другие. Менять знаки или результат вычисления выражения хулиганы не решились, даже для них это слишком низко. Когда Вова проснулся, он обнаружил рядом с его листочком ластик и карандаш. У Вовы есть принципы — если хулиганы изменили не более двух цифр, то он их простит, иначе они будут наказаны по всей строгости ясельных законов.
К сожалению, чтобы понять, сколько цифр изменили хулиганы, Вове явно понадобится ваша помощь. Определите, могло ли данное выражение быть получено из верного равенства заменой не более двух цифр, и если да, то в каких числах и какие цифры были изменены.
Единственная строка входного файла содержит выражение, которое обнаружил Вова у себя на листке. Выражение состоит из двух частей, разеделенных знаком ' = '.
Первая часть содержит \(n\) целых неотрицательных чисел, разделенных знаками сложения (' + ') и умножения (' * ') (\(1 \le n \le 10^5\)). Вторая часть — целое неотрицательное число, означающее результат вычисления выражения.
Числа и все знаки разделяются одним пробелом. Гарантируется, что все числа строго меньше \(10^9 + 7\) и записаны без ведущих нулей.
В случае, если данное выражение не может быть получено из верного равенства заменой не более двух цифр, выведите « NO ».
В противном случае в первой строке выведите « YES ». На следующей строке выведите целое число \(k \leq 2\) — количество чисел , которые были изменены.
В следующих \(k\) строках выведите по два числа — позицию измененнного числа в выражении (от \(1\) до \(n\)) и его исходное значение.
Суммарно должно быть изменено не более двух цифр. В процессе замены в числах не должны появиться ведущие нули и числа должны остаться меньше \(10^9 + 7\). Если существует несколько вариантов ответа, выведите любой из них.
Баллы за поздадачи 1 – 6 начисляются только в случае, если все тесты соответствующей подзадачи и необходимых подзадач, а также тесты из условия, успешно пройдены.
Подзадача 7 оценивается потестово — всего в ней 25 тестов, каждый из которых независимо оценивается в 1 балл.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 7 | \(n \le 45\) | первая ошибка | |
2 | 13 | \(n \le 100\) | 1 | первая ошибка |
3 | 15 | все числа в выражении меньше \(10\) | первая ошибка | |
4 | 12 | нет операций умножения | первая ошибка | |
5 | 13 | нет операций сложения | первая ошибка | |
6 | 15 | все числа в выражении меньше \(10^5\) | 3 | первая ошибка |
7 | 25 | нет | 1 – 6 | потестовая оценка |
В подзадачах 3 и 6 ограничение касается только чисел слева от знака равенства, результат вычисления выражения может быть произвольным числом, меньшим \(10^9 + 7\).
56 + 14 * 86 + 51 * 55 = 3925
YES 1 3 76
97 + 14 * 31 * 76 + 99 * 73 = 40930
NO