Curvy Little Bottles

Time limit1sMemory limit128 MB

Summary
Given a polynomial and x bounds that define a bottle of revolution, find the x positions where the cumulative volume hits each increment, up to 8 marks.
Level

Medium5 of 10

Topics
Math, Binary search, Implementation, Prefix sum
Solved
No attempts yet

Problem

On her bike rides around Warsaw, Jill came across a shop selling interesting glass bottles. She thought it would be a fun project to use such bottles for measuring liquids, but that would require placing marks on a bottle to indicate various volumes. Where should those volume marks go?

Jill formalized the problem as follows. A bottle is formed by revolving, around the xx-axis, the region under the graph of a polynomial PP between x=xlowx = x_{low} and x=xhighx = x_{high}. Thus the xx-axis runs vertically through the center of the bottle. The bottom of the bottle is a solid circular disk at x=xlowx = x_{low}, and the top of the bottle, at x=xhighx = x_{high}, is left open. The value of PP is greater than zero everywhere between xlowx_{low} and xhighx_{high}.

The volume of the bottle between xlowx_{low} and a height xx is ∫xlowxπ P(t)2 dt\int_{x_{low}}^{x} \pi\,P(t)^2\,dt. For example, the bottle formed by P(x)=4−0.25xP(x) = 4 - 0.25x with xlow=0x_{low} = 0 and xhigh=12x_{high} = 12 has a bottom circle of radius 44, a top opening of radius 11, and height 1212.

Given a polynomial PP, the bounds xlowx_{low} and xhighx_{high}, and the volume increment between successive marks, compute the distances up from xlowx_{low} of the marks at successive volume increments. A mark cannot be placed past the top of the bottle, and no more than the first 88 increments should be marked.

Input

The input contains several test cases, one after another, until end of file. Each test case consists of three lines of bottle data:

  • Line 1: nn, the degree of the polynomial, an integer with 0≤n≤100 \le n \le 10.
  • Line 2: a0,a1,…,ana_0, a_1, \ldots, a_n, the real coefficients of the polynomial PP, where a0a_0 is the constant term and aia_i is the coefficient of xix^i. For each ii, −100≤ai≤100-100 \le a_i \le 100, and an≠0a_n \ne 0.
  • Line 3: two real values xlowx_{low} and xhighx_{high}, the boundaries of the bottle, with −100≤xlow<xhigh≤100-100 \le x_{low} < x_{high} \le 100 and xhigh−xlow>0.1x_{high} - x_{low} > 0.1; followed by incinc, an integer volume increment between successive marks, with 1≤inc≤5001 \le inc \le 500.

Output

For each test case, print two lines. On the first line, print the case number and the volume of the full bottle, in the form Case k: V. On the second line, print the increasing sequence of at most 88 successive distances up from the bottom of the bottle for the volume marks, separated by single spaces. All volumes and distances must be accurate to two decimal places. If the bottle does not have enough volume for even one mark, print insufficient volume on the second line instead.

It is guaranteed that no mark falls within 0.010.01 of the top of the bottle, that the volume of the bottle does not exceed 10001000, and that all rounded mark distances on a bottle differ by at least 0.050.05.

Examples1

  1. Example 1

    Input
    1
    4.0 -0.25
    0.0 12.0 25
    1
    4.0 -0.25
    0.0 12.0 300
    0
    1.7841241161782
    5.0 10.0 20
    0
    1.0
    0.0 10.0 10
    
    Expected output
    Case 1: 263.89
    0.51 1.06 1.66 2.31 3.02 3.83 4.75 5.87
    Case 2: 263.89
    insufficient volume
    Case 3: 50.00
    2.00 4.00
    Case 4: 31.42
    3.18 6.37 9.55