| Fişierul intrare/ieşire: | sageti.in, sageti.out | Sursă | ad-hoc |
| Autor | Din Folclor | Adăugată de |  Dragos Alin Rotaru •mathboy |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Sageti
Tractorel şi-a cumpărat un arc cu foarte multe săgeţi. Acesta are N săgeţi aşezate în şir, orientate spre stânga ('<') sau în dreapta ('>'). Personajul principal are dreptul la operaţia ERASE care elimină o săgeată din şir. Cum talentul lui Tractorel este numărarea dolarilor, acesta numără săgeţile la stânga din şir şi le notează cu NRS, respectiv NRD cele poziţionate la dreapta .
Dându-se un şir de N săgeţi acesta vrea să afle numărul minim de operaţii ERASE astfel încât după efectuarea lor şirul să înceapă doar cu săgeţi spre dreapta iar în continuarea lor să se afle doar săgeţi orientate spre stânga şi NRS = NRD.
După cum v-aţi obişnuit, Tractorel vă roagă să răspundeţi la T întrebări.
Date de intrare
Fişierul de intrare sageti.in conţine pe prima linie un număr natural T, reprezentând numărul de teste. Fiecare din cele T linii va conţine un număr natural N semnificând numărul de săgeţi şi un şir de caractere S de lungime N. N si S sunt separate printr-un spaţiu.
Date de ieşire
În fişierul de ieşire sageti.out se vor afla T linii, fiecare conţinând câte un singur număr reprezentând răspunsul cerinţei.
Restricţii
- 1 ≤ T ≤ 15
- 1 ≤ N ≤ 106
Exemplu
| sageti.in | sageti.out |
|---|---|
| 2 3 >>< 10 >>><<><<>> | 1 4 |
Explicaţie
Pentru simplitate vom consideră că începem numerotoarea poziţiilor de la 1.
În primul caz se poate aplica operaţia ERASE pe săgeată de pe prima poziţie din şir.
În al 2-lea caz se poate aplica ERASE pe săgeţile de pe poziţiile 5, 7, 9, 10.
