A. Zinapoya

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Aziz balandligi N ta zinapoyadan iborat bo’lgan zinapoya oldida turibdi, u zinapoyaning yuqori qismiga chiqmoqchi. Aziz bir yurishda 1 ta yoki 2 ta zinapoya yuqorilay oladi. Aziz zinapoyaning yuqori qismiga chiqish variantlar sonini aniqlang (tartib ahamiyatga ega emas).

Eslatma: Tartib ahamiyatga ega emas degani, masalan, n=4 holat uchun {1, 2, 1}, {2, 1, 1}, {1, 1, 2} lar bir xil variantda chiqish hisoblanadi.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida yagona son, N(1 ≤ N ≤ 10¹⁸) soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida yagona son, zinapoya yuqorisiga chiqish variantlar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4	3
2	5	3

B. Integer

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Berilgan 32 bitli ishorali N butun sonning kompyuter xotirasida qanday ifodalanishini aniqlang

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida yagona butun son, $N (-2^{31} ≤ N <2^{31})$ soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida N sonining kompyuter xotirasida qanday ifodalanishini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	0	00000000000000000000000000000000
2	10	00000000000000000000000000001010
3	-5	11111111111111111111111111111011

C. K-kichik son

Xotira: 16 MB, Vaqt: 1000 ms

Masala

N ta elementdan iborat to’plamdagi K-kichik sonni toping.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, $N (1 ≤ N ≤ 10^5)$ soni kiritiladi. Keyingi satrda $N$ ta $[-10^9, 10^9]$ oralig’idagi butun sonlar bo’sh joy bilan ajratilgan holda kiritiladi. Oxirgi satrda esa bitta butun son, $K (1 ≤ K ≤ N)$ soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 5 9 1	5
2	3 5 2 7 2	5
3	8 10 11 13 8 1 9 4 12 4	9

D. Daraxt

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Berilgan daraxtning barcha tugunlari balandliklari yig’indisini toping!

Eslatma: Daraxt ildizining balandligi 1 ga teng hisoblanadi.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, $N (1 ≤ N ≤ 10^5)$ daraxt tugunlari soni kiritiladi.

Ikkinchi satrda $N$ ta son, $i$ - son $i$ - tugun qaysi tugundan kelib chiqganligini ifodalaydi, daraxt ildizi -1 bilan ifodalanadi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida barcha tugunlar balandliklari yig’indisini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 -1	1
2	8 6 6 8 -1 4 5 8 5	25
3	6 3 3 6 1 6 -1	15

E. Fibonacci EKUB

Xotira: 16 MB, Vaqt: 1000 ms

Masala

$F_0 = 0, \space F_1 = 1,\space \dots ,\space F_k = F_{k-1} + F_{k-2} \space (k> 1)$ sonlar ketma-ketligi Fibonacci ketma-ketligi deyiladi.

Fibonaccining ikkita hadi eng katta umumiy bo’luvchisini toping.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining yagona satrida ikkita butun son, $i$ va $j (1 ≤ i, j ≤ 10^{18})$ kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son $F_i$ va $F_j$ ning EKUBini $10^9+7$ ga bo’lgandagi qoldiqni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 5	5
2	7 3	1
3	2 2	1