На сайте acmp.ru добавились 300 новых задач, и сейчас самое время их решить.
Очень интересная задача. Одно условие чего стоит! Оно даёт введение в булеву алгебру, если вдруг раньше не приходилось иметь с ней дела (но это, правда, вряд ли).
Итак, нужно максимизировать количество единичек. Воспользуемся методом динамического программирования. Состоянием динамики будет пара: сколько операций уже сделали и какой результат (0 или 1). Значение - количество единичек. А переходов два: поставить 0 и поставить 1. Или меньше, так как заданная булева функция накладывает ограничения. Рассмотрим получившуюся таблицу на первом примере:
Но в этой задаче надо восстановить и саму последовательность. И есть два способа:
- для каждой клетки запоминать a и b, при которых получилось максимальное значение, и тогда с помощью этих значений можно будет сделать обратный ход, выписывая значения b,
- ничего дополнительного не запоминать, а при обратном ходе снова вычислять лучшие a и b.
В решении ниже реализован второй вариант:
Но это решение не проходит по памяти на сайте. Замечу, что эта задача с регионального этапа Всероссийской олимпиады школьников по информатике, а там ограничения по памяти были сильно слабее, это решение зашло. Если решение переписать на С++, то тоже всё будет хорошо, даже с такими суровыми ограничениями.
Но мы поступим по-другому. Достаточно сделать несколько запусков программы и заметить, что ответы очень часто повторяются и не отличаются разнообразием. К тому же и булевых функций всего 16, поэтому можно попробовать на всех. В итоге получается такая таблица с ответами:
А отсюда уже получается простое решение с разбором всех случаев:
Такая чудесная цепочка решений может иногда получаться.
Предыдущий выпуск: Задача 712. Дипломы
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.