МЦНМО 3184

Ссылка на задачу

• МЦНМО #3184 — Космические исследования

Похожие задачи

• РОИ 2010-2011, региональный этап, D

Комментарии

Пусть в строке y самый левый объект имеет координату xl, а самый правый — координату xr. Утверждается, что из-за того, что перемещения по вертикали возможны только в одном направлении, нам потребуется покрыть весь отрезок [xl; xr].

Состояние динамики будет включать координаты текущей клетки, а также маску из 2k бит, кодирующую покрытие k последних горизонталей: биты 2i и 2i + 1 отвечают за покрытие начала и конца i-го ряда.