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
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
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
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
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
Problem Author: Denis Dublennykh
Problem Source: NEERC 2012, Eastern subregional contest