● Bayan 2012-2013 Elimination Round - A. Duel

مسابقه برنامه نویسی بیان - انتخابی آبان 91

دوئل

در نوع جدیدی از بازی دوئل، n سرباز در یک صف قرار می گیرند و هر سرباز به سمت چپ ‘(‘ یا راست ‘)’ نشانه گیری کرده و آماده ی شلیک می شود. در هر ثانیه، اگر دو سرباز به سمت یکدیگر نشانه گرفته باشند و سرباز زنده ای میان آن دو نباشد، به همدیگر شلیک می کنند و هر دو کشته شده و به زمین می افتند. سربازانی که از مسابقه جان سالم به در ببرند، جوایز نفیسی دریافت می کنند.

برای مثال اگر جهت گیری اولیه سربازان به صورت ) ( ( ( ) ( ) ) ( ( باشد، در ثانیه اول سربازان چهارم و پنجم از سمت چپ و سربازان ششم و هفتم به هم شلیک خواهند کرد و در ثانیه دوم، سربازان سوم و هشتم به هم شلیک خواهند کرد و سایرین سالم خواهند ماند.

برگزار کننده ی این مسابقه از شما خواسته است تا با توجه به جهت گیری اولیه سربازان، تعداد سربازهایی که جان سالم بدر خواهند برد را بدست آورید تا او جوایز لازم را تهیه کند.

input

2
10
))(()()))(
6
()(())

output

4
0

ورودی:

در خط اول ورودی، عدد صحیح (T (1 ≤ T ≤ 100 تعداد تست ها آمده است.

برای هر تست، در خط اول عدد صحیح (n (1 ≤ n ≤ 1000 و در خط دوم جهت گیری اولیه سربازها به صورت رشته ای           به طول n شامل کاراکترهای ‘)’ و ‘(‘ آمده است.

خروجی:

به ازای هر تست در خروجی، در یک خط تعداد سربازهایی که جان سالم به در می برند را چاپ کنید.

// A Drop of the Programming Sea - adops.blog.ir

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i=0; i<t; i++)
    {
        int n;
        cin >> n;
        string str;
        cin >> str;
        str = str.substr(0, n);
        while(str.find("()")!=-1)
            str.erase(str.find("()"), 2);
        cout << str.length() << endl;
    }
}