시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 54 19 17 36.170%

문제

선홍이는 집 앞마당에 일렬로 배치된 N(≤100,000)개의 칸으로 구성된 화단을 가꾸면서 왼쪽부터 차례로 1, 2, 3, … N의 번호를 붙여주었다. 어느 날 선홍이는 자신의 화단에 보석이 묻혀 있을 지도 모른다는 찌라시를 접하고는 금속 탐지기를 통해 보석을 파악하기로 마음 먹게 된다. 선홍이의 금속 탐지기는 s와 e라는 두 숫자를 지정해주면 s번 화단부터 e번 화단까지 돌며 그 구간 안에 있는 보석의 총 개수를 알려준다. (1≤s≤e≤N) 선홍이는 금속 탐지기를 통해 자신의 화단을 M(≤100,000)번 테스트해보고 그 결과를 적어놓았다. 때마침 지나가던 영민이는 평소 선홍이에게 괴롭힘 당한 것에 대한 분풀이를 하기 위해 보석 개수를 조작해 일의 자릿수만을 남겨 놓았다. 이 사실을 알고 화가 난 선홍이는 영민이를 불러 이 자료만을 가지고 각 칸에 있는 보석 개수를 유추해오라는 지시를 내렸다. 불쌍한 영민이를 도와주자 ㅠㅠ

입력

첫째 줄에 화단의 개수 N과 테스트한 횟수 M이 주어진다.

둘째 줄부터 M개의 줄에는 공백을 사이에 두고 si, ei, ci가 주어진다. 이는 i번째 테스트에서 선홍이가 [si, ei] 구간을 탐사했으며 그 구간의 보석 개수의 일의 자리 숫자가 ci임을 의미한다. (1≤si≤ei≤N, 0≤ci≤9)

출력

테스트 결과에 부합하게끔 각 칸의 보석 개수를 출력한다. 답이 여러 개라면 아무거나 출력해도 좋으며, 입력 자체에 모순이 있는 경우 -1을 출력한다. 각 칸에 묻혀 있는 보석의 수는 0이상 100이하의 정수여야 한다.

예제 입력 1

5 4
1 2 4
2 5 3
3 4 1
1 4 5

예제 출력 1

16 28 4 7 64

예제 입력 2

5 3
1 3 4
1 4 3
4 4 8

예제 출력 2

-1

힌트

1번 예제에서는 4 0 0 1 2, 96 98 94 97 94 등도 답이 될 수 있다. 2번 예제를 만족하는 해는 없음을 쉽게 알 수 있으므로 -1을 출력한다.

출처

High School > 대구과학고등학교 > 2017 대곽 Codejam 정보경시대회 5번

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: tlwpdus