Editorial for COCI '10 Contest 2 #1 Puž
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Calculating the snail's position day by day would be too slow, since the expected result can be very large.
During one day and one night, the snail climbs exactly meters. His entire trip consists of days and nights, plus the last day in which he reaches the top of the pole. Therefore, our solution is the smallest integer for which holds.
Solution
It's now easy to find a direct expression for :
We use integer division, and print as a result.
Alternative solution
We can use binary search to solve the problem. We start with some potential solution , and check if the inequality holds. If the inequality doesn't hold, we must use a smaller . If it holds, we can increase and try again. This gives us an solution.
Comments