시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB74422741175635.991%

문제

Given a sequence of integers, a1, a2, …, an, we define its sign matrix S such that, for 1 ≤ i ≤ j ≤ n, Sij="+" if ai + … + aj > 0; Sij="−" if ai + … + aj < 0; and Sij="0" otherwise. 

For example, if (a1, a2, a3, a4)=( −1, 5, −4, 2), then its sign matrix S is a 4×4 matrix: 

  1 2 3 4
1 - + 0 +
2   + + +
3     - -
4       +

We say that the sequence (−1, 5, −4, 2) generates the sign matrix. A sign matrix is valid if it can be generated by a sequence of integers. 

Given a sequence of integers, it is easy to compute its sign matrix. This problem is about the opposite direction: Given a valid sign matrix, find a sequence of integers that generates the sign matrix. Note that two or more different sequences of integers can generate the same sign matrix. For example, the sequence (−2, 5, −3, 1) generates the same sign matrix as the sequence (−1,5, −4,2). 

Write a program that, given a valid sign matrix, can find a sequence of integers that generates the sign matrix. You may assume that every integer in a sequence is between −10 and 10, both inclusive. 

입력

The first line contains an integer n(1 ≤ n ≤ 10), where n is the length of a sequence of integers. The second line contains a string of n(n+1)/2 characters such that the first n characters correspond to the first row of the sign matrix, the next n−1 characters  to the second row, ..., and the last character to the n-th row. 

출력

Output exactly one line containing a sequence of n integers which generates the sign matrix. If more than one sequence generates the sign matrix, you may output any one of them. Every integer in the sequence must be between −10 and 10, both inclusive.

예제 입력 1

4
-+0++++--+

예제 출력 1

-2 5 -3 1

예제 입력 2

2
+++

예제 출력 2

3 4

예제 입력 3

5
++0+-+-+--+-+--

예제 출력 3

1 2 -3 4 -5

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2008 G번

  • 문제의 오타를 찾은 사람: 1207koo