P4820 [CTT] Book Stack

Ants are hardworking animals, and they like to challenge limits. Now they have run into a difficult problem. The ants live in a library with a large number of books. Each book is a rectangle with the same shape, size, and mass. The ants want to place these books at the edge of a horizontal table. The ants like a neat arrangement, so they require that the books must be placed horizontally, with their width parallel to the table edge (as shown in the figure), and it is not allowed to place more than one book at the same height.  The ants want the books to extend out of the table edge as far as possible, while not letting the stack collapse due to gravity. They have already measured the book length $M$ (as shown in the figure) using some unknown method. If there are a total of $N$ books, please help compute how to place them so that the maximum horizontal overhang beyond the table edge is as large as possible. You do not need to consider how the ants build this stack of books. If the vertical projection of the center of mass of all books above a certain book is not on that book, or falls exactly on the boundary of that book, then the stack is unstable and will collapse due to gravity. Consider the following assumptions: - Ignore the Earth's rotation, and the gravitational coefficient does not change with height. - The books are ideal 2D objects with uniform mass and rigid material. - Under the condition that the stack does not collapse, each book's position coordinates can be any real number. ## Constraints - $N \le 10^{18}$, and the testdata guarantees that the answer is $< 10^{6}$.

The first line contains positive integers $N$ and $M$.

Output an integer $L$, representing the farthest integer distance of horizontal extension (the greatest integer not exceeding the answer).

$N \le 10^{18}$, and the testdata guarantees that the answer is $< 10^{6}$. Translated by ChatGPT 5