IOI 1996 day1 2- 잡 프로세싱(Job Processing) > 문제은행 : 정보올림피아드&알고리즘




2075 : 잡 프로세싱(Job Processing)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
7 회   
시도횟수
31 회   

문제

어떤 공장이 생산 라인이다. 생산 과정에는 A와 B라는 두 가지 공정이 이루어진다. 

공장에는 각각의 공정을 수행하도록 되어있는 기계가 여러대 있다.

아래 그림은 생산라인의 구성 모습을 잘 보여주고 있다. 

A공정을 하는 기계는 처음에 들어온 원료를 사용하여 이를 중간 생성물로 바꾼 뒤 이를 B공정을 맡은 기계에 넣는다. 

B공정을 하는 기계는 중간 생성물을 더 가공하여 그것으로 완제품을 만든다.

 

 

 

단, 여기서는 원료 하나가 각각 중간 생성물과 완제품의 순서로 바뀐다. 

모든 기계는 서로에게 영향을 주지 않고 같은 시간에 병렬식으로 따로따로 동작한다. 

각 원료의 크기는 별 제한이 없으며, 개수만이 의미가 있다. 

다만 기계들은 제각기 성능이 달라, 한 개의 원료를 처리하는 시간이 기계마다 서로 다를 수 있다.

모든 기계가 작업을 동시에 시작했을 때, N개의 원료가 모두 A과정을 마무리하는데 필요한 가장 짧은 시간을 계산하라. 

그리고 N개의 원료가 모두 완제품으로 바뀌는데 걸리는 가장 짧은 시간도 계산하라.

 


입력형식

첫줄에 원료의 수 N(1≤N≤1,000), "A"공정을 처리하는 기계의 수 M1(1≤M1≤30), "B"공정을 처리하는 기계의 수 M2(1≤M2≤30)가 들어온다.

둘째 줄에는 M1개의 수가 나오며, 이것은 A공정의 각 기계가 원료를 중간 생성물로 바꾸는데 걸리는 시간이며, 이어서 M2개의 수가 나오는데 이것은 B공정의 각 기계가 중간 생성물을 완제품으로 바꾸는데 걸리는 시간이다. 각 기계의 시간 범위는 1~20이다.


출력형식

첫 번째로는 모든 원료가 A공정을 다 마치는 데 걸리는 최소 시간을 두 번째는 모든 원료가 완제품으로 바뀌는데 걸리는 최소 시간을 한 줄에 출력한다.


입력 예

5 2 3
1 1 3 1 4

출력 예

3 5


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP