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.

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 $A-B$ $A - B$ meters. His entire trip consists of $X$ $X$ days and $X$ $X$ nights, plus the last day in which he reaches the top of the pole. Therefore, our solution is the smallest integer $X$ $X$ for which $X \times (A-B) + A \ge V$ $X \times (A - B) + A \geq V$ holds.

Solution

It's now easy to find a direct expression for $X$ $X$ :

$\displaystyle \begin{align*} X \times (A-B) + A &\ge V \\ X \times (A-B) &\ge V-A \\ X &= \left\lceil \frac{V-A}{A-B} \right\rceil \\ X &= \left\lfloor \frac{V-A+A-B-1}{A-B} \right\rfloor \\ X &= \left\lfloor \frac{V-B-1}{A-B} \right\rfloor \end{align*}$ $\begin{aligned} X \times (A - B) + A & \geq V \\ X \times (A - B) & \geq V - A \\ X & = ⌈ \frac{V - A}{A - B} ⌉ \\ X & = ⌊ \frac{V - A + A - B - 1}{A - B} ⌋ \\ X & = ⌊ \frac{V - B - 1}{A - B} ⌋ \end{aligned}$

We use integer division, and print $X+1$ $X + 1$ as a result.

Alternative solution

We can use binary search to solve the problem. We start with some potential solution $X'$ $X^{'}$ , and check if the inequality holds. If the inequality doesn't hold, we must use a smaller $X'$ $X^{'}$ . If it holds, we can increase $X'$ $X^{'}$ and try again. This gives us an $\mathcal O(\log V)$ $O (\log V)$ solution.

Comments

There are no comments at the moment.