부호 행렬로 수열 찾기
시간 제한2초메모리 제한128 MB
숨겨진 정수 수열의 모든 부분합 부호가 주어질 때, 같은 부호 행렬을 만드는 정수 수열(각 값 -10~10)을 하나 복원합니다.
문제
정수 수열 a1, a2, ..., an이 있다. 1 <= i <= j <= n인 모든 구간에 대해, 구간합 ai + ... + aj의 부호를 모아 부호 행렬 S를 만든다. Sij는 구간합이 양수이면 "+", 음수이면 "-", 0이면 "0"이다.
수열 (-1, 5, -4, 2)의 부호 행렬은 다음과 같다.
이때 그 수열이 위 부호 행렬을 생성한다고 말한다. 어떤 정수 수열로 만들 수 있는 부호 행렬을 올바른 부호 행렬이라고 한다.
올바른 부호 행렬이 주어졌을 때, 그 행렬을 생성하는 정수 수열 하나를 찾아라. 같은 부호 행렬을 생성하는 수열은 여러 개일 수 있다. 출력하는 모든 정수는 -10 이상 10 이하이면 된다.
입력
첫째 줄에 수열의 길이 n이 주어진다 (1 <= n <= 10). 둘째 줄에는 길이가 n(n+1)/2인 문자열이 주어진다. 이 문자열은 부호 행렬의 윗삼각 부분을 행 순서대로 적은 것이다. 처음 n개 문자는 첫 번째 행, 다음 n-1개 문자는 두 번째 행, ..., 마지막 문자는 n번째 행을 나타낸다.
출력
주어진 부호 행렬을 생성하는 길이 n의 정수 수열을 한 줄에 출력한다. 가능한 수열이 여러 개라면 아무거나 출력해도 된다. 모든 정수는 -10 이상 10 이하이어야 한다.