Игра Zuma

Помогите пожалуйста решить задачу.

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

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

Входные данные:
Содержит описание ряда шаров, цвет каждого шара описывается заглавной буквой английского алфавита (A..Z). Известно, что длина ряда не превышает 14 шаров, а для уничтожения ряда требуется не более 10 выстрелов, если следовать оптимальной стратегии.

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

Ввод: ABBBAA
Вывод: 1 B1

Ввод: ACMNEERC
Вывод: 10 A0 A0 C0 M2 M2 N2 N2 E2 R2 R2

Ввод: BAAA
Вывод: 3 B0 B0 A0

0

Это здорово, но как 42 получить?

0

Сообщение от KSergey9 Хорошо вам

прям щас в браузере можете наверстать:
https://yandex.ru/games/tag/zuma_117

Сообщение от KSergey9 Это здорово, но как 42 получить?

вы рассказ не читали?
https://ru.wikipedia.org/wiki/... его_такого

0

Не, ну так не играю...
Даже мысли в эту сторону у меня не было

0

Сообщение от KSergey9 Это здорово, но как 42 получить?

ну, я же исправился, ответ 28(по условию задачи) или для случая SmallEvil 30 ударов.

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

когда у мя есть такие теоремы или аксиомы, то можно приступать к продуктивному решению.

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

случай SmallEvil с 15 шарами разного цвета как раз такой.

чтобы снять один шар нужно добавить ещё 2 такого же цвета.
а раз их 15, то 15 * 2 = 30 шаров нужно будет добавить.

нужны делать гипотезы,

так как доказывать/опровергать гипотезы у мя тямы не всегда хватает,
то в качестве доказательства как раз валидатор будет самое то.

а раз валидатора нет, то нет и супер-пупер решения))

вот пример нетривиального желоба с шарами(без уникальных цветовых нодов), на котором у мя зависает:

0

Сообщение от XLAT если ряд шаров состоит из нодов с уникальным цветом, то такие ноды можно сразу безболезненно снять из желоба.

Нельзя просто взять и снять, их тоже нужно учитывать, так или иначе.
Вот например, входная цепочка.
"VABZBCBB"
V и A убираются без проблем, C и Z - участвуют в цепочке в строго определенном порядке.
Убираются Z потом С - B схлопываются.

Добавлено через 5 минут

Сообщение от Pelmen342 для уничтожения ряда требуется не более 10 выстрелов

Наверное это условие и есть тот ограничитель, для которого может пройти брутфорс.
Хотя я бы на это не ставил.

1

Сообщение от SmallEvil "VABZBCBB"

Хороший контрпример, мой алгоритм не сработает корректно, не даст минимальную цепочку действий.

0

Я просто понаблюдать тут.
Чет не цепляет задачка. Да и делать, а потом зажать (ТС же нужно самому учится, не могу себе позволить препятствовать святому процессу) не хочется )

0

Сообщение от SmallEvil Наверное это условие и есть тот ограничитель

тс валидатор зажал, а мы тут мучайся)

0