// 100.cpp http://acm.uva.es/p/v1/100.html // // Solution to ACM problem #100 - "3n + 1" // // Matthew Eagar - meagar@gmail.com // Verified to work as of Feb 19 / 2005 #include #include typedef unsigned long ulong; int main() { ulong min, max; // our bounds as read from stdin std::vector cache(1000000, 0); while (std::cin >> min >> max) { ulong lbound, ubound; if (min < max) { lbound = min; ubound = max; } else { lbound = max; ubound = min; } ulong n, cycles, maxCycles = 0; // check each number in our given range (n1..n2) for (ulong i = lbound; i <= ubound; ++i) { n = i, cycles = 0; // loop until we hit 1 while (n != 1) { ++cycles; n = (n % 2 ? 3 * n + 1 : n / 2); if (n < cache.size() && cache[n]) { cycles += cache[n]; break; } } cache[i] = cycles; if (cycles >= maxCycles) maxCycles = cycles; } // write results, using origional version of lbound and ubound // I haven't taken the time to figure out why I have an off-by-one error... std::cout << min << " " << max << " " << maxCycles + 1 << std::endl; } }