TopCoder Statistics - Problem Statement

Problem Statement

The creek bed is dry. We are given the elevation of the creek bed every 50 feet horizontally along its course, west to east. Our town is located in a valley just to the east of the last elevation. It has just started raining at a rate of r inches per hour over the entire creek bed. (This means that in a volume with straight sides and a flat bottom the water level would rise r inches per hour.)

We can treat this as a 2-dimensional problem by approximating the creek as having a constant width. We will assume that the creek bed is made up of linear segments between the known elevations. We will also treat the water as flowing instantaneously.

Given r, and a int[] ht giving the elevations (in feet) in order from west to east, return the number of hours before the water starts flooding the town.

Definition

Class:: FlashFlood
Method:: hours
Parameters:: int, int[]
Returns:: double
Method signature:: double hours(int r, int[] ht)
(be sure your method is public)

Notes

The conversion between feet and inches is 12 inches = 1 foot.
A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

r will be between 1 and 100, inclusive.
ht will contain between 2 and 50 elements, inclusive.
Each element of ht will be between 0 and 5000, inclusive.
The elements of ht will have distinct values.
At least one element of ht will be greater than its last element.

Examples

7

{150,140}

Returns: 0.0

All the rain that falls in the creek bed immediately flows into town.
7

{160,140,150}

Returns: 6.428571428571427

160 / \ / \ \^^^^^^^^^150 \^^^^^^^/ \^^^^/ (Town) 140 -----+------+------+------ The water will build up in a triangular region until its height reaches 150. The picture shows the water at the crucial moment. The horizontal width of the triangle is (25+50) and its altitude is 10 so its area is 75*10/2 = 375. All the rain that falls on the 100 foot long creek bed goes into this region, so every hour the area of water increases by 100*(7/12) square feet. So the region will be full and start flooding the town in 375 / (700/12) = 45/7 hours.
12

{110,170,175,155,160,140,150}

Returns: 2.6562500000000018

175 / \ / \ \ 160 \ / \ 155 \ \ 150 \ / 140 (town) -----+------+------+------+------+----- Before the easternmost triangular region fills up, the triangular region just to its west will fill up. So flooding will begin when the water level is 150 in the easternmost region and 160 in the region to its west. The rain falling on the first 100 feet of creek (not shown in the picture) fortunately drains the other way, but all the rain on the remaining 200 foot long creek bed will contribute. So we calculate area/rain = [(62.5*5)/2 + (75*10)/2 ] / (200 * 12 / 12)
12

{110,170,175,155,160,161,140,150}

Returns: 2.4561904761904767
7

{4000,160,140,150}

Returns: 4.285714285714288
13

{ 4000, 3801, 3901, 3702, 3802, 3603, 3703, 3504, 3604, 3405, 3505, 3306, 3406, 3207, 3307, 3108, 3208, 3009, 3109, 2910, 3010, 2811, 2911, 2712, 2812, 2613, 2713, 2514, 2614, 2415, 2515, 2316, 2416, 2217, 2317, 2118, 2218, 2019, 2119, 1920, 2020, 1821, 1921, 1722, 1822, 1623, 1723, 1524, 1624 }

Returns: 34.67336683417088
11

{ 4003, 3805, 3895, 3701, 3796, 3604, 3704, 3497, 3602, 3401, 3499, 3296, 3398, 3196, 3295, 3098, 3195, 2995, 3105, 2896, 3003, 2799, 2902, 2702, 2802, 2596, 2705, 2502, 2602, 2405, 2503, 2295, 2404, 2201, 2299, 2101, 2199, 2000, 2100, 1900, 2002, 1797, 1897, 1700, 1796, 1604, 1702, 1500, 1600 }

Returns: 40.027955428791614
1

{ 3996, 3798, 3902, 3698, 3802, 3602, 3702, 3501, 3597, 3405, 3495, 3305, 3402, 3196, 3296, 3104, 3201, 2996, 3097, 2897, 3002, 2795, 2898, 2698, 2803, 2601, 2704, 2497, 2604, 2405, 2500, 2301, 2396, 2199, 2299, 2099, 2202, 1995, 2100, 1897, 2005, 1802, 1895, 1703, 1801, 1599, 1702, 1495, 1601 }

Returns: 449.57005491022187
2

{ 4011, 3829, 3928, 3701, 3815, 3633, 3728, 3500, 3596, 3415, 3537, 3318, 3421, 3200, 3328, 3103, 3233, 3027, 3143, 2913, 3020, 2839, 2926, 2736, 2833, 2626, 2711, 2510, 2616, 2410, 2543, 2313, 2425, 2197, 2320, 2113, 2216, 2037, 2111, 1939, 2043, 1819, 1924, 1704, 1827, 1604, 1700, 1523, 1614 }

Returns: 206.33449874591486
49

{ 3954, 3855, 3864, 3728, 3896, 3584, 3699, 3467, 3659, 3397, 3509, 3456, 3423, 3346, 3321, 3203, 3265, 3076, 3128, 2921, 3034, 2838, 2975, 2822, 2834, 2679, 2785, 2600, 2573, 2500, 2564, 2402, 2484, 2367, 2364, 2214, 2345, 1975, 2218, 1945, 2153, 1813, 1949, 1696, 1922, 1597, 1741, 1621, 1602, 1999 }

Returns: 17.896908774348233
29

{ 3986, 3807, 3883, 3930, 3787, 3852, 3988, 3810, 3843, 3898, 3788, 3832, 3924, 3743, 3847, 3915, 3651, 3778, 3856, 3724, 3786, 3837, 3688, 3769, 3794, 3685, 3770, 3859, 3625, 3689, 3754, 3586, 3694, 3797, 3560, 3638, 3792, 3561, 3639, 3749, 3575, 3617, 3672, 3476, 3630, 3700, 3525, 3628, 3668 }

Returns: 23.43802955665025
1

{ 5000, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 4999 }

Returns: 58487.38777959187
100

{5000,0,4000,3999,3998}

Returns: 0.0
48

{5000,0,4000,3998}

Returns: 0.0
20

{4400,4300,2000,2001,1999,2002,100,0,102}

Returns: 8.10014408174461
20

{2000,2001,1999,2002,100,0,102}

Returns: 20.600210304942166
39

{5000,2000,4500,4400,4401,4404,3000,3922}

Returns: 47.31178259916723
39

{5000,4403,4402,4405,4400,4401,4404,3000,3922}

Returns: 29.78230066616227
1

{3992,4403,4402,4405,4400,4401,4404,3000,3922}

Returns: 1848.807521367521
13

{155, 160, 145, 150, 135, 140, 125, 130, 159 }

Returns: 16.94945054945056

Statistics

Problem Statement for "FlashFlood"

Problem Statement

Definition

Notes

Constraints

Examples