UVa 100

From Algorithmist
Jump to navigation Jump to search

100 - The 3n + 1 problem[edit]

Summary[edit]

Follow the instructions for all the numbers in the given range and keep record of the largest cycle, there is nothing more to it than that. Bruteforce will do.

Explanation[edit]

A "follow the instructions" problem.

Even with no optimizations, one can pass the judge's tests with more than enough time. The relatively low acceptance rate comes from the fact that it's usually the first problem people attempt - people who are unfamiliar with the system. The Gotcha is a good one - it teaches you never to make assumptions about programming contest problems.

Optimizations[edit]

To get the problem in good time you must create an array with size 1000000. Then using recursion with memoization try to not compute any value more than once. This will help you solve it in about 0.200 sec.

Gotchas[edit]

  • j can be smaller than i.
  • j can equal i.
  • The order of i and j in output must be the same as the input, even when j is smaller than i.

Input[edit]

1 10
100 200
201 210
900 1000
1000 900
999999 999990

Output[edit]

1 10 20
100 200 125
201 210 89
900 1000 174
1000 900 174
999999 999990 259

Solutions[edit]

Java: http://acm-solution.blogspot.com/2010/11/acm-uva-100-3n-1-problem-java.html

C++: http://acm-solution.blogspot.com/2010/08/acm-uva-100-3n-1-problem.html

C++: http://www.lukejduncan.com/2009/08/uva---100---3n1-problem.php.

Java: http://adilakhter.wordpress.com/2013/02/21/1729

F#: http://adilakhter.wordpress.com/2013/02/20/collatz-problem-a-k-a-3n1-problem/ (SPOJ 4073)

See Also[edit]