CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Roller coaster

Time limit: 2.00 s
Memory limit: 512 MB

You have designed a brand new roller coaster for the Aaltomäki amusement park. Your design consists of $N$ track segments, each of them typically a part in which the train first goes uphill and then back downhill. For each track segment, you got its technical specifications from the amusement engineers, as four numbers, $P$ , $R$ , $A$ and $F$ .

These are to be interpreted as follows:

The train that enters the track segment has to run at speed at least $R$ (or it fails to even climb uphill, which would be bad).
To make the customers really happy during this track segment, the train should have speed at least $P$ when entering the track segment.
Some kinetic energy is lost due to friction and other losses, and here the change of speed can be approximated as follows: if the train enters the track segment at speed $x$ , it will leave the track segment at speed $x - A - x \cdot F/100$ . That is, you lost $A$ units of speed and $F$ percent of speed.

Now your task is to find the right starting speed $x$ for the roller coaster train in the beginning of the track, so that when the train goes through all track segments the following holds:

You meet the minimum speed requirement $R$ for every track segment.
You meet the happiness requirement $P$ for at least 50% of track segments.
Your choice of $x$ is as small as possible.

All input values here are integers; speeds are here represented as meters per hour, and our roller coaster trains can easily travel at supersonic speeds if that is what is needed for sufficient amount of happiness, so the numbers can get pretty large. Your answer $x$ has to be also an integer, and the answer has to be exact (i.e., the smallest possible integer $x$ that satisfies all the constraints when you calculate the speed as an exact rational number after each segment). The input is guaranteed to be such that a solution always exists.

Input:

One line with the number $N$ , the number of segments. Then $N$ lines that describe the segments from first to last; each line consists of the four numbers $P$ , $R$ , $A$ , and $F$ , separated by spaces.

Output:

One line with the number $x$ , the smallest speed that meets the requirements.

Limits:

$1 \leq N \leq 10$

$0 \leq A \leq R \leq P \leq 1000000$

$0 \leq F \leq 99$

Example 1

Input:

3
1000 5 5 0
20 20 20 50
50 50 0 99

Output:

Explanation:

If you start with speed $145$ , the following happens:

You enter the $1^{st}$ segment with speed $145$ and leave it with speed $140$ (speed reduced by $5$ units)
You enter the $2^{nd}$ segment with speed $140$ and leave it with speed $50$ (speed reduced by $20$ units and by extra $50%$ )
You enter the $3^{rd}$ segment with speed $50$ and leave it with speed $0.5$ (speed reduced by $99%$ )

This way you meet the input speed requirement $R$ in each segment and also the happiness requirement $P$ for the $2^{nd}$ and $3^{rd}$ segment. As there are $3$ segments and $2$ of them make customers happy, it is enough for the $50%$ happiness requirement, too. So $145$ is certainly a valid starting speed here. You can check that none of the lower speeds will work.

Example 2