Lamps
TopCoder TCO2014 Round 1A
Time Limit: 0.1s, Memory Limit: 64MiB
В градината с цветя на Ели има пътечка, по протежението на която има N лампи. Някои от тях са включени, а останалите – изключени. Момичето може да включва и изключва лампите ползвайки контролер с N бутона, също разположени в редичка. Бутонът с индекс 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. При тези дефекти Ели не може да достигне до състояние с по-малко от две включени лампи.
Мрън!