|
|
 |
Условие
В каждой клетке полоски длины 100 стоит по фишке. Можно за 1 рубль поменять местами любые две соседние фишки, а также можно бесплатно поменять местами любые две фишки, между которыми стоят ровно 4 фишки. За какое наименьшее количество рублей можно переставить фишки в обратном порядке?
Решение
Занумеруем фишки и клетки по порядку от 0 до 99. Бесплатная операция не меняет остаток номера клетки при делении на 5.
Оценка. Мысленно расположим кучки фишек по кругу. Сначала кучка фишек с остатком 0, потом – с 1, и так далее до 4. Платная операция переставляет пару фишек из соседних кучек. Фишки из нулевой кучки должны участвовать хотя бы в одной такой замене, чтобы добраться до четвёртой кучки. Аналогично для фишек из четвёртой кучки. Фишки из первой кучки должны участвовать хотя бы в двух заменах, чтобы добраться до третьей кучки. Аналогично для третьей кучки. Значит, потребуется хотя бы (20 + 20 + 40 + 40):2 = 60 рублей. Но если будет потрачено только 60 рублей, то фишкам из первой кучки придётся идти через вторую кучку, поэтому хотя бы одна фишка из второй кучки будет участвовать в заменах. Следовательно, необходимо больше 60 рублей.
Алгоритм. Ясно, что бесплатными операциями можно расставить фишки внутри кучки в любом порядке. Поэтому правильно расставить все фишки из нулевой и четвёртой кучек можно за 20 рублей. Рассмотрим оставшиеся три кучки. Мысленно оставим только одну фишку $A$ во второй кучке. Поменяем её с фишкой из первой кучки. Каждый раз будем передвигать дальше фишку, пришедшую во вторую кучку, за счёт новой фишки. Тогда за 40 рублей мы перетащим все фишки из первой кучки в третью, а из третьей – в первую кроме одной: она останется во второй кучке, не дойдя до первой. Поменяем её с $A$, и все фишки окажутся в нужных кучках.
Ответ
За 61 рубль.
Замечания
5 баллов
