E D R , A S I H C RSS

Adventures In Moving:PartIV

이 문제는

인기도:A(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:3(1~4)

About AdventuresInMoving:PartIV

워털루에서 대도시로 이사를 가려고 하는데, 이삿짐 트럭을 빌려서 갈까 생각 중이다. 그런데 요즘 기름 값이 하도 비싸서 가는데 기름 값이 얼마 정도 들지 미리 계산해보고자 한다.

이 트럭은 1킬로미터를 가는 데 1리터의 기름이 필요하다. 기름통은 200리터다. 워털루에서 트럭을 빌릴 때는 기름통이 절반만큼 차 있다. 나중에 대도시에서 차를 반납할 때도 기름은 절반 이상 채워 놓아야 한다. 그렇게 하지 않으면 렌탈 회사에 훨씬 비싼 비용을 지불해야 한다. 기름 값은 최대한 아끼고 싶지만, 그렇다고 해서 길 위에서 기름이 바닥나서 멈춰서는 일은 없도록 해야 한다.

Input

첫 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 입력되며, 그 다음 줄은 빈 줄이다. 각 테스트 케이스는 정수만으로 구성된다. 첫번째 정수는 워털루에서 대도시까지의 거리를 킬로미터 단위로 표시한 것으로, 최대 10,000이다. 그 밑으로는 출발지로부터 거리가 가까운 것부터 먼 것 순서로, 주유소에 대한 정보가 입력되며, 최대 100개까지 입력될 수 있다. 각 주유소에 대해 워털루로부터의 거리(킬로미터 단위)와 휘발유 1리터당 가격(0.1센트 단위)이 입력된다. 리터당 휘발유 값은 최대 2,000(즉 200센트 = 2달러)이다. 서로 다른 테스트 케이스 사이에는 빈 줄이 입력된다.

output

각 테스트 케이스에 대해 워털루에서 대도시까지 가는 데 드는 연료비의 최소 값을 출력한다. 문제의 제약조건에 따를 때 워털루에서 대도시까지 갈 수 없으면 "Impossible"이라고 출력한다. 서로 다른 테스트 케이스에 대한 결과 사이에는 빈 줄을 출력한다.

Sample Input

~cpp 
1

500
100 999
150 888
200 777
300 999
400 1009
450 1019
500 1399

Sample Output

~cpp 
450550

풀이

작성자 사용언어 개발시간 코드
문보창 C++ 2일 AdventuresInMoving:PartIV/문보창
김상섭 C++ 2주일 AdventuresInMoving:PartIV/김상섭

쓰레드

음. 나중에 대도시에서 차를 반납할 때도 기름은 절반 이상 채워 놓아야 한다. 여기서 절반 이상이라는 조건에 주의를 하지 않으면 안됩니다. -- 보창

Greedy한 선택이 안되는 반례

위의 테스트 케이스를 보면 처음에는 거리가 100인 주유소에 무조건 가야합니다. 그러면 기름은 0이 되고, 스터디때 말한 방법으로 하면 앞의 200까지를 살피고, 가장 작은 가격이 있는 곳인 (200, 777) 까지 갈 수 있는 기름 100을 넣고 출발합니다. 그러나 여기서 살펴보면 최적의 해는 여기서 50만큼의 기름만 넣고, 150의 지점에서 또 50의 기름을 넣어서 (200,777)에 가는 경우입니다. -- 보창
----
문제분류 / 경시대회준비반
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:18
Processing time 0.0974 sec