e-olymp
Məsələlər

3n+1 məsələsi

3n+1 məsələsi

Ədədi ardıvıllıq yaratmaq üçün aşağıdakı alqoritmə nəzər salaq:

1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n = 3 * n + 1
5. else n = n / 2
6. GOTO 2

Məsələn, n=22üçün aşağıdakı ardıcıllıq alınacaqdır:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1.

Belə hesab edirlər ki, bu alqoritm istənilən n tam ədədi üçün sonda n=1verir. Bu ehtimal hələlik isbat olunmasa da 0<n<1000000 üçün doğruluğu yoxlanmışdır.

n ədədi üçün alınan ardıcilliğin ədədləri sayını (1 də daxil olmaqla) onun dövr uzunluğu adlandıraq. Yuxarıdakı misalda 22-nin dövr uzunluğu 16-ya bərabərdir.

Verilmiş i j ədədləri də daxil olmaqla, onlar arasında yerləşən ədədlər üçün maksimal dövr uzunluğunu tapmaq tələb olunur.

Giriş verilənləri

Hər test ayrıca sətirdə iki i j tam ədədi ilə verilir. Verilən ədədlər 1000000-dən kiçik və 0-dan böyük olmalıdır. Hesablama zamanı 32 bitlik tam ədəd tipindən istifadə etmək kifayətdir.

Çıxış verilənləri

Hər i j cütünü daxil olduğu ardıcıllıqla çıxarın. Beləliklə hər test üçün ayrıca sətirdə boşluq işarəsi ilə ayrılmaqla, üç ədəd daxil edilmiş i ,j ədədləri və özləri də daxil olmaqla onlar arasındakı ədədlər üçün tapılmış maksimal dövr uzunluğunu verin.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
1 10
100 200
201 210
900 1000
Çıxış verilənləri #1
1 10 20
100 200 125
201 210 89
900 1000 174