Curvy Little Bottles
Time limit1sMemory limit128 MB
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 -axis, the region under the graph of a polynomial between and . Thus the -axis runs vertically through the center of the bottle. The bottom of the bottle is a solid circular disk at , and the top of the bottle, at , is left open. The value of is greater than zero everywhere between and .
The volume of the bottle between and a height is . For example, the bottle formed by with and has a bottom circle of radius , a top opening of radius , and height .
Given a polynomial , the bounds and , and the volume increment between successive marks, compute the distances up from of the marks at successive volume increments. A mark cannot be placed past the top of the bottle, and no more than the first 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: , the degree of the polynomial, an integer with .
- Line 2: , the real coefficients of the polynomial , where is the constant term and is the coefficient of . For each , , and .
- Line 3: two real values and , the boundaries of the bottle, with and ; followed by , an integer volume increment between successive marks, with .
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 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 of the top of the bottle, that the volume of the bottle does not exceed , and that all rounded mark distances on a bottle differ by at least .