Розв’язок

За одну передачу гроші можуть просунутися щонайбільше на $k$ місць у напрямку водія: між тим, хто передає, і тим, хто отримує, тоді стоять $k-1$ людей.

Нехай гроші побували в $p$ пасажирів. Разом із передачею водієві це p+1 передач, якими потрібно подолати відстань n+1 місць. Тому має виконуватися нерівність (p+1)k \ge n+1.

Відповідь можна обчислити цілочисельним діленням: (n+k)/k-1. Це те саме, що $n/k$, також із цілочисельним діленням.

Справді, нехай n=qk+r, де 0 \le r < k. Можна передати гроші через $q$ пасажирів: перші $q$ передач просунуть гроші на $k$ місць кожна, а остання передача водієві — на r+1 \le k місць. Меншої кількості пасажирів недостатньо, бо $q$ передач можуть подолати не більше ніж qk \le n місць.

Складність

Часова складність — $O(1)$, додаткова пам’ять — $O(1)$.