Inchworm
SRM 163 · 2003-09-08 · by Eeyore
Problem Statement
The inchworm is a creature of regular habits. She inches forward some distance along the branch of a tree, then stops to rest. If she has stopped at a leaf, she makes a meal of it. Then she inches forward the same distance as before, and repeats this routine until she has reached or passed the end of the branch.
Consider an inchworm traveling the length of a branch whose leaves are spaced at uniform intervals. Depending on the distance between her resting points, the inchworm may or may not be able to eat all of the leaves. There is always a leaf at the beginning of the branch, which is where the inchworm rests before setting out on her journey.
You are given three
Notes
- The inchworm starts by gobbling up the leaf at the beginning of the branch.
- If there is a leaf at the end of the branch, the inchworm eats it only if it falls at a resting point.
Constraints
- branch is between 1 and 1000000 (one million), inclusive
- rest is between 1 and 1000, inclusive
- leaf is between 1 and 1000, inclusive
11 2 4 Returns: 3
Leaves grow 0, 4, and 8 inches from the beginning of the branch. The inchworm eats them all.
12 6 4 Returns: 2
The inchworm misses the leaves growing at distances 4 and 8, but eats those at 0 and 12.
20 3 7 Returns: 1
The inchworm eats only the leaf at the outset.
21 7 3 Returns: 2
The inchworm eats the leaves at the beginning and end of the branch.
15 16 5 Returns: 1
The inchworm eats only the leaf at the outset.
Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Inchworm with a public method int lunchtime(int branch, int rest, int leaf) · 105 test cases · 2 s / 256 MB per case