Задача Balls
N куль розташовано вертикально в стовпчик. Кожна з куль зафарбована в один з чотирьох кольорів: червоний (R), зелений(G), синій(B) або жовтий (Y). Групою називають кілька поряд розташованих куль однакового кольору, безпосередньо згори або знизу від яких знаходяться кулі іншого кольору або куль немає.
За один хід можна обрати будь яку групу, яка складається хоча б з двох куль, і вилучити її. За вилучення групи, яка складається з k кульок, гравець отримує k2 очок. Після знищення групи, кулі, які розміщені вище, опускаються донизу – стовпчик знову стає суцільним. Для прикладу на рисунку наведена позиція: 10 куль двох кольорів. В ній є 4 групи, яки містять 3, 2, 4 та 1 кулю відповідно. Якщо вилучити групу з чотирьох куль, гравець отримає 16 очок, та 5 куль згори спустяться до низу. В результаті буде 6 куль двома групами по три в кожній.
За заданою початковою позицією треба визначити, чи можливе знищення всіх куль, і, якщо це можливо, то яку найбільшу кількість балів можна при цьому отримати.
Технічні умови.
Напишіть програму Balls, яка читає з клавіатури послідовність з символів “R”, “G”, “B” та “Y”, що описує початкову позицію. Букви задають кольори куль в порядку перегляду зверху до низу. (“R” позначає червоний, ”G” – зелений, ”B” – синій та ”Y” – жовтий кольори). Початкова позиція має не менш двох та не більш за 100 бульбашок.
Програма повинна вивести на екран одне ціле число – найбільшу кількість очок, яку можна отримати. Якщо знищити всі кулі неможливо, програма повинна вивести число 0.
| Приклади |
|
| Введення: |
Виведення: |
| Приклад 1 |
|
RRRGGRRRRG
|
34 |
| Приклад 2 |
|
| RB |
0 |