프로그램 명: ceoi_jobs(special judge)
제한시간: 1 초
CEOI 는 N 날 동안 M 개의 일을 처리하도록 요청을 받았다
하나의 일 을 수행하기 위해서는 한 기계에서 하루가 필요하고 한 기계는 하루동안 하나의 일을 처리할 수 있다.
CEOI 는 여러대의 기계를 사용할 수 있다. 즉 하루 동안 기계 수 만큼의 일을 할 수 있고 모든 일은 지연 날수 D 가 주어지는데
처리해하는 날 S 이면 S+D 일까지는 해도 무방하다.
Task
모든 작업은 D 날 동안의 여유를 가지면서 최소의 기계 수로 일을 마치고 자 한다. 최소 기계수와 각 날에 처리 하는 일을 출력 하는게 문제이다.
여러개의 답이 존재 하는 경우 그 중 하나를 출력한다.
The Central Engineering Organization, International (CEOI) has received M job requests for the next N
days. To perform a job requires exactly one day by one machine. CEOI has access to several machines, each
of which can perform at most one job per day, so the organization can do at most as many jobs a day as the
number of available machines. CEOI aims to work with at most D days of delay, which means that if a client
submits a job for processing on day S, then it will be finished no later than on day S+D.
Task
You are to write a program that computes the minimum number of machines that the organization needs
to process all jobs with at most D days of delay.
입력
- The first line of the input contains three integers,
- N (1 ≤ N ≤ 100 000) is the number of days the organization performs jobs,
- D (0 ≤ D < N) is the maximum number of days permitted for the delay,
- and M (1 ≤ M ≤ 1 000 000) is the number of job requests.
The days are numbered from 1 to N, and the requests are
numbered from 1 to M.
- The second line contains exactly M integers separated by space, the ith number is the day when request i is submitted for processing. No jobs are submitted after day N-D.
출력
- The first line of the output contains one integer, the minimum number of machines that the organization
needs to be able to process all jobs with at most D days of delay.
- The next N lines describe a feasible schedule for processing the requests. The (i+1)th line contains the identifiers of the requests scheduled for
day i. Numbers in a line must be separated by space and terminated by 0.
If there are multiple solutions,
your program should output only one; it does not matter which one.
입출력 예
입력
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
출력
2
5 1 0
9 4 0
2 10 0
6 12 0
3 7 0
11 8 0
0
0
출처:ceoi 2012
[질/답]
[제출 현황]
[푼 후(0)]