10198번 - Crossing River 다국어

Doctor Nefario is planning a trip after spending a lot of time doing research in his lab. During the trip he needs to cross a river. Fortunately there are N rocks in the river lying on a straight line across the river that may be used to make the crossing. The width of the river (i.e., the total distance that needs to be crossed) is L.

Doctor Nefario’s scooter can hover in the air, but to make the river crossing he wants to build a rocket booster that can make longer jumps. The cost of a rocket booster depends on its quality. More precisely, a rocket booster that can boost jumps up to distance R costs R². The booster may be used multiple times, but each jump costs an additional amount C.

For example, if Doctor Nefario builds a rocket booster that can boost jumps up to distance 10 and uses it to make 5 jumps, the total cost would be 10² + 5 × C = 100 + 5C.

Given the width of the river L, the cost of each jump C, and the location of N rocks, your goal is to find the minimum cost M for Doctor Nefario to cross the river, the number of jumps J needed, and the range R selected for the rocket booster.

For instance, in the figure above Doctor Nefario needs to cross a river of width 6. There are 4 rocks at distances 1, 2, 3, and 5. One possible solution is to build a rocket booster with range 3, which would allow the scooter to cross the river with two jumps.

The parameters of this problem may be quite large: 1 ≤ L ≤ 10⁹, 0 ≤ C ≤ 10⁶, and 0 ≤ N < 1000. Your implementation should represent these values using long instead of int. Exhaustively checking all possible values for range R will not work in the time allowed.

The input consists of multiple test cases. The first line of each test contains three integers L, C and, N: the width of the river, cost of each jump, and the number of rocks, respectively. Each of the next N lines contains an integer specifying the distance of a rock. The input terminates with a line containing just 0.

For each test case, print the minimum cost of crossing the river in the following format: Minimum cost M achieved with J jumps of range R

정확한 출력 형식은 제출에서 언어를 Java로 설정하면 확인할 수 있다.