Inequality
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)Total Submission(s): 14 Accepted Submission(s): 1
Problem Description
Little Ruins is a studious boy, recently he learned inequation!
As homework, his teacher gives him a problem of inequation: give you an array a with length $N-1$, please find an array $x$ with length $N$ and $x_i \times x_{i+1} \geq a_i$ for each $i$ from $1$ to $N-1$ and try to minimize the sum of $x$.
As homework, his teacher gives him a problem of inequation: give you an array a with length $N-1$, please find an array $x$ with length $N$ and $x_i \times x_{i+1} \geq a_i$ for each $i$ from $1$ to $N-1$ and try to minimize the sum of $x$.
Input
First line contains an integer $T$, which indicates the number of test cases.
Every test case begins with an integers $N$, which is the length of array $x$.
The second line contains $N-1$ integers $a_1$, $a_2$, $\cdots$, $a_{N-1}$, indicating the array $a$.
Limits
$1 \leq T \leq 50$.
$1 \leq N \leq 2000$.
$0 < a_i \leq 10^4$.
For 80\% of the use cases, $1 \leq N \leq 100$ holds.
Every test case begins with an integers $N$, which is the length of array $x$.
The second line contains $N-1$ integers $a_1$, $a_2$, $\cdots$, $a_{N-1}$, indicating the array $a$.
Limits
$1 \leq T \leq 50$.
$1 \leq N \leq 2000$.
$0 < a_i \leq 10^4$.
For 80\% of the use cases, $1 \leq N \leq 100$ holds.
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.
Round the y to the fifth digit after the decimal point.
Round the y to the fifth digit after the decimal point.
Sample Input
2 4 2 3 2 4 1 2 3
Sample Output
Case #1: 5.77350 Case #2: 5.47723