МЦНМО 3184
(перенаправлено с «РОИ 2010-2011, региональный этап, D»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Похожие задачи
Комментарии
Пусть в строке y самый левый объект имеет координату xl, а самый правый — координату xr. Утверждается, что из-за того, что перемещения по вертикали возможны только в одном направлении, нам потребуется покрыть весь отрезок [xl; xr].
Состояние динамики будет включать координаты текущей клетки, а также маску из 2k бит, кодирующую покрытие k последних горизонталей: биты 2i и 2i + 1 отвечают за покрытие начала и конца i-го ряда.