#10987. The 3n + 1

The 3n + 1

The 3n + 1 problem

题目背景

本题可能有超过题目范围的数据。

题面翻译

考虑下面的程序:

  1. 输入 nn
  2. 输出 nn
  3. 如果 n=1n=1 退出程序
  4. 如果 nn 是奇数,n3n+1n \rightarrow 3 n + 1
  5. 如果 nn 是偶数 nn2n\rightarrow \dfrac n 2
  6. 回到第 22

若输入 2222,会得出下面的数列: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

我们推测,对于任何输入的正整数 nn,程序最终都会输出 11n106n\le 10^6 时,保证推论正确)。 给定 nn,可以计算这个程序输出的所有数字的数量(包括最后的 11)。我们把输出的数字总数称为这个 nn 的周期长度。对于上面的例子,周期长度为 1616

对于输入的每对 (i,j)(i,j),计算 [i,j][i,j] 内所有数字区间长度的最大值。

输入格式

输入几对整数 (i,j)(i,j),保证 0<i,j1040<i,j\le 10^4。对于每对 (i,j)(i,j),你需要计算 [i,j][i,j] 内最大区间长度。数据保证 3232 位整数在计算过程中不溢出。

输出格式

对于每对 (i,j)(i,j),先输出 i,ji,j,再输出 [i,j][i,j] 范围内最大周期长度,每个数字中间一个空格,然后换行。

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

1 10
100 200
201 210
900 1000

样例输出 #1

1 10 20
100 200 125
201 210 89
900 1000 174