# UVa 846

Jump to navigation
Jump to search

## 846 - Steps[edit]

## Summary[edit]

An ad hoc math quiz.

## Explanation[edit]

First, the start and end numbers do not really matter. So we can assume the start number is always 0. Given the number of steps, it is not hard to find out the maximum number we can reach using the steps. The results for the first few steps are shown below.

steps max_reachable_number increase 0 0 (0) 1 1 (1) +1 2 2 (11) +1 3 4 (121) +2 4 6 (1221) +2 5 9 (12321) +3 6 12 (123321) +3 7 16 (1234321) +4 8 20 (12344321) +4

Thus the function from the number of steps to the maximum reachable number is for even steps, and for odd steps. The numbers from to can be reached by using steps, but not by using less than steps (proof ignored). The solution to this problem is really about writing the inverse function of . An algorithm can be obtained.

If we write the inverse function of , it is for both cases.

## Gotchas[edit]

- Probably need to take special care of the trivial case in which the start and end numbers are the same.

## Input[edit]

4 45 45 45 48 45 49 45 50

## Output[edit]

0 3 3 4