САМАЯ СЛОЖНАЯ ЗАДАЧА №24 ИЗ ЕГЭ ПО ИНФОРМАТИКЕ

• Основная волна ЕГЭ по информатике завершена, и в резерве появилась сложная задача.  

• Автор видео, сдававший экзамен, решил задачу с помощью неэффективного алгоритма.  

• Видео посвящено двум решениям задачи: простому и более сложному.  

• Задача заключается в выборе подстроки из арифметического выражения, значение которой равно нулю.  

• Автор предлагает сначала использовать переборный алгоритм, а затем более эффективное решение.  

• Функция eval преобразует строку выражения в понятный для интерпретатора вид.  

• Пример использования: строка "5 + 10 = 15" преобразуется в "5 + 10 = 15".  

• Функция отсутствует в некоторых языках, что делает переборное решение менее универсальным.  

• В строке не должно быть двух знаков плюс или умножения подряд.  

• Идея: разбить строку на подстроки, избегая запрещенных комбинаций.  

• Использование функции split для разбиения строки на подстроки.  

• Создание списка подстрок, избегая подстрок с запрещенными комбинациями.  

• Проверка всех возможных подстрок на соответствие условию.  

• Перебор всех возможных подстрок внутри строки.  

• Проверка значения арифметического выражения для каждой подстроки.  

• Исключение подстрок с недопустимыми знаками.  

• Проверка текущего символа на знак плюс или умножить.  

• Определение подстроки как части строки и накопление новой строки.  

• Расширение границ возможностей для поиска подходящей подстроки.  

• Форжин ренч используется для накопления строки слева направо.  

• Проверка на незначащие нули: если строка начинается с нуля, она не подходит.  

• Замена всех цифр на единички для упрощения проверки.  

• Проверка, что подстрока не заканчивается на знаки плюс или умножения.  

• Преобразование подстроки в арифметическое выражение и проверка на ноль.  

• Запись максимального значения в переменную.  

• Проверка подстрок длиной менее ста не имеет смысла.  

• Добавление проверки на длину подстроки больше накопленного значения.  

• Решение работает корректно на файлах с экзамена.  

• Идея Виктора Лашина для эффективного решения.  

• Замена подстрок с двумя плюсами или знаками умножения на двойные.  

• Разбиение подстрок по знакам плюс для проверки на ноль.  

• Примеры подстрок, которые не подходят из-за ненулевых значений.  

• Подстроки, которые подходят, имеют значение ноль.  

• Разбиение подстрок по знакам плюс для проверки на нулевые значения.  

• Проверка подстрок на нулевые значения и накопление.  

• Возможность сброса накопленных значений и начала с более оптимального варианта.  

• Конкатенация подстрок для получения длинной подстроки, которая является результатом.  

• Выражения могут быть различными, например, ноль на семьдесят два или просто семьдесят два.  

• В записи чисел отсутствуют ведущие нули.  

• Пример выражения: семьсот двадцать на сорок четыре.  

• Если в подстройке есть ноль умножить, то значение всей подстройки будет нулем.  

• Пример: ноль умножить на ноль равно нулю.  

• Можно найти позицию элемента ноль умножить и срезать все, что левее этой позиции.  

• Решение уже построено, осталось воплотить его в код.  

• Если подстрока равна нулю, её можно склеить с выражениями правее.  

• Пример: ноль плюс ноль плюс заменить на плюс и знак восклицания.  

• Если подстрока содержит знак плюс и ноль, её можно заменить на плюс и знак восклицания.  

• Пример: два умножить на ноль заменить на два умножить и знак восклицания.  

• Если в подстроке есть знак восклицания, она подходит.  

• Заменить ноль умножить на ноль умножить и знак восклицания.  

• Разбить строки по плюсам и склеить куски между плюсами.  

• Использовать метод split для разбиения по плюсам и удаления лишних знаков.  

• Разбить строки по плюсам для получения более мелких кусочков.  

• Склеивать подстроки, которые содержат ноль.  

• Пример: плюс это плюс это плюс это, где плюс это ноль, а остальное не ноль.  

• Введение понятий "фрагмент" и "подстрока".  

• Разбиение строки на фрагменты и подстроки.  

• Использование текущей длины для каждого фрагмента.  

• Если в фрагменте есть знак восклицательный, он считается нулевым.  

• Добавление плюса в конце фрагмента для учета склеивания.  

• Использование счетчика минус один для учета плюса в конце.  

• Если в подстроке нет знака восклицательного, но есть ноль умножить, можно обрезать лишние элементы.  

• Удаление лишних элементов и сохранение только тех, которые делают выражение нулевым.  

• Если подстрока заканчивается на ноль, можно начать с этого нуля.  

• В противном случае, если нет подходящих случаев, счетчик сбрасывается.  

• Подведение итогов и проверка решения.  

• Решение эффективно и сводится к линейной сложности.  

• Решение за линию, но требует много умственных усилий.  

• Проверка решения на тестах.  

• Решение работает без нареканий, но требует много времени и усилий.  

• Решение не рекомендуется для школьников, но полезно для профессионалов.  

• Создаем строку, используя рандомные символы из алфавита.  

• Длина строки должна быть от 5 до 100 символов.  

• Строка не должна содержать чисел с незначащими нулями.  

• Строка не должна начинаться с двух нулей или нуля и единицы.  

• Проверяем, что строка удовлетворяет условиям.  

• Если условие выполнено, делаем брейк.  

• Создаем функцию для неэффективного решения.  

• Проверяем, что эффективный алгоритм равен неэффективному.  

• Выводим строку и проверяем на тысячу тестов.  

• Эффективное решение выводит единицу, а неэффективное ноль.  

• Добавляем проверку, чтобы учитывать только выражения.  

• Пробуем запустить тысячу тестов, все успешно.  

• Запускаем сто тысяч тестов, решение работает корректно.  

• Решение сложное и требует много времени на отладку.  

• Решение универсальное и корректно обрабатывает все случаи.  

• Решение через конечный автомат и регулярные выражения.  

• Регулярные выражения не рекомендуются для ЕГЭ.  

• Решение через переборное решение подходит для сложных задач.  

• Решение сложное, но интересное и полезное.  

• Призываем учителей подумать о целесообразности использования регулярных выражений.  

• Желаем успешной подготовки к ЕГЭ по информатике.