The PDF version of this problem can be downloaded here.
You have a special pizza oven, named as Automatic Cooking Machine - Immediately Completing Pizza Cooker (ACM-ICPC). This pizza oven can bake one pizza at a time. No matter the amount of cheese or the size of pizza, the oven can automatically heat the pizza with the most suitable temperature, and nish baking almost immediately. You always turn on the pizza oven at time 0, and turn it off at time m.
Every thing works well except one flaw in the ACM-ICPC. The pizza oven will explode if no pizza is sent into it in k consecutive time units. Moreover, your cook has a weird habit that he only makes pizza in n certain time points: a1, ... , an. That is, at each time ai, your cook will make one pizza and send it into the pizza oven. Then, the pizza oven returns to your cool a well-baked pizza at time ai + ε , ε < 1.
In order to prevent the oven explodes, you have to pay for adjusting the pizza-making time. Your cook asks for |ai - a'i| dollar to adjust ai to a'i. Also, your cook
refuses to make more pizzas, and he cannot make two pizzas at the same time. What is the minimum cost you have to pay to keep the oven from explosion?
The first line of the input file contains an integer T (1 ≤ T ≤ 50) indicating the number
of test cases.
For each test case, the first line contains three integers n, m, and k (1 ≤ n ≤ 250000,
1 ≤ k ≤ m ≤ 109). The following line contains n integers, a1, ... , an (0 ≤ a1 < ... < an ≤ m). Note that all the adjusted a'i must also be integers.
For each test case please output the minimum cost as required, or BOOM if it is impossible to prevent explosion.
2 2 9 3 4 7 1 5 2 3
2 BOOM
Migrated from old NTUJ.
tmt514
| No. | Testdata Range | Score |
|---|