P7494 Three-Dispatch Rescue

>Just like the first domino, that person’s appearance started the story that followed. Muro raises many pigs at home. Under his training, these pigs are very well-behaved. Of course, sometimes these pigs can also become quite naughty…

One morning, Muro found that a piece of cake he had secretly kept was eaten! He immediately guessed that one of the pigs had eaten the cake, so he rushed to the pigsty to find that pig and punish it. There are $n$ pigs in the pigsty, numbered with integers from $1$ to $n$. Except for the pig that ate the cake, all other pigs **have the same weight**, and the pig that ate the cake is **slightly heavier** than the others (you may assume the pigs were originally $5\text{kg}$, and the one that ate the cake is $5.1\text{kg}$). Muro cannot tell by sight which pig ate the cake. Fortunately, Muro has a balance scale. He can drive pigs onto the two sides of the scale to compare which side is heavier. However, this scale is not very large: each side can hold at most $m$ pigs, otherwise the scale will be damaged and become unusable (the pig that ate the cake **will not reduce the number of pigs that can be placed on one side**, i.e., **whether or not a pig ate the cake, each side can still hold at most $m$ pigs**). Muro does not want to spend too much time, so he wants to know, under the condition that **the scale is not damaged**, **at least how many weighings are needed to guarantee finding the pig that ate the cake**. Please compute this number.

One line with two positive integers $n,m$.

One line with one positive integer, the answer.

#### Explanation for Sample 1: Muro first puts pig $1$ and pig $2$ onto the two sides of the scale respectively, then puts pig $3$ and pig $4$ onto the two sides respectively. In this way, he can definitely find the pig that ate the cake, and the number of weighings is $2$. Obviously, using the scale only once cannot guarantee finding the pig that ate the cake. #### Explanation for Sample 3: Each side of the scale can hold at most $2$ pigs, so at least $3$ weighings are needed to guarantee finding it. ------------ #### Constraints **This problem uses bundled testdata.** + Subtask 1 ( $10\%$ ): $n,m\leq10$. + Subtask 2 ( $25\%$ ): $n,m\leq10^6$. + Subtask 3 ( $15\%$ ): $n\leq m$. + Subtask 4 ( $50\%$ ): no special constraints. For all testdata, $1\leq n,m\leq10^{15}$. Translated by ChatGPT 5