5638번 - 수문 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 256 | 99 | 81 | 36.818% |
문제
댐은 n개의 수문을 가지고 있다. 각각의 수문은 자체 용량과 물길을 가지고 있고, 하류에 영향을 줄 수 있다.
수문이 열렸을 때, 영향을 받는 지역은 홍수의 위험이 있다. 수문에 의한 예상 피해액은 지역의 인구의 수와 면적으로 계산할 수 있다.
수문 Gi의 유량이 Fi m3/hour 이고, 피해 비용이 Ci라고 하자. 댐에는 물이 Vm3 만큼 저장되어 있고, 이 물을 T시간 이내에 모두 비워내야 하는 상황이다. 이때, 수문을 어떻게 열어야 피해 비용이 최소가 되는지를 구하는 프로그램을 작성하시오.
예를 들어, 댐에 수문이 4개가 있고, 각 수문의 유량과 피해 비용이 아래와 같다고 하자.
| 수문 | G1 | G2 | G3 | G4 |
|---|---|---|---|---|
| 유량 (m3/hour) | 720,000 | 50,000 | 130,000 | 1,200,000 |
| 비용 | 120,000 | 60,000 | 50,000 | 150,000 |
물 5백만 m3을 7시간 안에 비워내야 하는 경우에, G1을 7시간동안 열어 놓으면 되고, 비용은 120,000이 된다.
물 5백만 m3을 30시간 안에 비워내야 하는 경우에는 G2를 29시간, G3를 28시간 동안 열어 놓으면 된다. 이때의 비용은 110,000이 된다.
모든 수문은 항상 독립적으로 동작하며, 수문은 항상 1시간 단위만큼 열 수 있다.
입력
첫째 줄에 수문의 개수 n이 주어진다. (1 ≤ n ≤ 20) 다음 n개 줄에는 각 수문 Gi의 유량 (m3/hour) Fi와 피해 비용 Ci가 주어진다. 다음 줄에는 테스트 케이스의 수 m (1 ≤ m ≤ 50)이 주어진다. 다음 m개 줄에는 V와 T가 주어지며, 물 V m3을 T시간 이내에 비워내야 한다는 뜻이다. (1 ≤ Fi, V, Ci ≤ 109, 1 ≤ T ≤ 1000)
출력
각 테스트 케이스마다, 최소 비용을 예제 출력과 같이 출력한다. 만약 물 V를 T시간 이내에 비워낼 수 없으면 "IMPOSSIBLE"을 출력한다.
예제 입력 1
4 720000 120000 50000 60000 130000 50000 1200000 150000 3 5000000 7 5000000 30 63000000 24
예제 출력 1
Case 1: 120000 Case 2: 110000 Case 3: IMPOSSIBLE
출처
ICPC > Regionals > Asia Pacific > Thailand > 2011 ACM-ICPC Asia Phuket Regional Programming Contest A번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호