prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem F:</font> Atomic Car Race</H1>3 4<p>5In the year 2020, a race of atomically energized cars will be held. Unlike today’s car races, fueling6is not a concern of racing teams. Cars can run throughout the course without any refueling.7Instead, the critical factor is tire (tyre). Teams should carefully plan where to change tires of8their cars.9</p>10<p>11The race is a road race having n checkpoints in the course. Their distances from the start are <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ... , and <i>a<sub>n</sub></i> (in kilometers). The <i>n</i>-th checkpoint is the goal. At the <i>i</i>-th checkpoint (<i>i</i> &lt; <i>n</i>),12tires of a car can be changed. Of course, a team can choose whether to change or not to change13tires at each checkpoint. It takes <i>b</i> seconds to change tires (including overhead for braking and14accelerating). There is no time loss at a checkpoint if a team chooses not to change tires.15</p>16<p>17A car cannot run fast for a while after a tire change, because the temperature of tires is lower18than the designed optimum. After running long without any tire changes, on the other hand,19a car cannot run fast because worn tires cannot grip the road surface well. The time to run20an interval of one kilometer from <i>x</i> to <i>x</i> + 1 is given by the following expression (in seconds).21Here <i>x</i> is a nonnegative integer denoting the distance (in kilometers) from the latest checkpoint22where tires are changed (or the start). <i>r</i>, <i>v</i>, <i>e</i> and <i>f</i> are given constants.23</p>24 25<pre>261/(<i>v</i> - <i>e</i> &times; (<i>x</i> - <i>r</i>)) (if <i>x</i> &ge; <i>r</i>)271/(<i>v</i> - <i>f</i> &times; (<i>r</i> - <i>x</i>)) (if <i>x</i> &lt; <i>r</i>)28</pre>29 30<p>31Your mission is to write a program to determine the best strategy of tire changes which minimizes32the total time to the goal.33 34</p>35 36<H2>Input</H2>37 38<p>39The input consists of multiple datasets each corresponding to a race situation. The format of a40dataset is as follows.41</p>42 43<pre>44<i>n</i>45<i>a</i><sub>1</sub> <i>a</i><sub>2</sub> . . . <i>a<sub>n</sub></i>46<i>b</i>47<i>r v e f</i>48</pre>49 50<p>51The meaning of each of the input items is given in the problem statement. If an input line52contains two or more input items, they are separated by a space.53</p>54 55<p>56<i>n</i> is a positive integer not exceeding 100. Each of <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ... , and <i>a<sub>n</sub></i> is a positive integer satisfying 0 &lt; <i>a</i><sub>1</sub> &lt; <i>a</i><sub>2</sub> &lt; . . . &lt; <i>a<sub>n</sub></i> &le; 10000. <i>b</i> is a positive decimal fraction not exceeding 100.0. <i>r</i> is a57nonnegative integer satisfying 0 &le; <i>r</i> &le; <i>a<sub>n</sub></i> - 1. Each of <i>v</i>, <i>e</i> and <i>f</i> is a positive decimal fraction.58You can assume that <i>v</i> - <i>e</i> &times; (<i>a<sub>n</sub></i> - 1 - <i>r</i>) &ge; 0.01 and <i>v</i> - <i>f</i> &times; <i>r</i> &ge; 0.01.59</p>60<p>61The end of the input is indicated by a line with a single zero.62</p>63 64 65<H2>Output</H2>66 67<p>68For each dataset in the input, one line containing a decimal fraction should be output. The69decimal fraction should give the elapsed time at the goal (in seconds) when the best strategy is70taken. An output line should not contain extra characters such as spaces.71</p>72<p>73The answer should not have an error greater than 0.001. You may output any number of digits74after the decimal point, provided that the above accuracy condition is satisfied.75</p>76 77<H2>Sample Input</H2>78<pre>792802 3811.0821 1.0 0.1 0.3835845 10 15 20 25850.15861 1.0 0.04 0.58710881783 3640 3991 4623 5465 5481 6369 6533 6865 8425894.1729072 59.4705 0.0052834 0.061122491092</pre>93 94<H2>Output for the Sample Input</H2>95<pre>963.53979731.924998168.668299</pre>100 101 102 103 104