eolymp
bolt
Try our new interface for solving problems
Məsələlər

Игра Zuma

Игра Zuma

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Возможно, некоторым из вас знакома игра Zuma о приключениях лягушки. В данной задаче правила похожи и довольно просты: в каменном жёлобе находится ряд разноцветных шаров; пушка, расположившаяся рядом с жёлобом, имеет некоторый запас разноцветных шаров и периодически закидывает их в желоб. Заброшенные шары встраиваются в ряд. Если после выстрела в желобе образуется непрерывная последовательность из трех или более шаров одного цвета, включающая заброшенный шар, то они исчезают, а соседние шары сдвигаются, смыкая ряд (см. рис. ниже). Если после исчезновения шаров в месте стыка соседние шары образуют непрерывную последовательность из трех или более шаров одного цвета, то они также исчезают, и так далее. Цель игры – уничтожить все шары.

Пронумеруем шары слева направо, начиная с единицы. Выстрел шара в позицию n означает, что он появится правее шара с номером n и окажется в позиции n+1. Номера шаров, расположенных правее прилетевшего шара, увеличиваются на единицу. Приземление шара левее всего ряда обозначается позицией с номером 0. После исчезновения некоторых шаров, шары в желобе нумеруются заново слева направо, начиная с единицы.

Требуется написать программу, определяющую оптимальную стратегию стрельбы. Оптимальной стратегией называется та, при которой наименьшее количество выстрелов приводит к исчезновению всех шаров, а если таких стратегий несколько, то выбирается та, при которой первый выстрел производится как можно левее, а если несколько и таких, то сравнение идёт по второму выстрелу и т.д.

Giriş verilənləri

Первая строка содержит количество тестов. Каждый тест состоит из одной строки с описанием одного ряда шаров, цвет каждого шара описывается заглавной буквой латинского алфавита (A..Z). Тест №1 и его решение изображен на иллюстрации. Известно, что длина ряда ≤ 14, а для уничтожения ряда требуется ≤ 10 выстрелов, если следовать оптимальной стратегии.

Çıxış verilənləri

Для каждого теста вывести одну строку: сначала минимальное количество выстрелов, затем через пробел пары буква-число: цвет шара и позицию выстрела. Выстрелы в ответе должны быть в перечислены в порядке их следования в игре.

Nümunə

Giriş verilənləri #1
2
ABBBAA
ACMNEERC
Çıxış verilənləri #1
1 B1
10 A0 A0 C0 M2 M2 N2 N2 E2 R2 R2
Mənbə Школа Программиста, Красноярский край, Пятая командная олимпиада, 15 ноября 2009, Задача G