UVa 371

From Algorithmist
Jump to: navigation, search

371 - Ackermann Functions[edit]

Summary[edit]

An Ackermann function is a function where you cannot determine the length of recursion based on the input value. In this problem, perform the instructions for one ackermann function : If X is even, divide by two, and if odd, Muliply by 3 and add 1.

Follow the instructions for all the numbers in each given range of two numbers, keeping record of the largest cycle. Print out the largest cycle size and the initial number.

Explanation[edit]

A "follow the instructions" problem. Bruteforce will work.

Optimizations[edit]

  • There's no harm in memoizing solutions for individual numbers.

Gotchas[edit]

  • As with UVa 100, the first number may be greater than the second.
  • However, the output states that the lower and upper bounds must be printed in a certain order.

Input[edit]

   1 20
  35 55
2000 3000
3000 2000
   0 0

Output[edit]

Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 35 and 55, 54 generates the longest sequence of 112 values.
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.

Solutions[edit]

See Also[edit]