Lamps
TopCoder TCO2014 Round 1A
Time Limit: 0.2s, Memory Limit: 64MiB
В градината с цветя на Ели има пътечка, по протежението на която има N лампи. Някои от тях са включени, а останалите – изключени. Момичето може да включва и изключва лампите ползвайки контролер с N бутона, също разположени в редичка. Бутонът с индекс i променя състоянието на лампа i: тя бива изключена, ако е била включена, и бива включена, ако е била изключена.
За съжаление, контролерът е леко дефектен. Макар и всеки от бутоните все още да променя състоянието на съответстващата му лампа, е възможно да променя и състоянието на една или и двете от съседните му такива. По-формално, натискането на бутона с индекс i има следните ефекти:
Сега Ели иска да остави възможни най-малко лампи включени. Помогнете ѝ, като определите колко най-малко ще са те в най-лошия вариант от дефекти.
За съжаление, контролерът е леко дефектен. Макар и всеки от бутоните все още да променя състоянието на съответстващата му лампа, е възможно да променя и състоянието на една или и двете от съседните му такива. По-формално, натискането на бутона с индекс i има следните ефекти:
- Състоянието на лампа i се променя.
- Състоянието на лампа i-1 (ако има такава) може да се промени.
- Състоянието на лампа i+1 (ако има такава) може да се промени.
Сега Ели иска да остави възможни най-малко лампи включени. Помогнете ѝ, като определите колко най-малко ще са те в най-лошия вариант от дефекти.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – броя лампи (и, съответно, бутони). На следващия ред ще бъде зададен стринг с N символа 'Y' и 'N', задаващ какво е състоянието на лампите в началото. Символът на позиция i ще бъде 'Y', ако i-тата лампа е включена, и 'N' ако не е.
Изход
На стандартния изход изведете едно цяло число – минималния брой включени лампи, които може да остави Ели в най-лошия за нея случай.
Ограничения
- 1 ≤ N ≤ 50
Примерен Вход | Примерен Изход |
---|---|
5 YNNYN | 2 |
2 YY | 0 |
9 YNYYYNNNY | 3 |
34 YNYYYYNYNNYYNNNNNNYNYNYNYNNYNYYYNY | 13 |
В първия пример Ели може само да влоши нещата. Например, представете си, че бутоните 1 и 2 променят състоянието и на двете лампи 1 и 2; бутоните 3 и 4 променят състоянието и на двете лампи 3 и 4, а бутон 5 променя състоянието на лампа 5. При тези дефекти Ели не може да достигне до състояние с по-малко от две включени лампи.