Какие задачи дают в полуфинале Yandex Cup

Альбина продолжает свой путь на Yandex Cup 2024 и в этот раз она снова попытается пройти на финальный этап в Ташкенте. Получилось это или нет - смотрите в ролике.
Актуальные вакансии: technokratos.c...
Подписка на канал: t.me/+yQC-SASH...
#python #yandexcup #программирование

[@igorglushatov1948]

Да, тут действительно O(k), так как размер стены константен, а алгоритм обработки этой стены не пробегает по клеткам больше двух раз. Жаль в видео не было объяснено, почему собственно алгоритм работает. Нужно бы подчеркнуть, что жадное размещение свитков гарантирует оптимальность и правильность, если мы начинаем с левого верхнего угла.
P.S. мы действительно можем скипать уже рассмотренные клетки, не обнуляя те, на которые свиток был помещён, а записывая 8+смещение на следующую необработанную ячейку. Таким образом диапазон [1; 8] будет означать тип клетки, в которую свиток не был помещён, а [9; 15] посещённую клетку со смещением, однако для этой задачи это бессмысленная оптимизация, так как свитки слишком маленькие