508. Black-white balls
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
n black and white balls were put into a bag. Petya doesn't know exactly how many black balls are there among them. He knows, however, that there are 0, 1,...,
n black balls among all balls in the bag with equal probability.
Petya took
l balls from the bag at random, and
l1 of them turned out black, while
l2 other turned out white (
l1 +
l2 =
l). Now he wants to predict how many black balls were there initially in the bag. Of course, if
l <
n, he can't be sure in his prediction, but he wants to predict a segment [a,
b], such that the amount
k of black balls belongs to it with probability at least
p.
You are given
n,
l1,
l2 and
p, and you must find such
a and
b that
b -
a is minimal possible. If there are several such pairs (
a,
b), choose the one with the smallest
a.
Input
In the first line there are four integer numbers: 1 ≤
n ≤ 50 — the number of balls in the bag, 0 ≤
l1 ≤
n — the number of black balls out of the
l balls that Petya took from the bag, 0 ≤
l2 ≤
n -
l1 — the number of white balls that Petya took from the bag, 0 ≤
p ≤ 100 — the required confidence in percent.
Output
Output numbers
a and
b separated by a space, 0 ≤
a ≤
b ≤
n.
Example(s)
sample input | sample output |
50 1 24 100
| 1 26
|
sample input | sample output |
50 1 49 100
| 1 1
|
sample input | sample output |
50 1 10 95
| 1 15
|