bilete

Майка ми има навик да оставя на цветни бележки инструкции за различни домакински дейности. Тя закача бележките на една дъска до хладилника. Бележките са правоъгълни, всички са с една и съща височина (равна на височината на дъската), но са с различни дължини. Мама никога не изхвърля старите бележки, а просто забожда новите върху старите. В момента цялата дъска е покрита с бележки и единственото, което се вижда са цветове на поставени бележки.

Всяка сутрин, докато си пия кафето си задавам един и същ въпрос: Колко бележки общо има на дъската?

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

За целта кодирам цветовете на бележките с главни букви от английската азбука (като на всеки сантиметър от дъската съпоставям по една буква, според цвета, който се вижда там).

Задача

Напишете програма, която след като анализира цветовете, които се виждат, определя минималния възможен брой бележки.

Вход

Входният файл  bilete.in  съдържа единствен ред, на който е записана последователност от главни букви от английската азбука, представящи цветовете, които се виждат на дъската.

Изход

Изходният файл  bilete.out  трябва да съдържа единствен ред, на който е записано едно число ­– минималния възможен брой бележки на дъската.

Ограничения

  • Дължината на дъската е най-много 100 cm.

 

Пример

bilete.in

bilete.out

Обяснение

ABCCCBAABA

4

Едно възможно решение е:
Мама поставя бележка с цвят
 A,   дълга 10 cm.
После поставя (на един сантиметър от левия край на дъската) бележка с цвят
  B, дълга 5 cm.
После поставя (на 2 cm от левия край на дъската) бележка с цвят
 C, дълга 3 cm.

Последната бележка (на 8 cm от левия край на дъската) има цвят  B  и е дълга 1 cm.

Ограничение за време: 0.1 секунди на тест

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School

За връзка: emanuela.cerchez@gmail.com

(Превод на български: Стоян Капралов)