A 3n + 1 probléma

A számítástechnikai problémákat gyakran sorolják bizonyos problémaosztályokba (például NP, megoldhatatlan, rekurzív). A feladatod megvizsgálni egy olyan algoritmus tulajdonságát, melynek nem minden bemenet esetén ismert a besorolása.

Tekintsük a következő algoritmust:

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

A 22-es bemenetre a következő számsorozatot kapjuk: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Arra következtethetünk, hogy az algoritmus véget ér (ha az 1-es kiíródott) bármely egész bemeneti adatra. Az algoritmus egyszerűségének ellenére nem ismert, hogy ez a következtetés igaz-e. Ellenőrizték viszont minden 0 és 1 000 000 közötti egész számra (sőt, valójában sokkal többre).

Egy adott n bemenet esetén meg lehet határozni a kiírandó számok számát (beleértve az 1-est is). Egy adott n-re ezt az n szám ciklushosszának nevezzük. A fenti példában a 22 ciklushossza 16.

Minden i és j számra határozd meg a közöttük lévő számok ciklushosszainak a maximumát.

A bemenet specifikációja

A bemenet egysoros tesztesetekből áll, melyek két egész számot tartalmaznak, i-t és j-t. Minden egész szám kisebb lesz 1 000 000-nál, és nagyobb 0-nál.

Fel kell dolgoznod minden számpárt, és meg kell határoznod a maximális ciklushosszt i és j között, beleértve i-t és j-t is.

Feltételezheted, hogy egyik művelet sem csordul túl 32 biten.

A kimenet specifikációja

Minden bemeneti számpárra ki kell írnod i-t és j-t, valamint a maximális ciklushosszt. Mind a három szám egy sorban legyen, pontosan egy szóközzel elválasztva. Az i és j számoknak abban a sorrendben kell a kimeneten megjelenniük, amilyen sorrendben a bemeneten szerepeltek, és őket követi a maximális ciklushossz (ugyanabban a sorban).

Példa bemenet

1. 1 10
2. 100 200
3. 201 210
4. 900 1000

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 1 10 20
2. 100 200 125
3. 201 210 89
4. 900 1000 174

letöltés szöveges állományként