내한 공연
면접 대비시간 제한1초메모리 제한128 MB
T분짜리 콘서트 동안 N명의 고정 길이 휴식 구간을 배치해서 어느 순간에도 겹치는 구간이 두 개를 넘지 않도록 시작 시각을 정하는 문제입니다.
문제
"The Drinking Musicians"는 N명으로 이루어진 유명 밴드이다. 이 밴드는 공연 중에도 멤버들이 자주 백스테이지로 사라져 휴식을 취하는 것으로 알려져 있다.
콘서트는 총 T분 동안 진행된다. 각 멤버 i는 공연 중 정확히 한 번, 정해진 시간 a_i분 동안 휴식을 취해야 한다. 어떤 순간에도 동시에 쉬는 멤버가 세 명 이상이면 무대에 남은 멤버들이 혼란에 빠져 공연을 계속할 수 없다. 따라서 동시에 쉬는 멤버는 많아야 두 명이어야 한다.
각 멤버의 휴식 시간이 주어질 때, 모든 휴식이 콘서트 시간 안에 끝나도록 각 멤버가 공연 시작 후 몇 분이 지난 시점에 휴식을 시작하면 되는지 구하시오.
입력
첫째 줄에 콘서트의 길이 T와 멤버의 수 N이 주어진다. (1 <= T <= 5000, 1 <= N <= 500)
둘째 줄에 각 멤버가 쉬어야 하는 시간이 입력 순서대로 공백으로 구분되어 주어진다.
항상 조건을 만족하는 답이 존재하는 입력만 주어진다. 답은 유일하지 않을 수 있다.
출력
각 멤버가 휴식을 시작해야 하는 시점을 입력 순서대로 공백으로 구분해 출력한다. 출력하는 값은 공연 시작 후 지난 분 수이다.
멤버 i의 휴식 시작 시각을 s_i, 휴식 시간을 a_i라고 하면 0 <= s_i이고 s_i + a_i <= T여야 한다. 또한 어떤 시점에도 구간 [s_i, s_i + a_i)에 포함되는 멤버 수가 2명을 넘으면 안 된다.
가능한 답이 여러 개이면 아무거나 출력해도 된다.