power starts at 0. Standing on step i, in one move it can:
- step down to i - 1. This is not allowed from step 0, and two step-downs in a row are not allowed either;
- jump up to step i + 2^power, after which power grows by 1.
A route is any sequence of moves, the empty one included. Count the routes after which the grasshopper stands on step target. A route may pass through target earlier: if the grasshopper lands on target, leaves and comes back, that is one more route.target=2 → 4
Four routes work: jump 1 → 2; step down 1 → 0, jump 0 → 1, jump 1 → 3, step down 3 → 2; jump 1 → 2, step down 2 → 1, jump 1 → 3, step down 3 → 2; step down 1 → 0, jump 0 → 1, step down 1 → 0, jump 0 → 2.
target=0 → 2
Either step down 1 → 0 right away, or step down, jump 1 back to step 1 and step down again. After that the jumps are too long to ever come back.
target=7 → 4
Step 7 = 1 + 1 + 2 + 4 − 1: three jumps and exactly one step down, which can go into any of the four gaps around the jumps.
target ≤ 10⁹target=2
4
Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.