|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||256 MB||60||19||19||47.500%|
John is taking a long drive from Rawalpindi to Karachi along the Indus Highway. His car’s full fuel tank holds enough petrol to travel k kilometers. You have a map that gives distances between fuel stations along the route. Let d1 < d2 < … < dn be the locations of all the gas stations along the route where di is the distance from Rawalpindi to the fuel station i.
Your goal is to help John decide which petrol stations he should stop at for refueling along the path so that he has to take minimum stops. Assume that he starts with a full tank.
The input consists of multiple test cases. The first line of input is the number of test cases N(1≤N≤100). Each of the following N lines contain the total distance D from Rawalpindi to Karachi in kilometers (1≤D≤10000), the number of kilometers K that his car can travel with a full tank (1≤K≤10000), the total number of filling stations S along the route (1≤S≤100), followed by S integers representing (distance from Rawalpindi in kilometers) the positions of the filling stations.
For each test case, print a single line that saying “Case #n:” where n is the test case number followed by a space followed by space separated list of petrol pump locations where John should stop for refueling for that test case. If John is going to run out of petrol, say “out of petrol” for that case.
3 1397 450 10 250 433 449 700 800 950 1000 1200 1350 1395 1380 500 5 100 600 900 1100 1200 1000 100 3 300 600 900
Case #1: 449 800 1200 Case #2: 100 600 1100 Case #3: out of petrol