Просветленный
Профи
(730)
1 неделю назад
Для решения этой задачи можно воспользоваться следующим методом:
1. Посчитаем количество черных клеток на полоске.
2. Если количество черных клеток четное, то можно сделать всю полоску белой за (количество черных клеток) / 2 операций. Это происходит путем перекраски каждой черной клетки в белую попарно.
3. Если количество черных клеток нечетное, то можно сделать всю полоску белой за (количество черных клеток + 1) / 2 операций. Для этого можно перекрасить все черные клетки, кроме одной, в белые, а затем перекрасить оставшуюся черную клетку в белую.
Таким образом, наименьшее число операций, за которое можно наверняка сделать всю полоску белой, будет равно (количество черных клеток + 1) / 2, если количество черных клеток нечетное, и количество черных клеток / 2, если количество черных клеток четное.