NOI '99 P3 - Birthday Cake

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type
National Olympiad in Informatics, China, 1999

July 17th is Mr. W's Birthday, and ACM-THU would like to create for him a birthday cake with volume N\pi, comprised of M cylindrical layers.

Counting upwards from the bottom layer, the i-th (1 \le i \le M) layer of cake is a cylinder with a radius of R_i and a height of H_i. When i < M, we require for R_i > R_{i+1} and H_i > H_{i+1}.

To reduce the money spent on icing the cake, we would like to minimize Q, the outer surface area of the cake (not including the bottom surface of the bottommost layer).

Let Q = S\pi. Please write a program that, given N and M, finds a strategy to construct the cake (with appropriate R_i and H_i values) that minimizes the value of S.

Other than Q, all values described above will be positive integers.

Input Specification

The input will consist of two lines. The first line is the integer N (N \le 10\,000), indicating that the volume of the cake is N\pi. The second line of input is the integer M (M \le 20), representing the number of levels in the cake.

Output Specification

The output should consist of one line - a positive integer S (if no answer, S = 0).

Sample Input

100
2

Sample Output

68

Formulas for cylinders:

Volume: V = \pi R^2H
Side surface area: A' = 2\pi RH
Bottom surface area: A = \pi R^2

Problem translated to English by Alex.


Comments

There are no comments at the moment.