시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB222100.000%

문제

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}$.

예제 입력 1

3 1 4 40

예제 출력 1

3

예제 입력 2

3 1 4 100

예제 출력 2

4

출처

Contest > Swedish Coding Cup > LTH Challenge 2017 C번

  • 문제를 만든 사람: Johan Sannemo