Гра Zuma

Можливо, деякі з вас знайомі з грою Zuma про пригоди жабки. У цій задачі правила схожі й досить прості: у кам'яному жолобі лежить низка кольорових кульок; поруч із жолобом розташована гармата, в запасі якої є кольорові кульки, і час від часу вона вистрілює ними в жолоб. Кинуті кульки вбудовуються у ряд. Якщо після пострілу в жолобі утворюється безперервна послідовність з трьох або більше кульок одного кольору, і ця послідовність містить кинуту кульку, то такі кульки зникають, а сусідні кульки зсуваються разом, закриваючи проміжок у ряду (див. рисунок нижче). Якщо після зникнення кульок на місці їхнього з'єднання знову утворюється безперервна послідовність з трьох або більше кульок одного кольору, ці кульки також зникають — і так далі. Мета гри — знищити всі кульки.

Пронумеруємо кульки зліва направо, починаючи з $1$. Вистрілити кулькою у позицію $n$ означає, що вона з'явиться праворуч від кульки з номером $n$ й опиниться на позиції n+1. Номери кульок, розташованих правіше кинутої, збільшуються на одиницю. Постріл у самий лівий край ряду відповідає позиції номер $0$. Після зникнення деяких кульок, ті, що залишилися, перенумеровуються зліва направо, починаючи з $1$.

Вам потрібно написати програму, яка визначає оптимальну стратегію стрільби. Оптимальною вважається стратегія, за якої мінімальна кількість пострілів призводить до зникнення всіх кульок. Якщо таких стратегій декілька, обирають ту, у якій перший постріл здійснюється якомога лівіше, потім (якщо рівність зберігається) порівнюють за другим пострілом, і так далі.