Problem A
Food Mixing
The Volbonans of the Luncheon Kingdom are cooking their famous Stupendous Stew! For the Volbonans, Stupendous Stew is simply any soup that has saltiness level $x$ and sweetness level $y$.
However, Bowser has stolen all of their ingredients! All they have left are existing soups: $n$ soups of varying salt levels $a_1,a_2,\dots ,a_ n$ and sweetness levels $b_1,b_2,\dots ,b_ n$. The Volbonans are attempting to salvage the situation by mixing their soups into a Stupendous Stew.
The saltiness and the sweetness of a mixture of soups is given by the weighted sum of the soups used to make it. For example if a mixture consisted of $75\% $ of a soup of $3$ saltiness and $25\% $ of a soup of $5$ saltiness, it would have a saltiness of $3.5$.
More formally, for each soup $i = 1, \ldots , n$, let $p_ i$ ($0 \leq p_ i \leq 1$) denote the proportion of soup $i$ used in a mixture. Then, the saltiness of the mixture is given by $\sum _{i=1}^ n p_ ia_ i$ and the sweetness is $\sum _{i=1}^ n p_ ib_ i$. The sum of all $p_ i$ must be $1$.
Tell the Volbonans if they can make Stupendous Stew. If they can, tell them how to make it.
Input
The first line of input is an integer $1 \leq n \leq 100\, 000$, representing the number of existing soups. The following line contains $n$ integers $a_1,a_2,\ldots ,a_ n$ ($0\leq a_ i\leq 1\, 000$), the saltiness levels of the $n$ soups. The following line contains $n$ integers $b_1,b_2,\ldots ,b_ n$ ($0\leq b_ i\leq 1\, 000$), the sweetness levels of the $n$ soups. The last line contains integers $x$ and $y$ ($0\leq x,y \leq 1\, 000$), the target saltiness and sweetness levels.
Output
If it is possible to make the Stupendous Stew, on the first line print “Yes” followed by a second line with proportions of each soup used in the mixture $p_1, p_2, \dots , p_ n$. Otherwise, print “No”.
If it is possible to make the Stupendous Stew, your answer will be accepted if both the sweetness of your mixture and the saltiness do not exceed an absolute or relative error of $10^{-6}$.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 2 4 5 1 1 1 3 3 2 |
Yes 0.5 0.0 0.0 0.5 |
Sample Input 2 | Sample Output 2 |
---|---|
4 1 2 4 5 1 1 1 4 3 2 |
Yes 0.4444444 0.0000000 0.2222222 0.3333333 |
Sample Input 3 | Sample Output 3 |
---|---|
3 7 8 7 8 7 7 8 8 |
No |