Diferențe pentru problema/sageti între reviziile #15 si #29

Sageti

Săgeți

== include(page="template/taskheader" task_id="sageti") ==

Tractorel si-a cumparat un arc cu foarte multe sageti. Acesta are $N$ sageti asezate in sir, orientate spre stanga $('<')$ sau in dreapta $('>')$.
Personajul principal are dreptul la operatia $ERASE$ care elimina o sageata din sir. Fie $NRS$ - numarul $('<')$ si $NRD$ numarul $('<')$.
 
Dandu-se un sir de $N$ sageti acesta vrea sa afle numarul minim de operatii $ERASE$ astfel incat dupa efectuarea lor sirul sa inceapa doar cu sageti spre dreapta iar in continuarea lor sa se afle doar sageti orientate spre stanga si $NRS = NRD$.
Dupa cum v-ati obisnuit, Tractorel va roaga sa raspundeti pentru $T$ intrebari.

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.

h2. Date de intrare

Fișierul de intrare $sageti.in$ contine pe prima linia un numar natural [$T$], reprezentand numarul de teste. Fiecare din cele $T$ linii vor contine un numar natural $N$ si un sir $S$ de sageti de lungime [$N$]. $N$ si $S$ sunt separate printr-un spatiu.

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.

h2. Date de ieșire

În fișierul de ieșire $sageti.out$ se vor afla $T$ linii continand cate un singur numar reprezentand raspunsul cerintei.

Î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.

h2. Restricții

* $1 ≤ T ≤ 30$

* $1 ≤ T ≤ 15$

* $1 ≤ N ≤ 10[^6^]$
h2. Exemplu

|
h3. Explicație

Pentru simplitate vom considera ca facem numaratoarea de la [$1$].
Pentru primul caz se poate aplica operatia $ERASE$ pe sageata de pe prima pozitie din sir.
Pentru al [$2$]-lea caz se poate aplica $ERASE$ pe sagetile de pe pozitiile 5, 9, 10

 
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.

== include(page="template/taskfooter" task_id="sageti") ==