A. N&i = i ?

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga n soni beriladi

\(S = \sum_{i = 1}^{n}1\ \ if\ n\ \&\ i\ ==\ i\ else\ 0\)

ni hisoblashingiz kerak.

Kiruvchi ma'lumotlar:

Yagona qatorda N soni kiritiladi.

\(N <= 10^{18}\)

Chiquvchi ma'lumotlar:

Masalada so'ralgan javobni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	8	1

B. Eng kichik katta

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga bo'sh bo'lmagan s satr beriladi. Siz leksikografik jihatdan bu satrdan katta bo'lgan eng kichik satrni topishingiz kerak.

!!! Siz faqat kichik lotin harflaridan foydalana olasiz.

Kiruvchi ma'lumotlar:

Yagona qatorda kichik lotin harflaridan iborat s satr kiritiladi. \((|s| \le 10^5)\)

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	z	za

C. K lar yig'indisi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bizda F funksiya mavjud va F(n,k) quyidagicha hisoblanadi:

Agar \(C_n^k\%2 == 1\) bo'lsa \(K\) ni qaytaradi.
Aks holda \(0\) ni qaytaradi.
Masalada biz S ni hisoblashimiz kerak va \(S = \sum_{k = 1}^{n} F(n,k)\)

Kiruvchi ma'lumotlar:

Yagona qator n soni kiritiladi.

\(n \le 10^{10}\)

Chiquvchi ma'lumotlar:

Masala javobini chiqaring

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	8	8
2	5	10

D. Teleportatsiya

Xotira: 64 MB, Vaqt: 2000 ms

Masala

Nyuboy xayolida “Teleport” nomli o'yinni o'ynayapti. O'yin n ta bosqichdan iborat. Nyuboyning vazifasi n-bosqichga yetib borish. Nyuboyning o'yindagi teleportatsiya kuchi k ga teng, ya'ni u hozir i-bosqichda bo'lsa bitta harakatda keyingi k ta bosqichdan biriga teleportatsiya qila oladi. Nyuboyning n-bosqichga yetib borish variantlar sonini chop eting.

Nyuboy o'yinni 1-bosqichda boshlaydi.

Kiruvchi ma'lumotlar:

Yagona qatorda n va k natural sonlari mos ravishda o'yindagi bosqichlar soni va Nyuboyning xayoliy teleportatsiya kuchi kiritiladi.

\((n \le 10^{15}, k \le min(n, 100))\)

Chiquvchi ma'lumotlar:

Nyuboyning n-bosqichga yetib borish variantlar sonini \(10^9 + 7\) ga bo'lgandagi qoldig'ini chiqaring.

Izoh:

1-namunaviy testda

1 → 2 → 3 → 4

1 → 2 → 4

1 → 3 → 4

Xuddi shunday 3 xil usulda yetib kelishi mumkin.

!!! Agar siz pythonda ishlasangiz yechimingizni pypy da jo'nating.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 2	3

E. Eng katta subset

Xotira: 512 MB, Vaqt: 2000 ms

Masala

Sizga N,Q va N uzunlikdagi raqamlardan iborat S satr beriladi va Q ta so'rov beriladi, siz barcha so'rovlarga javob berishingiz kerak. So'rov quyidagicha:

\(l,r,k\) sonlari kiritiladi, \(S\) satrning \([l,r]\) oralig'idan uzunligi \(k\) dan katta bo'lmagan subsetlar ichidan eng kattasini topishingiz kerak.

!!!Agar siz python dasturlash tilida ishlasangiz PyPy compilatoridan foydalaning

Kiruvchi ma'lumotlar:

1-qatorda mos ravishda \(N\) va \(Q\) sonlari,2-qatorda esa \(S\) satr kiritiladi. Keyingi \(Q\) ta qatorda \(l,r,k\) sonlari kiritiladi.

\(N,Q <= 10^6\)

So'rovlardagi barcha \(k\) larning yig'indisi \(2*10^6\) dan oshmaydi

Chiquvchi ma'lumotlar:

\(Q\) qatorda mos ravishda so'rovlarga javoblarni chop eting.

Agar [l,r] oralig'idagi barcha raqamlar no'l(0) ga teng bo'lsa u holda chiqishda 1 ta no'l(0) ni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 5 7113319716 10 10 1 9 9 3 7 8 7 6 7 7 5 7 5	6 1 97 19 319
2	6 9 187195 6 6 5 3 4 1 6 6 6 2 3 2 2 3 3 4 4 6 1 5 5 2 5 1 3 3 6	5 7 5 87 87 1 18719 9 7