時間制限:1000ミリ秒
メモリ制限:10000KB
丸括弧エンコーディング
問題
Sをs1 s2...s2nなる丸括弧のみからなる文字列、つまり「正規な文字列」とする。Sは以下の2通りの方法で符号化(エンコード)される:
piが「i番目の閉じ括弧以前にある開き括弧の数」であるような列P = p1 p2...pn (P列)
wiが「i番目の閉じ括弧と、それに対応する開き括弧の間にある閉じ括弧の数」であるような列W = w1 w2...wn (W列)
上記のエンコードの例を示す:
S | ( | ( | ( | ( | ) | ( | ) | ( | ) | ) | ) | ) |
P列 | 4 | 5 | 6 | 6 | 6 | 6 | ||||||
W列 | 1 | 1 | 1 | 4 | 5 | 6 |
正規な文字列のP列を、同じ文字列のW列に変換するプログラムを書け。
入力
入力の最初の行には、テストケースの数をあらわす1つの整数t(1 <= t <= 10)が書かれている。
その次の行からは、テストケースが順番に書かれている。テストケースの最初の行は、整数n(1 <= n <= 20)が、また次の行にはP列をあらわすn個の正整数が空白を区切りとして書かれている。
出力
出力ファイルはt個のテストケースに対してそれぞれの応答が書かれている。それぞれのテストケースに対する出力は、与えられたP列と同じ文字列をあらわすW列を記したn個の整数が空白を区切りとして書かれている。
入力例
2 6 4 5 6 6 6 6 9 4 6 6 6 6 8 9 9 9
出力例
1 1 1 4 5 6 1 1 2 4 5 1 1 3 9
出典
Tehran 2001