Проверка равенств без скобок для длинных чисел — олимпиадная задача
Задача
Во входном файле записано равенство вида A = B, где A и B – это выражения, содержащие сколь угодно длинные целые числа и знаки операций +, - (бинарный и унарный) и *. Выражения не содержат скобок. Требуется проверить выполнение заданного равенства и вывести в выходной файл результат проверки в форме «Да, выполняется» или «Нет, не выполняется». Длина входного файла данных не превосходит 60 килобайт. Числа и знаки операций в выражении могут разделяться пробелами и/или символами перевода строки. Пример входного файла 2
- 43 = 86 Пример выходного файла Да, выполняется
Решение
Скачатьархив тестов и решений
Поскольку в результате вычислений могут получаться очень большие числа, то точно подсчитать значение каждого из выражений A и B за отведенное для работы программы время нереально. Однако относительно легко сравнить левую и правую части по какому-то модулю. Если провести такую проверку для достаточно большого набора взаимно простых модулей, то можно с большой вероятностью дать правильный ответ.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь