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