Category

Similar Problems

0596. Kollatz gipotezasi

Time limit : 1500 ms
Memory limit : 64 mb


Matematikaning hal qilinmagan muammolaridan biri bo’lgan Kollatz gipotezasi yoki Sirakuza muammosi matematikada eng g’ayri tabiiy hodisalardan biri hisoblanadi. Buni nimaligini tushuntirish uchun ushbu rekursiv funksiyani keltirib o’tamiz.

Gap shundaki qanday son bo’lmasin, u qachondir baribir 1 ga keladi. Keyinchalik esa 1 - 2 - 4 - 1 - 2 – 4 cheksiz rekursiya davom etadi. Masalan 5. Dastlab 5 soni toq bo’lgani uchun 16 ga o’zgaradi, 16 juft bo’lgani uchun 8 – 4 – 2 – 1…. Sizga q ta so’rovlar soni beriladi. Sizdan har bir so’rovda n soni qancha amaldan keyin 1 ga kelib qolishi so’raladi. Javob tarikasinda hamma so’rovlarga javoblarni yigindisi chiqarilsin.

Kiruvchi ma’lumotlar: Birinchi qatorda 1 ta butun son q(1 ? q ? 105). Keyingi q qatorda bittadan son (1 ? n ? 107). Gap shundaki son 1 ga kelguncha ancha kattalishib ketishi mumkin. Shuning uchun testlardaki sonlar shunday tanlanganki, ular rekursiv funksiyani hisoblash vaqti 108 dan katta bo’lib ketmasligi kafolatlanadi.

Chiquvchi ma’lumotlar: Yagona qatorda masala yechimi chiqaring.

Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

3

5

3

16

16

Input
3

5

3

16
Output
16