|
|
 |
Условие
Имеется полоска 1×99, разбитая на 99 клеток 1×1, которые раскрашены через одну в чёрный и белый цвет. Разрешается перекрашивать одновременно все клетки любого клетчатого прямоугольника 1×k. За какое наименьшее число перекрашиваний можно сделать всю полоску одноцветной?
Подсказка
Каждое перекрашивание разрушает не более двух границ между клетками разных цветов.
Решение
Оценка. Назовём перемычкой отрезок, разделяющий две клетки разных цветов. В начале у нас имеется 98 перемычек. Каждое перекрашивание изменяет число перемычек не более чем на 2. Значит, 48 перекрашиваний не хватит.
Алгоритм. Перекрасим все клетки со второй по 98-ю, затем все клетки с третьей по 97-ю, ..., наконец, одну 50-ю клетку. После этого полоска станет одноцветной.
Ответ
За 49 перекрашиваний.
Источники и прецеденты использования
| web-сайт | |
| задача |
