300984: CF186B. Growing Mushrooms

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Growing Mushrooms

题目描述

Each year in the castle of Dwarven King there is a competition in growing mushrooms among the dwarves. The competition is one of the most prestigious ones, and the winner gets a wooden salad bowl. This year's event brought together the best mushroom growers from around the world, so we had to slightly change the rules so that the event gets more interesting to watch. Each mushroom grower has a mushroom that he will grow on the competition. Under the new rules, the competition consists of two parts. The first part lasts $ t_{1} $ seconds and the second part lasts $ t_{2} $ seconds. The first and the second part are separated by a little break. After the starting whistle the first part of the contest starts, and all mushroom growers start growing mushrooms at once, each at his individual speed of $ v_{i} $ meters per second. After $ t_{1} $ seconds, the mushroom growers stop growing mushrooms and go to have a break. During the break, for unexplained reasons, the growth of all mushrooms is reduced by $ k $ percent. After the break the second part of the contest starts and all mushrooms growers at the same time continue to grow mushrooms, each at his individual speed of $ u_{i} $ meters per second. After a $ t_{2} $ seconds after the end of the break, the competition ends. Note that the speeds before and after the break may vary. Before the match dwarf Pasha learned from all participants, what two speeds they have chosen. However, the participants did not want to disclose to him all their strategy and therefore, did not say in what order they will be using these speeds. That is, if a participant chose speeds $ a_{i} $ and $ b_{i} $ , then there are two strategies: he either uses speed $ a_{i} $ before the break and speed $ b_{i} $ after it, or vice versa. Dwarf Pasha really wants to win the totalizer. He knows that each participant chooses the strategy that maximizes the height of the mushroom. Help Dwarf Pasha make the final table of competition results. The participants are sorted in the result table by the mushroom height (the participants with higher mushrooms follow earlier in the table). In case of equal mushroom heights, the participants are sorted by their numbers (the participants with a smaller number follow earlier).

输入输出格式

输入格式


The first input line contains four integer numbers $ n $ , $ t_{1} $ , $ t_{2} $ , $ k $ $ (1<=n,t_{1},t_{2}<=1000; 1<=k<=100) $ — the number of participants, the time before the break, the time after the break and the percentage, by which the mushroom growth drops during the break, correspondingly. Each of the following $ n $ lines contains two integers. The $ i $ -th $ (1<=i<=n) $ line contains space-separated integers $ a_{i} $ , $ b_{i} $ $ (1<=a_{i},b_{i}<=1000) $ — the speeds which the participant number $ i $ chose.

输出格式


Print the final results' table: $ n $ lines, each line should contain the number of the corresponding dwarf and the final maximum height of his mushroom with exactly two digits after the decimal point. The answer will be considered correct if it is absolutely accurate.

输入输出样例

输入样例 #1

2 3 3 50
2 4
4 2

输出样例 #1

1 15.00
2 15.00

输入样例 #2

4 1 1 1
544 397
280 101
280 101
693 970

输出样例 #2

4 1656.07
1 937.03
2 379.99
3 379.99

说明

- First example: for each contestant it is optimal to use firstly speed 2 and afterwards speed 4, because $ 2·3·0.5+4·3&gt;4·3·0.5+2·3 $ .

Input

加入题单

上一题 下一题 算法标签: