URL: http://acm.zju.edu.cn/show_problem.php?pid=1016
Problem:
Let S = s1 s2 … s2n be a well-formed string of parentheses. S can be encoded in two different ways:
* By an integer sequence P = p1 p2 … pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
* By an integer sequence W = w1 w2 … wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).
Following is an example of the above encodings:
S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input:
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.
Output:
The output consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.
Sample Input:
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output:
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9
My Solution: (C++, GCC)
You can solve this problem quickly if you have understood what the difference is between the P-sequence and W-sequence. Let's look at P-sequence first. Each integer in this sequence indicates the number of left parentheses before a right parenthese. In this way, subtracting Pi with Pi-1 and store the result into element p[i], the number of left parentheses between Pi and Pi-1can be calculated with ease.
SUBPi = Pi = Pi - Pi-1, specially P0 is same to the old one.
Here SUBPi indicates the number of left parentheses which are not coupled with the first i-1 right parentheses. Now let's have an iteration from SUBP0 to SUBPn, and you will find there are two situation we have to deal with. If SUBPi > 0, simply output Pi - SUBPi + 1. Otherwise search last left parenthese Li which has not been coupled with right parentheses, and count left parentheses between Li and Pi (include Li). What's more output the number you have just got.
#include <iostream>
// PS: The code is for study purpose only, never submit it as ones own.
// From: http://blog.csdn.net/mskia/
// email: ichobits@21cn.com
int main(void) {
int t;
std::cin >> t;
int p[20], subp[20];
for (int i = 0; i < t; ++i) {
int n;
std::cin >> n;
for (int j = 0; j < n; ++j) {
std::cin >> p[j];
}
for (int j = n - 1; j > 0; --j) {
subp[j] = p[j] - p[j - 1];
}
subp[0] = p[0];
for (int j = 0; j < n; ++j) {
p[j] = subp[j];
}
for (int j = 0; j < n; ++j) {
if (j > 0) {
std::cout << ' ';
}
if (subp[j] > 0) {
std::cout << p[j] - subp[j] + 1;
--subp[j];
} else {
int sum = 0;
for (int k = j; k >= 0; --k) {
if (subp[k] == 0) {
sum += p[k];
} else {
sum += p[k] - subp[k];
std::cout << sum + 1;
--subp[k];
break;
}
}
}
}
std::cout << std::endl;
}
return 0;
}
