Задача
В строку выписаны 40 знаков: 20 крестиков и 20 ноликов. За один ход можно поменять местами любые два соседних знака. За какое наименьшее количество ходов можно гарантированно добиться того, чтобы какие-то 20 стоящих подряд знаков оказались крестиками?
Решение
Для того чтобы 20 крестиков стояли подряд, необходимо и достаточно, чтобы все нолики стояли с краев (возможно, все с одного края).
Оценка. Пусть есть строка с произвольной расстановкой крестиков и ноликов. Будем делать разрешённые ходы, перемещая нолики к правому или к левому краю так, чтобы правее или левее них уже не было крестиков.
Для этого сначала выберем самый правый и самый левый нолики. Для того чтобы один из них оказался с краю, требуется не более 10 ходов, так как либо слева от самого левого, либо справа от самого правого нолика стоит не более, чем 10 крестиков.
Далее, возьмём самый правый и самый левый нолик из оставшихся 19. Рассуждая аналогично, получим, что для указанного перемещения опять потребуется не более 10 ходов, и так далее. Таким образом, для получения требуемой расстановки потребуется не более 20·10 = 200 ходов.
Приведём пример изначальной расстановки для случая, когда меньшего количества ходов не хватит. Пусть в ряд стоят 10 крестиков, затем 20 ноликов, а затем еще 10 крестиков. В этом случае для перемещения каждого нолика к краю потребуется ровно 10 ходов.
Ответ
За 200 ходов.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь