UVa 846

From Algorithmist
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