UVa 228
자원 할당
설명
한 소프트웨어 개발 회사가 생산성을 높이기 위해 새로운 프로그래머들을 고용하려고 한다. 하지만 생산성을 측정하는 것이 어렵기 때문에, 프로그래밍 부서에서 새로 작성한 소스 코드의 줄수를 생산성으로 간주하기로 했다. 회사는 생산성을 최대화시키기 위해서 어떻게 돈과 프로그래머를 각 부서에 할당해야 할 지를 결정할 만한 자원 할당 모델을 찾고자 한다.
각 부서는 필요로 하는 인원과 예산이 따로 있다. 예를 들어, 어떤 부서가 0, 3, 5, 6명의 새로운 프로그래머가 필요하다고 한다면, 이 부서에 1, 2, 4, 7명의 새로운 프로그래머를 배치하면 안된다. 예산도 마찬가지로, $0, $20000, $50000, $90000를 필요로 하는 부서에 이외의 금액을 예산으로 책정할 수 없다. 또한 각 부서마다 새로운 프로그래머와 예산이 할당되었을 때 증가되는 소스코드의 줄 수가 주어진다. 증가되는 소스코드는 양의 값을 가지며, 0명의 새 프로그래머와 $0의 예산이 주어진다면, 증가되는 소스코드는 0줄이다. 위 예제에서는 프로그래머에서 4가지 경우, 예산에서 4가지 경우가 있으므로 총 16가지 경우를 생각해 볼 수 있으며, 각각의 경우에 증가되는 소스코드가 입력될 것이다.
당신은 새 프로그래머와 자원을 각 부서에 가장 효율적으로 배치하는 프로그램을 작성해야 한다. 각 부서마다 몇 명의 프로그래머가 배치될 것이며 얼마의 예산이 할당될 것인가를 결정해야 한다. 각 부서에 배치된 프로그래머의 수의 합은 새로 고용하는 프로그래머의 총 인원수를 넘지 못하며, 예산 또한 책정된 전체 예산을 넘지 못한다. 이 프로그램을 작성하는 방법은 여러 가지가 있는데, 이 중 아무 것이나 사용해도 된다.
입력
몇 개의 테스트케이스가 주어질 수 있다.
입력파일의 첫 세 줄은 다음과 같다.
d : 부서의 개수(0<d<=20)
p : 새로 고용할 프로그래머의 최대 수
b : 부서에 새로 배치할 예산의 최대 액수
위의 3줄 이후에 나오는 정보는 각 부서에 대한 정보이다. 첫 번째 나오는 것은 division #1에 대한 정보이고, 두 번째는 division #2, 세 번째는 division #3...과 같다. 각 부서의 정보는 다음과 같이 구성되어 있다.
n : 새로 배치할 수 있는 프로그래머의 수의 가지수
x1 x2 x3...xn : 새로 배치할 수 있는 프로그래머 수(공백으로 구분된다)
k : 새로 배치할 수 있는 예산 액수의 가지수
b1 b2 b3...bn : 배치할 수 있는 예산의 액수(공백으로 구분된다)
n*k 크기의 정수 배열 : i행 j열의 데이터는 xi명의 프로그래머와 bj의 예산을 새로 배치했을 때 증가하는 소스코드의 줄 수이다.
새 프로그래머와 예산을 어떤 부서에도 배치하지 않는 것도 물론 가능하다. 이 경우에는 증가하는 소스코드의 줄 수가 0이 될 것이다.
만약 d에 0이 입력될 경우 파일의 끝으로 간주하면 된다. 각 테스트케이스는 새로운 줄로 시작한다.
출력
각 테스트케이스에 대해 problem #1, problem #2와 같이 몇 번째 테스트케이스인지 밝혀야 한다. 각 테스트케이스마다 새로 투자할 돈의 총 액수와 새로 배치할 프로그래머의 수를 출력하고, 이로 인해 증가되는 생산성(증가되는 소스코드의 줄 수)은 얼마인지 출력한다. 이후 각 부서별로 얼마의 돈과 프로그래머를 배치할 것인지와 이로 인해 증가하는 소스코드의 줄 수를 출력한다. 부서와 부서 사이에는 빈 줄이 존재해야 한다. 출력은 출력 예제를 참고하여 가능한 한 읽기 쉬운 형태로 해야 한다.
입력 예제
10
90000
4
0 2 5 6
4
0 20000 50000 70000
0 10000 20000 50000
60000 20000 10000 40000
20000 10000 30000 40000
30000 10000 40000 30000
5
0 1 3 4 8
3
0 40000 80000
0 50000 30000
50000 40000 60000
20000 30000 50000
80000 90000 50000
30000 40000 70000
3
0 4 6
5
0 50000 30000 40000 50000
0 30000 50000 60000 30000
10000 20000 30000 40000 50000
20000 30000 40000 50000 60000
0
출력 예제
Optimal resource allocation problem #1
Total budget: $80000
Total new programmers: 6
Total productivity increase: 210000
Division #1 resource allocation:
Budget: $0
Programmers: 2
Incremental lines of code: 60000
Division #2 resource allocation:
Budget: $40000
Programmers: 4
Incremental lines of code: 90000
Division #3 resource allocation:
Budget: $40000
Programmers: 0
Incremental lines of code: 60000
원문 보기 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=164
인천과고내신산출.exe
