A. Eng go’zal bo’luvchi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Megamix sonlarni taqqoslashni judayam yoqtiradi, shuning uchun u sonlarni go’zallik darajasi bo’yicha taqqoslashni o’ylab topdi. Uning fikricha ikkita sondan eng go’zali ularning raqamlari yig’indisi kattasidir, agarda raqamlar yig’indisi teng bo’ladigan bo’lsa ularning qiymat jihatdan kichigi boshqasiga nisbatan go’zalroqdir.

Kiruvchi ma'lumotlar:

Bitta natural N(1 ≤ N ≤ 10¹²) soni beriladi.

Chiquvchi ma'lumotlar:

N sonining eng go’zal bo’luvchisini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	12	6

B. Yo’llar soni

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Xaritada shaharlarning bog’lashini keltirilgan, unga ko’ra 0 – shahardan 1-shaharga bo’lgan yo’llar soni a₀ ta, 1 – shahardan 2 – shaharga bo’lgan yo’llar soni a₁ ta, va hokazo, shunday tartibda faqatgi yonma-yon shaharlar orasida yo’llar bor.

Megamix 0 – shahardan oxirgi shaharga borishning necha xil usuli mavjudligini bilmoqchi, unga yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 1000) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun alohida ikki qatorning birinchi satrida N (2 < N ≤ 100) shaharlar soni, ikkinchi satrda N-1 ta butun son, a_i(0 < a_i ≤ 1000) shaharlar orasidagi yo’llar soni kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda Megamix bilmoqchi bo’lgan sonni chop eting, bu son juda katta bo’lishi mumkin, shuning uchun siz natijaviy sonning 1234567 ga bo’lgandagi qoldig’ini chop eting.

Misollar:

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

C. Permutatsiyalar soni

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Megamixda N ta 0 va M ta 1 raqami bor. U o’zidagi raqamlardan foydalanib hosil qilish mumkin bo’lgan barcha N+M xonali sonlarni yozib chiqdi, shu permutatsiyalar ichida nechtasi 1 bilan boshlanishini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 200) testlar soni kiritiladi. Keyingi satrdan boshlab har bir test uchun alohida qatorda bo’sh joy bilan ajratilgan holda N va M(1 ≤ N, M ≤ 1000) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish fayliga har bir test uchun alohida satrda bitta butun son, Megamix hosil qilgan permutatsiyalar ichida 1 bilan boshlanadiganlari sonini 10⁹+7 ga bo’lgandagi qoldig’ini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 1 1 2 3	1 6

D. Bo’linuvchi juftliklar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Singa N va K sonlari beriladi, 1 ≤ i < j ≤ N va (i+j) mod K = 0 shart qanoatlanadigan juftliklar sonini aniqlang

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 100) soni kiritiladi, keyingi T ta qatorda ikkitadan butun son, N va K(1 ≤ K ≤ N ≤ 10⁹)

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda bittadan butun son, masala javobini chop eting.

Misollar:

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

E. Massiv elementlarini tenglash

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga N ta elementdan iborat A massiv berilgan, siz massiv ustida bir amalda quyidagilardan birini bajarishingiz mumkin:

- massivni ixtiyoriy bir elementidan tashqari barcha elementini qiymatini 1 ga oshirish;

- massivni ixtiyoriy bir elementidan tashqari barcha elementini qiymatini 2 ga oshirish;

- massivni ixtiyoriy bir elementidan tashqari barcha elementini qiymatini 5 ga oshirish.

Sizga berilgan massivning barcha elementini tenglash uchun siz eng kamida nechta amal bajarishingiz kerakligini aniqlang.

Masalan sizga [1,1,5] elementlardan iborat massiv berilgan bo’lsa: [1,1,5]→[3,3,5]→[5,5,5] ikkita amalda siz qo’yilgan maqsadga erishasiz.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 100) testlar soni kiritiladi. Keyingi qatordan boshlab har bir test uchun alohida ikkita qatorning birinchisida bitta butun son, N(1 ≤ N ≤ 10000) massiv elementlar soni, ikkinchi qatorda esa N ta butun son A(0 ≤ A_i ≤ 1000)

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda masala javobini chop eting.

Misollar:

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