Zvimbalius
시간 제한1초메모리 제한1024 MB
N개의 이동 명령(S, P, R, V) 문자열이 주어질 때, 드론이 시작점으로 돌아오도록 바꿔야 하는 최소 명령 수를 구한다.
문제
Vytis turi naują žaislą – nuotoliniu būdu valdoma bepilotę skraidyklę, dar žinomą kaip dronas arba zvimbalius. Dronas yra bepilotis sragtasparnis, kuris skrenda vykdydamas jam duotas komandas.
Vyčio dronas supranta keturias komandas – S, P, R, V – kurios atitinkamai liepia jam skristi vieną metrą į šiaurę, pietus, rytus ar vakarus.
Vytis nusprendė išbandyti savo žaislą ir įvedė į jį N komandų, tačiau jas įvedęs suprato, kad dronas, įvykdęs tas komandas, gali nesugrįžti į pradinį tašką. Deja, komandas taisyti sunku, nes drono programinė įranga neleidžia nei pridėti, nei ištrinti jau įvestų komandų, o jas pakeisti galima tik po vieną. Vytis nori pakeisti kuo mažiau komandų taip, kad įvykdęs visas komandas dronas grįžtų į pradinį tašką.
Suskaičiuokite kiek mažiausiai komandų Vyčiui reikės pakeisti, kad dronas sugrįžtų į pradinį tašką.
입력
Pirmoje eilutėje yra pateiktas skaičius N – įvestų komandų kiekis. Antroje eilutėje yra pateiktas N komandų eilutė be tarpų k1k2...kN, kuriame ki yra i-toji komanda, užkoduota taip, kaip nurodyta sąlygoje.
출력
Išveskite vieną sveikąjį skaičių – kiek komandų reikia pakeisti, norint, kad dronas sugrįžtųį pradinį tašką.
Jei neįmanoma pakeisti komandų taip, kad dronas sugrįžtų į pradinį tašką, išveskite NEGALIMA.
제한
- 1 ≤ N ≤ 100 000