Cucumber Conundrum

A jar of sliced pickled cucumber. Author: W.carter, License: CC BY-SA 4.0
Maj loves pickled cucumber (also known as pickles). However, her partner is not as keen on filling a sandwich with pickles. Maj would like to maximize the amount of pickles on a sandwich, while still avoiding being judged by her partner.

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?


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 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
Sample Input 2 Sample Output 2
3 1 4 100
CPU Time limit 1 second
Memory limit 1024 MB
Johan Sannemo
Source LTH Challenge 2017
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in