# UVa 100

## Contents

## 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)