Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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.TXTOUTPUT.TXT
1ABBBAA1 B1
2ACMNEERC10 A0 A0 C0 M2 M2 N2 N2 E2 R2 R2
3BAAA3 B0 B0 A0

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru