|
Zuma
(Время: 3 сек. Память: 64 Мб Сложность: 60%)
Возможно, некоторым из вас знакома игра Zuma о приключениях лягушки. В данной задаче правила похожи и довольно просты: в каменном жёлобе находится ряд разноцветных шаров; пушка, расположившаяся рядом с жёлобом, имеет некоторый запас разноцветных шаров и периодически закидывает их в желоб. Заброшенные шары встраиваются в ряд. Если после выстрела в желобе образуется непрерывная последовательность из трех или более шаров одного цвета, включающая заброшенный шар, то они исчезают, а соседние шары сдвигаются, смыкая ряд. Если после исчезновения шаров в месте стыка присутствуют соседние шары (как слева, так и справа), образующие непрерывную последовательность из трех или более шаров одного цвета, то они также исчезают, и так далее. Цель игры – уничтожить все шары.
| Этап | Рисунок | Пояснение |
|---|
| 1 |  | Выстреливается новый шар «B», в позицию после шара №1 |
| 2 |  | После выстрела новый шар образует с соседними последовательность цвета «B», в позициях 2-5. Длина последовательности ≥3, поэтому шары 2-5 исчезнут |
| 3 |  | Оставшиеся шары займут позиции 1-3, и поскольку новая последовательность цвета «А» длины ≥3, она тоже исчезнет |
Пронумеруем шары слева направо, начиная с единицы. Выстрел шара в позицию n означает, что он появится правее шара с номером n и окажется в позиции n+1. Номера шаров, расположенных правее прилетевшего шара, увеличиваются на единицу. Приземление шара левее всего ряда обозначается позицией с номером 0. После исчезновения некоторых шаров, шары в желобе нумеруются заново слева направо, начиная с единицы.
Требуется написать программу, определяющую оптимальную стратегию стрельбы. Оптимальной стратегией называется та, при которой наименьшее количество выстрелов приводит к исчезновению всех шаров.
Входные данные
Входной файл INPUT.TXT содержит описание ряда шаров, цвет каждого шара описывается заглавной буквой английского алфавита (A..Z). Известно, что длина ряда не превышает 14 шаров, а для уничтожения ряда требуется не более 10 выстрелов, если следовать оптимальной стратегии.
Выходные данные
В выходной файл OUTPUT.TXT выведите строку: сначала минимальное количество выстрелов, затем через пробел пары буква-число: цвет шара и позицию выстрела. Выстрелы в ответе должны быть перечислены в порядке их следования в игре. В случае наличия нескольких оптимальных стратегий выберите любую.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | ABBBAA | 1 B1 |
| 2 | ACMNEERC | 10 A0 A0 C0 M2 M2 N2 N2 E2 R2 R2 |
| 3 | BAAA | 3 B0 B0 A0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
