ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2012, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Titan Ruins: Overtaking Fire

Time limit: 1.0 second
Memory limit: 64 MB
Soren walked around the room looking for hidden exits but didn't find any.
`Seems like we have to go down this tunnel.'
`It can be a long way...' Alba sighed.
`I have an idea! Look at this cart, we can roll down in it, that'll be much faster.'
So they did. Luckily, the floor in the tunnel was smooth and even, and, though the tunnel's walls were quite close to the cart, there was still enough space to go without any difficulties.
A few minutes later a strange noise captured Soren's attention. He turned around and saw a huge wall of fire following them and getting closer and closer. Apparently, they somehow activated a trap.
`Listen, we have to do something about this thing or it will burn us...'
`Well, I can put up a magic shield that will keep the fire behind the cart. But it'll take a lot of energy and I can't see where this tunnel ends.'
`Are you a wizard or what? Use the Space Scanning Spell!'
`Right you are... Ok, there are some side tunnels down the tunnel. We can turn to one of them, so that the fire will pass us by. But the floor in the side tunnels is not as smooth as here, and the cart will slow down.'
`That's good, if you think of it. We don't want to return to the tunnel until the whole fire wall has gone ahead of us. Maybe we'll even have to cast the Deceleration Spell inside the side tunnel. Even if the cart stops completely and we have to go by foot it will still be better than death.'
Meanwhile, the wall of fire continued to approach the cart. Time was running out, and a plan had to be developed fast. Wizards can turn to a side tunnel only once because the cart is very old and not suited well for making turns. But which tunnel to use?
The friction in the tunnel is such that the cart moves at a constant speed. In all the side tunnels, however, the cart moves with the same constant deceleration. In addition, Alba and Soren can use the Deceleration Spell to increase the roughness of the floor in any particular side tunnel (and thus increase the deceleration in that side tunnel). The spell can be cast at different power levels, increasing the deceleration proportionally to the amount of magic energy spent. The cart decelerates only when it is fully inside of a side tunnel. The Shield Spell can be cast when the fire is right behind the cart and makes the fire stay there, but this spell requires a constant supply of magic energy. There is no need to use the Shield Spell while the cart is fully inside of a side tunnel.


The first line contains eight integers: v is the speed of the cart, l is its length, V is the speed of the fire wall if it is not kept back by a magic shield, L is the depth of the fire wall, D is the current distance from the fire wall to the cart's back end, a is the cart's deceleration due to the roughness of the side tunnel floor, k is the amount of magic energy needed to sustain a magic shield behind the cart for one second, and c is the amount of magic energy consumed by the Deceleration Spell to increase deceleration by 1 m/s2, (0 < v, V, a, l, L, D < 105; v < V; 0 ≤ k, c ≤ 104).
The second line contains the number of side tunnels n (1 ≤ n ≤ 1 000). In each of the next n lines there are two integers li and ri; they are the distances from the front of the cart to the beginning and to the end of the corresponding side tunnel (0 < li; li + l < ri < li+1; ri < 105).
All the distances are given in meters (m), the speeds are given in meters per second (m/s), and the units for the deceleration are meters per second squared (m/s2). The cost of the Shield Spell is given in magic energy units per second, and the cost of the Deceleration Spell is given in magic energy units per deceleration units.


Output the least possible amount of magic energy that the wizards will have to spend to escape the fire wall. The answer must be given with absolute or relative error not exceeding 10−5.


1 1 2 1 1 100 1 1234
100 102
Problem Author: Denis Dublennykh
Problem Source: NEERC 2012, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1911. Titan Ruins: Overtaking Fire