UVa 100
From Algorithmist
Contents |
[edit] 100 - The 3n + 1 problem
[edit] Summary
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.
[edit] Explanation
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.
[edit] Optimizations
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.
[edit] Gotchas
- 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.
[edit] Input
1 10 100 200 201 210 900 1000 1000 900
[edit] Output
1 10 20 100 200 125 201 210 89 900 1000 174 1000 900 174
[edit] Solutions
C++: http://www.lukejduncan.com/2009/08/uva---100---3n1-problem.php
C++: http://acm-solution.blogspot.com/2010/08/acm-uva-100-3n-1-problem.html
