Hunting Dog
Autumn Tournament (2010)
Submission name: dog.cpp
Problem summary
A dog starts N steps behind a hare. In each round the hare jumps M steps and the dog jumps K steps. Find the minimum number of dog jumps needed to reach or pass the hare.
Input
Three positive integers N, M and K.
Output
The required number of jumps.
Constraints
M < K < N; 20 < N < 1000; 1 < M, K < 20.
Worked example
Original statement sample, translated without changing its numeric data.
Input
150 7 9
Output
75
Solution analysis
- Each pair of jumps reduces the distance by K − M steps. This quantity is positive because the dog jumps farther.
- After j jumps the dog has closed j(K − M) steps. Find the smallest integer j for which this is at least N by rounding the division N/(K − M) upward.
- For N = 150, M = 7 and K = 9, each round closes 2 steps. Exactly 75 rounds close all 150 steps.
Why it works
After j rounds the remaining gap is N − j(K − M). The dog has caught the hare exactly when this is nonpositive. The smallest integer satisfying that inequality is the ceiling of N/(K − M), which the program computes.
Watch out. Ordinary integer division rounds down. Include one more jump when there is a remainder.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
int gap,hareJump,dogJump;
cin>>gap>>hareJump>>dogJump;
int gain=dogJump-hareJump;
// Add gain - 1 before division to round upward.
cout<<(gap+gain-1)/gain<<'\n';
}