Problem E
Skattaskrattar
Languages
en
is
When people earn wages they have to pay taxes on them to the government. To calculate how much they should pay, the wages are divided into tax brackets that the government announces, but in each bracket a certain percentage of the wages that fall into that bracket have to be paid.
Let us take an example with three tax brackets:
Bracket |
Wages |
Tax percentage |
$1$ |
$0$ kr. – $1\, 000$ kr. |
$40\% $ |
$2$ |
$1\, 000$ kr. – $5\, 000$ kr. |
$30\% $ |
$3$ |
$5\, 000$ kr. and above |
$50\% $ |
Let us presume some person gets $3\, 000$ kr. as wages. The wages completely cover the first bracket ($1\, 000$ kr. being in that bracket) and the rest into the second ($2\, 000$ kr. in that bracket). That person thus pays $40\% $ of the first $1\, 000$ kr. of the wages and $30\% $ of the next $2\, 000$ kr. of the wages. In total that’s $0.4 \cdot 1\, 000 + 0.3 \cdot 2\, 000 = 1\, 000$ that has to be paid in taxes.
On the other hand, had the person gotten $5\, 500$ kr. in wages, the wages would have covered the first bracket ($1\, 000$ kr. in that bracket), covered the second bracket ($4\, 000$ kr. in that bracket) and the rest had gone into the third ($500$ kr. in that bracket). In total that would have been $0.4 \cdot 1\, 000 + 0.3 \cdot 4\, 000 + 0.5 \cdot 500 = 1\, 850$ that has to be paid in taxes.
The year is $3020$, and even though skyscrapers stand proudly in Reykjavík and flying cars park in hovering parking spaces for a hefty fee, the same tax bracket system is still in use. The number of brackets has increased though, now there are $n$ brackets. The first bracket ranges from $0$ to $a_1$ kr., the second from $a_1$ to $a_2$ kr., and so on until the $n$-th tax bracket that holds from $a_{n-1}$ and up. The first tax bracket has a tax percentage of $p_1\% $, the second has a percentage of $p_2\% $ and so on until tax bracket $n$ which has a tax percentage of $p_ n\% $.
The president has been looking into how the tax brackets for $3021$ should look. He has an idea with $m$ tax brackets and they are described as above except we denote the thresholds with $b_ i$ instead of $a_ i$ and the tax percentages are denoted by $q_ i$ instead of $p_ i$. If these tax brackets were to be put into use next year, the president has asked you to find all wages he could pay his employees that would have them pay the same taxes in $3020$ and $3021$. Wages can be any real number, as long as they are not negative, but the tax brackets are always positive integers.
Input
The first line of the input contains two integers $n$ and $m$ ($1 \leq n,m \leq 10^5$), the number of tax brackets in the years $3020$ and $3021$.
Then there are $n$ lines describing the tax brackets in $3020$. The first $n - 1$ lines contain two positive integers $p_ i$ and $a_ i$. Then there is a single line with the integer $p_ n$ ($0 < p_ i < 100$ for all $i$).
Then there are $m$ lines denoting the tax brackets in $3021$. The first $m - 1$ lines contain two positive integers $q_ i$ and $b_ i$. Then there is a single line with the integer $q_ m$ ($0 < q_ i < 100$ for all $i$).
The tax brackets are given in increasing order, i.e. $a_ i < a_{i+1}$ and $b_ i < b_{i+1}$, and no tax bracket goes beyond $10^5$ kr., i.e. $a_{n-1}, b_{m-1} \leq 10^5$.
Output
The output should contain all wages that pay the same tax in both tax bracket systems, given in increasing order. If wages $x$ pay the same taxes in both tax systems, it is guaranteed that no other such wages exist in the interval $[x - 10^{-4}, x + 10^{-4}]$.
The output is considered correct if each value has an absolute or relative error of at most $10^{-4}$. This means it doesn’t matter how many significant digits the answer contains as long as it’s accurate enough.
Scoring
Group |
Points |
Constraints |
1 |
40 |
$n,m \leq 10^3$ |
2 |
60 |
No further constraints |
Sample Input 1 | Sample Output 1 |
---|---|
3 2 40 1000 30 5000 50 20 500 80 |
0.000000000000000 750.000000000000000 |
Sample Input 2 | Sample Output 2 |
---|---|
2 3 71 14 42 43 5 6 49 20 |
0.000000000000000 |
Sample Input 3 | Sample Output 3 |
---|---|
5 5 86 874 10 2170 18 5738 99 5891 76 98 497 31 3229 75 7670 58 8394 60 |
0.000000000000000 605.436363636363581 1577.380952380952294 17815.375000000003638 |