// 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;
}
}