|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||9||9||8||100.000%|
Lord Cohen is a baron with the best-looking hedge in the country. His award-winning hedge consists of N bushes planted side by side in a straight line. The bushes are numbered left to right from 1 to N. The baron's neighbours all cut their own hedges so that all of their bushes have the same height. But Lord Cohen has a secret key to his landscaping success. His gardener follows a special rule when trimming the hedge, which is why the baron's hedge is always in its award-winning condition.
The rule is -- to start on the left at bush #2 and move to the right. The gardener cuts the top of each bush to make it exactly as tall as the average of the two bushes on either side. If the bush is already as short as the average or shorter, then the gardener does not touch this bush and moves on to the next bush on the right, until the second-to-last bush. The baron is certain that this procedure is the key to success.
The first line of the input gives the number of test cases, T. T test cases follow. Each one consists of two lines. The first line will contain an integer N, and the second line will contain N space-separated integers denoting the heights of the bushes, from bush #1 to bush #N.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the height of bush number N - 1 after the gardener has finished trimming the hedge according to the baron's special procedure.
Answers with a relative error of at most 10-4 will be considered correct.
6 5 1 2 3 6 7 5 1 2 3 4 7 3 7 7 7 5 7 8 7 9 9 5 5 8 9 9 9 6 1 2 2 2 2 2
Case #1: 5.000000 Case #2: 4.000000 Case #3: 7.000000 Case #4: 8.000000 Case #5: 8.500000 Case #6: 1.937500