Problem C
Cucumber Conundrum
Both Maj’s sandwich and the pickles have a circular shape. The sandwich has radius $s$ cm and the pickles have radius $r$ cm.
Maj has exactly $n$ pickles. She wants to place as many of them as possible on her sandwich, as long as:
-
at most $z \% $ of the area of the sandwich is covered by pickles.
-
no two pickles overlap (but they are allowed to touch).
How many pickles can Maj place on her sandwich?
Input
The input consists of:
-
one line with the decimal numbers $s$ and $r$ ($1 \le s \le 10$, $0.5 \le r \le s$, at most $6$ digits after the decimal point), the radius of the sandwich and the radius of a pickle, in centimetres.
-
one line with the integers $n$ and $z$ ($1 \le n \le 7$, $0 \le z \le 100$), the number of pickles Maj have, and the maximum area she may cover with them, in percent.
Output
Output the maximum number of pickles Maj can place on her sandwich. The input will always be constructed such that this number does not change if the radius of the sandwich increases or decreases by $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 4 40 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 4 100 |
4 |
