문제
두비두 마을 두호의 두부 공장 인기가 식을줄 몰라 행복한 두호는 다양한 맛의 두부를 기획했다.
커피맛 두부, 민트맛 두부 등등..
그렇게 총 N개의 맛을 출시할 예정이고 이를 위해서 M개의 장비를 구입했다.
맛은 1 ~ N 의 번호를 가지며, 장비는 1 ~ M 의 번호를 가진다.
장비 별로 만들 수 있는 맛 종류(type), 한번에 만들 수 있는 최대 개수(capacity), 만드는데 걸리는 시간(duration)이 정해져 있다.
생산이 이루어지는 규칙은 아래와 같다.
tick시각에 생산 필요한 수량이 있고 생산 가능한 장비가 있다면 생산을 시작한다.
만약, 생산 가능한 장비가 여러개라면 번호가 작은 장비부터 생산을 시작한다.
생산은 min(대기 수량, 장비의 capacity) 개 만큼 이루어지며, (tick + duration) 에 완료 된다.
생산이 완료된 장비는 완료된 시각(=tick + duration)부터 다시 생산 가능하다.
tick 시각에 들어온 주문은 tick 시각부터 바로 생산 가능하다.
위 규칙에 맞게 아래 공장을 운영하며 아래 두 가지 명령을 수행해보자.
0 tick type cnt
: 주문
tick시각에 type 종류의 두부 cnt개가 주문된다.
tick시각까지 업데이트 후, type 두부를 생산하고 있는 장비 id의 합을 출력한다.
1 tick
: 대기 수량이 가장 많은 type과 수량 확인
tick 시각에 생산 대기 중인 수량이 가장 많은 두부 type과 그 수량을 출력한다.
만약, 동일 수량이 여러개라면 번호가 가장 작은 type을 출력한다.
(생산 중인 수량은 포함하지 않는다.)입력
첫째 줄에 두부 종류 N, 장비 수 M이 입력된다.
둘째 줄에 장비 별 생산 가능한 두부 종류(type)가 M개 입력된다. 1번 장비부터 M번 장비 순이다.
셋째 줄에 장비 별 한번에 생산 가능한 최대 개수(capacity)가 M개 입력된다.
넷째 줄에 장비 별 한번 생산에 필요한 시간(duration)이 M개 입력된다.
다섯째 줄에 명령 수 Q가 입력된다.
여섯째 줄부터 Q개 줄에 걸쳐 명령이 형식에 맞게 입력된다.
: 0 tick type cnt
: 1 tick
[제약사항]
* N <= 20
* M <= 1,000
* Q <= 20,000
* 1 <= duration <= 1,000
* 1 <= capacity <= 500
* 1 <= tick <= 100,000,000
* 1 <= type <= N
* 모든 장비의 총 동작 횟수 <= 1,000,000
출력
cmd 1인 명령마다 한 줄씩 type과 남은 수량을 한 칸 띄고 출력한다.
예제
2 4
1 1 2 2
5 2 3 4
4 2 3 2
11
0 1 1 9
1 2
0 3 2 12
1 4
1 5
0 6 2 10
1 7
0 8 1 13
1 11
0 12 2 2
1 13
3
1 2
7
2 5
2 1
7
2 4
3
1 4
3
1 0
힌트
출처
teriusu
로그인해야 코드를 작성할 수 있어요.