시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1212 | 481 | 374 | 42.452% |
상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다.
A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다.
예를 들어, A를 5만큼, B를 3만큼, C를 7만큼 가지고 있고, 각 화학 제품의 가격은 다음과 같은 경우를 생각해보자.
화학 제품 | 단위 가격 |
---|---|
AB | \$100 |
BC | \$30 |
CA | \$80 |
A 하나와 B하나를 혼합해 AB 하나를 만들면 \$100을 얻게 된다. 그 다음 B 2개와 C 2개를 혼합하면 \$60을 얻게 되고, C 4개와 A 4개를 혼합해 \$320을 얻게 된다. 총 이익은 \$480이 되고 이 이익이 가능한 이익 중 최댓값이다. 한 화학 물질은 모두 사용하지 않을 수도 있다. 이 예제에서는 C를 하나 사용하지 않았다.
다른 예로, A가 3개, B가 3개, C가 3개가 있고, AB, BC, CA의 가격이 모두 \$100인 경우를 생각해보자. A 2개와 B 2개를 혼합해 \$200을 얻고, B 1개와 C 1개를 혼합해 \$100을 얻을 수 있다. 마지막으로 C 1개와 A 1개를 섞으면 \$100을 얻는다. 총 이익은 \$400이 되고, 이 값도 가능한 이익 중 최댓값이다.
상근이가 가지고 있는 A, B, C의 양과 AB, BC, CA의 가격이 주어졌을 때, 상근이가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 상근이가 가지고 있는 A, B, C의 양이 주어진다. 둘째 줄에는 AB, BC, CA의 가격이 주어진다. 입력으로 주어지는 모든 숫자는 정수이며, 1보다 크거나 같고, 1,000보다 작거나 같다.
각 테스트 케이스 마다 최대 이익을 출력한다.
2 5 3 7 100 30 80 3 3 3 100 100 100
480 400
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2011 B번