Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の文字列 S があります。S の各文字は <
または >
です。
要素数 N+1 の非負整数列 X_0,X_1,\ldots,X_N は、すべての 1 \leq i \leq N について次の条件を満たすとき 良い非負整数列 と呼ばれます。
- S_i が
<
のとき : X_{i-1}<X_i - S_i が
>
のとき : X_{i-1}>X_i
良い非負整数列 A が与えられるので、この数列をできるだけ多くの良い非負整数列に分解してください。 つまり、正の整数 k および k 個の良い非負整数列 B_1,B_2,\ldots, B_k であって、次の条件を満たすもののうち、 k が最大のものを 1 つ求めてください。
- すべての 0 \leq i \leq N について B_1,\ldots,B_k の i 項目の値の合計は A_i と等しい。
制約
- 1 \leq N \leq 100
- 0 \leq A_i \leq 10^4
- S は
<
と>
からなる長さ N の文字列である。 - A は良い非負整数列である。特に、要素数は N+1 である。
入力
入力は以下の形式で標準入力から与えられる。
N S A_0 A_1 \cdots A_N
出力
以下の形式で、標準出力に出力せよ。
k B_{1,0} B_{1,1} \cdots B_{1,N} : B_{k,0} B_{k,1} \cdots B_{k,N}
ここで、B_{i,j} は良い非負整数列 B_i の j 項目の値を表している。
入力例 1
3 <>< 3 8 6 10
出力例 1
2 1 5 4 7 2 3 2 3
Score : 400 points
Problem Statement
We have a string S of length N, where each character is <
or >
.
A non-negative integer sequence of N+1 elements, X_0,X_1,\ldots,X_N, is said to be good when it satisfies the following for every 1 \leq i \leq N:
- X_{i-1}<X_i, if S_i is
<
; - X_{i-1}>X_i, if S_i is
>
.
Given a good non-negative integer sequence A, divide it into as many good non-negative integer sequences as possible. That is, find a positive integer k and k good non-negative integer sequences B_1,B_2,\ldots, B_k satisfying the following with the maximum possible value of k:
- For every 0 \leq i \leq N, the sum of the i-th elements of B_1,\ldots,B_k equals A_i.
Constraints
- 1 \leq N \leq 100
- 0 \leq A_i \leq 10^4
- S is a string of length N consisting of
<
and>
. - A is a good non-negative integer sequence. Particularly, A has N+1 elements.
Input
Input is given from Standard Input in the following format:
N S A_0 A_1 \cdots A_N
Output
Print your answer to Standard Output in the following format:
k B_{1,0} B_{1,1} \cdots B_{1,N} : B_{k,0} B_{k,1} \cdots B_{k,N}
Here, B_{i,j} denotes the value of the j-th element of the good non-negative integer sequence B_i.
Sample Input 1
3 <>< 3 8 6 10
Sample Output 1
2 1 5 4 7 2 3 2 3