Шеренга солдат
Есть задачи, «вкусные» для программирования. Например, такая.
N солдат, стоящие в шеренге, получили команду «нале-во!», но k из них ошибочно выполнили поворот направо. Далее каждую секунду пара солдат, стоящие лицом друг к другу поворачиваются на 180°.
Сколько секунд будет продолжаться движение?
Наверное, имеет значение расположение ошибившихся солдат в шеренге? Тогда, данных N и k недостаточно для описания начального условия задачи.
Похоже было, что соревнование выиграют русские. Все их батальоны уже заняли позиции по ту сторону поля. Под голубыми сводами июньского неба ряды солдат сомкнулись, образовав плотную стену с навесом из черных треуголок. Над головами русского воинства живописно реяли на ветру сотни знамен. Из небольших просветов между батальонами одноглазо обозревали равнину жерла 3-фунтовых пушек, которые были направлены в сторону видневшихся на горизонте рядов вражеской пехоты и всадников. Эта зеленая стена солдат, сверкающих штыков, пушек и необозримого леса пик и стягов растянулась более чем на две версты в длину и представляла собой по меньшей мере впечатляющее зрелище.
Это что-то вроде сортировки пузырьком. Только сравнение происходит параллельно. Движение будет продолжаться не более N секунд.
Можно еще улучшить: если направо повернулся только самый левый солдат, то этот «пузырек» будет всплывать N-1 секунду. Так что ограничение сверху еще более жесткое.
Если их двое, то самый левый в первую секунду ждет, а потом «всплывает» N-2 секунды (потому что он будет вторым справа — пузырек, конечно, не солдат). В итоге те же N-1.
Это можно экстраполировать и на произвольное расположение.
Итого, ответ: количество солдат между самым левым, смотрящим направо, и его антиподом, плюс одна секунда.
Можно еще подумать про случайную расстановку, но вроде бы ничего не меняется.
Число разворотов зависит не только от n и k, но и от взаимного расположения солдат. Их можно подсчитать так. Найдите первого справа солдата, смотрящего вправо, и посчитайте, сколько солдат отделяет его от правого края. Найдите второго солдата, смотрящего вправо, и посчитайте, сколько солдат отделяет его от второго места с правого края. И так для всех солдат, смотрящих вправо. Сумма переходов на свои места справа и есть общее число разворотов.