yipo
12/12/2017 - 3:36 PM

uva100

The 3n + 1 problem

#include <array>
#include <iostream>
using namespace std;

inline size_t next(size_t n)
{
    return (n % 2) ? (3 * n + 1) : (n / 2);
}

size_t cycle_length(size_t n)
{
    static array<size_t, 10000> cache = { 0, 1 };

    size_t len = 0;
    while (n >= cache.size())
    {
        n = next(n);
        len++;
    }

    if (cache[n] == 0)
    {
        cache[n] = 1 + cycle_length(next(n));
    }
    return len + cache[n];
}

size_t test_case(size_t first, size_t last)
{
    if (first > last) swap(first, last);

    size_t max = 0;
    for (size_t i = first; i <= last; i++)
    {
        size_t len = cycle_length(i);
        if (len > max) max = len;
    }
    return max;
}

int main()
{
    size_t a, b;
    while (cin >> a >> b)
    {
        cout << a << " " << b << " " << test_case(a, b) << endl;
    }
    return 0;
}