Олимпиады по программированию

olympiads.ru

II Всероссийская заочная олимпиада школьников по информатике, 2007/08 учебный год

Задача D. Муха (OFF-LINE проверка)

Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.

Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.

Напишите программу, которая определит, есть ли у мухи шанс спастись, и если есть, то выведет, что должна муха для этого делать.

Формат входных данных

Во входном файле заданы числа V, W, A, T, C, D. Все числа целые. 0≤V≤W≤1000, 0≤A≤1000, 0<T≤1000, -1000000≤C≤D≤1000000.

Формат выходных данных

Если муха может спастись, выведите, как она должна для этого лететь. Для этого выведите последовательность команд для мухи. Количество команд не должно превышать 100. Каждая команда задается двумя числами Ti, Ai, которые обозначают, что в течение времени Ti муха должна лететь с ускорением Ai. Ti и Ai не обязаны быть целыми, Ti должны быть положительны (не могут быть равны 0), сумма всех Ti должна быть равна T с точностью до 10^-6.

Если, в рамках указанных ограничений, муха спастись не сможет, в выходной файл выведите одно число -1 (минус 1).

Примечания

Муха может сначала снизить скорость до 0, а затем полететь в обратную сторону (см. примеры).

Если в момент времени T муха окажется на концах отрезка, т.е. в точке C или D, она все равно погибнет.

Примеры

10 10 5
1 -100 100

-1

10 20 5
1 9 11

0.2 0
0.8 4

10 10 5
5 0 1000

4 -5
1 0