A. Qora katakcha

Xotira: 32 MB, Vaqt: 1000 ms

Masala

NxM shakldagi shaxmat doskasi oq va qora kataklardan iborat. Chap pastki burchagi qora rangda bo'lsa, ushbu shaxmat katakchasida nechta qora katak mavjud.

Kiruvchi ma'lumotlar:

N va M natural son beriladi. \((1≤N,M≤10^3)\)

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 4	8

B. G'alati poyezd

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Javlonbek poyezdda sayohatga chiqdi. Vagonda kupelar soni rasmda ko’rsatilgani kabi bo'lib K ta vagondan iborat. N-vagonda qaysi kupelar joylashganini aniqlashga harakat qilib eplolmadi. Siz unga yordam bering.
(Namunada 11 ta vagonli poyezd keltirilgan)

Kiruvchi ma'lumotlar:

Birinchi qatorda vagonlar soni natural K soni beriladi. \((1≤N≤K≤10^{9})\)

Ikkinchi qatorda natural N soni beriladi. \((1≤N≤K)\)

Chiquvchi ma'lumotlar:

Chiqishda kupelar raqamini tartib bilan chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	11 11	41 42 43 44 45 46

C. Qisqa to'ldirish

Xotira: 512 MB, Vaqt: 1500 ms

Masala

Sizga 1xN o‘lchamdagi setka berilgan. Boshlang‘ich holatda barcha kataklar oq rangda. Har soniyada quyidagilar sodir bo‘ladi:

Har bir qora rangdagi katakka qo‘shni bo‘lgan kataklar qora rangga bo‘yaladi. Har bir qora rangdagi \(x\)-katak uchun \(x+1\)-inchi va \(x-1\)-inchi kataklar ham (agar mavjud bo‘lsa) qora rangga bo‘yaladi.
Xohlagan bir katakni qora rangga bo‘yashingiz mumkin.

Savol:

Barcha kataklarni qora rangga bo‘yash uchun eng kamida qancha vaqt kerak bo‘ladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda T soni \((1\le T \le 100)\) - Testlar soni.

Keyingi T qatorda N soni \((1 \le N \le 10^9)\).

Chiquvchi ma'lumotlar:

To'ldirish uchun eng kam vaqt(sekund) ketishini chop eting.

Izoh:

1-testda mumkin bolgan ketma-ketlik (bu yerda yashil rang ohirgi qoraga boyalgan katak):

2-testda:

Misollar:

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

D. So'z yasash #2

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Javlonbek faqat N ta turli harflarini o'z ichiga olgan K ta harfli so'zlarni tuzadi va tanlangan qandaydir harf har bir so'zda to'liq M marta ishlatiladi. Boshqa harflarning har biri so'zda bir necha marta qatnashishi yoki umuman qatnashmasligi ham mumkin. So'z har qanday to'g'ri keladigan harflar ketma-ketligi bo'lib, ma'noli bo'lishi shart emas. Javlonbek yoza oladigan shunday nechta so'z borligini aniqlash dasturi tuzilsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤2*10^4)\)

Ikkinchi qatorda natural N, K va M sonlar beriladi. \((0≤M≤K≤N≤26)\)

Chiquvchi ma'lumotlar:

Masala javobini \(10^9+7\) ga bo'lgandgi qoldiqni chop eting.

Izoh:

1-testda. 3 2 1 da
3 ta turli hatflar masalan ABC dan 2 uzunlikda so'zlar yasash lozim. Shulardan qaysidir bitta harf faqat 1 marta uchraydigan so'zlar soni kerak. Qandaydir 1 ta harf deyilmoqda. Hohlasak A harfni, B harfni yoki C harfi olishimiz mumkin. Masalan A ni 1 marta uchrashini ko'rib chiqsak:
1) AB
2) AC
3) BA
4) CA
so'zlarni hosil qila olamiz demak 4 ta so'z hosil qilish mumkin.

Misollar:

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

E. Uzoq to'ldirish

Xotira: 512 MB, Vaqt: 1500 ms

Masala

Sizga 2xN o'lchamdagi setka berilgan. Boshlang'ich holatda barcha kataklar oq rangda bo'ladi. Har soniyada quyidagilar sodir bo'ladi:

Har bir qora rangdagi katakka qo'shni bo'lgan kataklar qora rangga bo'yaladi. Agar (x, y) katak qora rangda bo'lsa, unda (x+1, y), (x, y+1), (x-1, y), va (x, y-1) kataklar (agar mavjud bo'lsa) qora rangga bo'yaladi.
Siz xohlagan katakni boshlang'ich holatda qora rangga bo'yashingiz mumkin.

Savol:
Setkaning barcha kataklarini qora rangga bo'yash uchun eng kamida qancha vaqt kerak bo'ladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda T soni \((1\le T \le 100)\) - Testlar soni.

Keyingi T qatorda N soni \((1 \le N \le 10^{18})\).

Chiquvchi ma'lumotlar:

Eng kamida qancha sekund ketishini choping

Izoh:

Birinchi test uchun 2 sekund kerak. Masalan(bu yerda yashil rang oxirgi tanglangan katak):

Ikkinchi test:

Misollar:

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

F. Kvadrat massiv

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga \(n\) ta elementlarda tashkil topgan massiv berilgan bo'lib, sizning vazifangiz massivdan ko'pi bilan \(2 ta\) sonni olib tashlagan holda, qolgan sonlar yig'indisi birorta bir natural sonni kvadrati bo'lishi mumkin ekanligini tekshirishdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda natural son, \(n(1≤n≤10^5).\)

Ikkinchi qatorda probel orqali n ta son beriladi \(a_i(1≤a_i≤10^9).\)

Chiquvchi ma'lumotlar:

Yagona qatorda agar mumkin bo'lsa \(Yes\), aks holda \(No\) so'zini chiqaring.

Izoh:

.

Misollar:

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

G. Kutubxona jumbog'i

Xotira: 128 MB, Vaqt: 2000 ms

Masala

Yosh qahramon Botir, bilimga chanqoq tadqiqotchi, uzoq yillar davomida turli o‘lkalarda bilim izlab yurdi. Nihoyat, u qadimiy bilimlarni o‘zida mujassam etgan mashhur kutubxonaga yetib keldi. Bu kutubxona avlodlardan-avlodlarga o‘tib kelayotgan murakkab jumboqlarni o‘z ichiga olardi.

Kutubxonadagi eng qimmatli bilimlardan foydalanish uchun, Botir bir ma’lumotlar tuzilmasi haqida bilimga ega bo‘lishi kerak edi. Bu tuzilma prefiks daraxti (yoki trie) deb ataladi.

Prefiks daraxti bu so‘zlar to‘plamidagi barcha prefikslarni quyidagicha ifodalaydigan ma’lumotlar tuzilmasidir:

Daraxtning har bir qirrasida alifbodagi bir harf yozilgan bo‘ladi.
Daraxtning ildizi bo‘sh prefiksni ifodalaydi.
Daraxtning boshqa barcha tugunlari bo‘sh bo‘lmagan prefikslarni ifodalaydi. Tugunlar ildizdan ushbu tugungacha bo‘lgan qirralarda yozilgan harflarni birlashtirish orqali hosil qilingan prefikslarni ko‘rsatadi.
Har bir tugundan chiqadigan qirralar orasida bir xil harf bo‘lmaydi (bu esa minimal tugunlar soni bilan daraxtni ifodalash imkonini beradi).

Prefiks daraxtiga namuna

Botir prefiks daraxtining qanday ishlashini tushunib olgach, haqiqiy jumboq boshlanadi!

Kutubxonachi, kichik ingliz harflaridan iborat bo‘lgan N ta so‘z ro‘yxatini taqdim etdi. Agar u oddiygina ushbu so‘zlar uchun prefiks daraxtidagi tugunlar sonini bilmoqchi bo‘lganida, jumboq juda oddiy bo‘lardi. Lekin u bundan qoniqmaydi. Kutubxonachi so‘zlarning har birini istalgan tartibda qayta joylashtirish orqali hosil bo‘lgan prefiks daraxtining eng kam tugunlar sonini bilishni istaydi.

Botirga jumboqni hal qilishda yordam bering va ushbu savolga javob toping!

Kiruvchi ma'lumotlar:

Kirish faylining 1-satrida natural son \(N (1 \le N \le 16 \) kiritiladi.

Keyingi N satrning har birida 1 tadan so'z kiritiladi. So'z ingliz alifbosining kichik harflaridan tashkil topgan.

Barcha so'zlarning umumiy uzunligi \( 10^6 \) dan oshmaydi.

Chiquvchi ma'lumotlar:

Kutubxonachining jumbog'i javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 a ab abc	4
2	3 a ab c	4

H. Binar o'yin

Xotira: 512 MB, Vaqt: 1500 ms

Masala

Ikki do'st Shohruh va Temur zerikib, o'yin o'ynashga qaror qildi. Ular \(x\) soni bilan boshlaydi. O'z yurishida, o'yinchi ikkalasidan birini qilishi mumkin:

\(x:=\Bigl\lfloor \dfrac{x}{2} \Bigr\rfloor\)
\(x:=x-1\)

Agar yurish payti, \(x=0\) bo'lsa, yuradigan o'yinchi yutqazgan bo'lib hisoblanadi. Agar ikkala o'yinchi ham optimal o'ynasa, va Shohruh birinchi yursa, kim yutishini ayting.

Kiruvchi ma'lumotlar:

Birinchi qatorda testlar soni \((1 \le T \le 10^4)\)

T qatorda \(x\) soni \((1\le x \le 10^{12})\)

Chiquvchi ma'lumotlar:

Javobga T ta qatorga har bir \(x\) uchun kim g'olib bo'lishini choping.

Izoh:

\(x=1\) bo'lganda, Shohruh nima qilsa ham, yurishidan keyin \(x=0\) boladi, shuning uchun Shohruh yutadi.

\(x=2\) uchun, Shohruh nima qilsa ham, yurishidan keyin \(x=1\) boladi, va Temur yurishida \(x=0\) qiladi, shuning uchun Temur yutadi.

Misollar:

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