탐사 Batch
Time limit | Memory limit | # of submissions | # of submitted users | Solved # | Accepted user ratio |
---|---|---|---|---|---|
2000 ms | 256 MiB | 34 | 16 | 10 | 62.50% |
직선 모양의 도로에 특별한 물체가 묻혀있다. 우리는 직선구간을 탐색할 수 있는 장비를 이용해서 이 물체가 어디에 있는지를 조사하고자 한다. 직선도로를 일차원 배열로 생각해보자. 아래 그림에서 숫자는 단위 구간의 번호이며 그 안에 ▲ 기호로 표시된 것은 우리가 찾아낼 물체이다.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|
▲ | ▲ | ▲ | ▲ | ▲ | ▲ |
그런데 우리는 어떤 연속된 구간에 포함되어 있는 물체의 개수를 를 이용하여 확인할 수 있다. 부터 까지의 구간에 물체가 개가 있음은 로 표현된다. (단 이다.) 예를 들어 그림 1과 같은 상황이라면 , , , 임을 알 수 있다.
여러분은 제시된 탐사작업의 결과가 모두 만족되는 구간을 재구성하는 프로그램을 작성해야 한다.
입력 형식
첫 줄에는 두 개의 정수 와 이 주어져 있다. 는 전체 구간의 길이이며, N은 조사한 결과의 개수이다. 이어 나타나는 개의 각 줄에는 하나의 탐사결과 를 나타내는 세 개의 숫자 , , 이 공백문자로 분리되어 제시되어 있다. 단 입력변수에 대한 제한 범위는 다음과 같다. .
출력 형식
여러분은 개의 탐사결과를 만족하는 전체 구간을 길이 인 문자열로 표시해야 한다. 물체가 있는 단위 구간은 문자 '#'
으로 표시해야 하고, 없는 단위 구간은 마이너스 기호 '-'
로 표시해야 한다. 답이 여러 개 존재할 때에는 그 중 하나만 출력하면 된
다. 만일 탐사결과를 모두 만족하는 답이 존재하지 않을 경우에는 문자열 "NONE
"을 출력해야 한다.
입력과 출력의 예
예제 1
입력
12 7
1 8 4
6 10 4
2 12 6
9 12 2
4 6 1
1 4 1
11 11 0
출력
--#--####--#
예제 2
입력
12 2
1 10 1
4 7 3
출력
NONE
Problem Source