P1731 [NOI1999] Birthday Cake

[Enhanced testdata link](https://www.luogu.com.cn/problem/T148457)

July 17 is Mr. W’s birthday. To celebrate, ACM-THU plans to make an $M$-layer birthday cake with volume $N\pi$, where each layer is a cylinder. Let the $i$-th layer from bottom to top ($1 \leq i \leq M$) be a cylinder with radius $R_i$ and height $H_i$. For $i \lt M$, it is required that $R_i \gt R_{i+1}$ and $H_i \gt H_{i+1}$. Since the cake needs to be frosted, to save cost as much as possible, we want the area $Q$ of the cake’s outer surface (excluding the bottom face of the lowest layer) to be minimized. Given $N$ and $M$, write a program to find a construction of the cake (appropriate values of $R_i$ and $H_i$) that minimizes $S=\dfrac{Q}{\pi}$. (Except for $Q$, all the quantities above are positive integers.)

The first line contains an integer $N$ ($N \leq 2 \times 10^4$), indicating that the cake’s volume is $N\pi$. The second line contains $M$ ($M \leq 15$), the number of layers of the cake.

Output an integer $S$. If there is no solution, output $0$.

Translated by ChatGPT 5