A. Uchburchak

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Asilbekda $a$ , $b$ va $c$ uzunlikdagi tayoqchalari bor. Asilbek bulardan foydalanib teng yonli uchburchak yasamoqchi, bunda tayoqchalarni birlashtirish yoki bo'laklash mumkin emas. Asilbekka uchburchak yasay olishini xabar bering.

Eslatma: Teng yonli uchburchak deb ikki tomoni uzunligi bir xil bo'lgan, uchinchi tomoni bir xil bo'lmagan uchburchakka aytiladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda $t$ testlar soni kiritiladi.

Keyingi $t$ qatorning har birida uchta butun son - $a$ , $b$ , $c$ kiritiladi.

$1 \le t \le 500$

$1 \le a, b, c \le 100$

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda agar teng yonli uchburchak yasash imkoni bo'lsa “Yes”, aks holda “No” yozuvini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 5 4 5 6 7 8 1 2 4 4 4 7	Yes No No Yes

B. Ikkilik sanoq sistemasi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Dunyoda 10 xil insonlar bor, bular ikkilik sanoq sistemasini tushunadiganlar, va boshqalar. Siz birinchi turdagi insonlardansiz. Sizga $N$ soni beriladi, siz berilgan sonni ikkilik sanoq sistemasida ifodalang, hamda natijaning raqamlar yig‘indisini ham hisoblang.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida bitta butun son, $N(0 \le N \le 10^{18})$ soni berilgan.

Chiquvchi ma'lumotlar:

Chiqish faylining yagona satrida bo'sh joy bilan ajratilgan holda ikkita butun son, sonini ikkilik sanoq sistemasida ifodalang, hamda shu ifodalanishning raqamlar yig‘indisini ikkilik sanoq sistemasida chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	14	1110 11
2	157	10011101 101

C. Massivni "tekislash"

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Zarifning tug'ilgan kuniga do'stlari $N$ ta elementdan tashkil topgan $A$ massivini sovg'a qilishdi. Zarif massivni ko'rib chiqdi va sovg'a qilingan massiv unga yoqmadi. Endi uni quyidagi amaldan xoxlagancha marotaba foydalanib o’zgartirmoqchi:

massivning istalgan elementini tanlab, uning qiymatiga $p$ ni qo'shadi va qolgan barcha elementga $q$ ni qo'shadi.

Zarif minimal operatsiyalar yordamida massivdagi barcha elementlarning qiymatini $K$ dan kichik bo'lmagan qilib o'zgartirmoqchi. Bunga yetarli bo'ladigan operatsiyalar sonini chop eting.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ va $K$ kiritiladi.

Ikkinchi qatorda $q$ va $p$ kiritiladi.

Keyingi qatorda $N$ ta son - $A$ massivi elementlari kiritiladi.

Barcha kiruvchi qiymatlar butun.

$1 \le N, K \le 10^5$

$1 \le q < p \le 10^5$

$1 \le A_i \le 10^5$

Chiquvchi ma'lumotlar:

Minimum operatsiyalar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 8 3 9 5 8 5 8 4	1
2	3 5 5 6 6 9 9	0

D. Binar satrni almashtirish

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Shohruhda $0$ va $1$ dan tashkil topgan binar satri mavjud. Bir amalda satrdagi ixtiyoriy $01$ qism-satrini tanlab uni $110$ ga o'zgartirish mumkin. Satrda $01$ satri qolmasligi uchun yuqoridagi amaldan eng kamida necha marotaba foydalanish kerakligini aniqlang. Natija juda katta bo'lishi mumkin, shuning uchun uni $10^9+7$ ga bo'lgandagi qoldiqni chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining yagona qatorida $s(|s| \le 10^5)$ satri kiritiladi.

Chiquvchi ma'lumotlar:

Minimum amallar sonini $10^9+7$ ga bo'lgandagi qoldiqni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	101	1
2	0101	4

E. Qaysarchalar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Kechki soat 16:40. 20 daqiqadan keyin bolalarni o'z uyiga olib ketishadi. Bog'chadagi tarbiyachining e'tiborsizligi tufayli bolalar bir-birining sumkasini taqib olishdi. Endi har bir bolaga o'zining sumkasini berish kerak. Ammo buning uchun hammani so'mkasini yig'ib olib qaytadan tarqatishning imkoni yo'q, ya'ni bolajonlar so'mkasiz uyga jo'natishi mumkin deb o'ylashadi. Shu sababli bog'cha tarbiyachisi barcha bolalarning so'mkasi o'zida bo'lib qolmaguniqa qadar xoxlagan marotaba ixtiyoriy ikkita bo'lani yoniga chaqirib ularning so'mkasini almashtiradi. Bu amalni bajarishda bog'cha tarbiyachisi almashtirilayotgan so'mkalarning vaznlari yig'indisicha energiya sarflaydi. Kun kech bo'lgani uchun tarbiyachi juda charchagan, shu sababli iloji boricha kamroq energiya sarflagan holda barcha bolaga o'z sumkasini bermoqchi. Bog'cha tarbiyachisi barcha bolaga o'zining so'mkasini berishi uchun eng kamida qancha energiya sarflashini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N(1 \le N \le 10^6)$ - bolalar soni kiritiladi.

Keyingi qatorda $N$ ta butun son $A_i(1\le A_i \le 10^4)$ - har bir sumka vazni.

Uchinchi qatorda $N$ ta butun son $B_i(1 \le B_i \le N)$ - har bir bolaning yelkasidagi sumka raqami kiritiladi.

So'nggi qatorda $N$ ta butun son $C_i(1\le C_i \le N)$ - har bir bolaning sumkasi raqami kiritiladi. Barcha $i \neq j$ uchun $B_i \ne B_j$ va $C_i \ne C_j$ shart bajariladi. Ya’ni $B$ va $C$ massivlari $1$ dan $N$ gacha sonlarning permutatsiyasi hisoblanadi.

Chiquvchi ma'lumotlar:

Barcha bolalar o'z sumkasiga ega bo'lishi uchun sarflanishi kerak bo'lgan minimal energiya miqdorini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	8 197 170 124 180 128 163 188 140 2 5 7 8 1 3 6 4 5 6 1 8 2 4 7 3	1534
2	6 40 24 20 12 24 16 2 5 6 4 1 3 6 4 3 5 1 2	112

F. Kanji for king (王)

Xotira: 32 MB, Vaqt: 1000 ms

Masala

N tugunli daraxt bor. Tugunlar 1 dan N gacha raqamlangan. Daraxtning nechta har xil sub-daraxti(bir yoki bir nechta qo’shni tugunlardan tashkil topgan qismi)ni "Kanji for King" daraxti shaklida ifodalash mumkinligini aniqlang!

Kanji for king daraxti:

Agar bitta sub-daraxtda qaysidir tugun mavjud bo'lsa, lekin boshqa sub-daraxtda bo'lmasa, ikkita sub-daraxt har xil hisoblanadi.

Daraxt - sikl mavjud bo'lmagan va bir tugundan boshqasiga har doim yo'l mavjud bo'lgan graf.

Kiruvchi ma'lumotlar:

Kirish faylining 1-qatorida $N(1 \le N \le 10^5)$ - tugunlar soni kiritiladi. Keyingi N-1 ta qatorning har biri ikkita butun son - $u$ va $v$ $(1 \le u , v \le N, u \ne v$ kiritiladi - bu degani $u$ va $v$ tugunlar o'zaro bog'langan.

Chiquvchi ma'lumotlar:

Daraxtning nechta har xil sub-daraxtini "Kanji for King" daraxti shaklida ifodalash mumkinligini aniqlang, hamda uni $10^9+7$ ga bo'lgandagi qoldiqni chop eting.

Izoh:

1-test uchun daraxt ko'rinishi:

Ushbu daraxtda faqatgina 1 ta Kanji for king daraxti mavjud.

2-test uchun quyidagi tugunlar Kanji for king daraxti bo'la oladi:

1, 2, 3, 4, 5, 6, 7, 8, 9
10, 11, 12, 13, 9, 14, 15, 16, 17
10, 11, 12, 8, 9, 14, 15, 16, 17
10, 11, 12, 8, 9, 13, 15, 16, 17
10, 11, 12, 13, 9, 14, 7, 8, 5
10, 11, 12, 13, 9, 16, 7, 8, 5
10, 11, 12, 14, 9, 16, 7, 8, 5
7, 8, 5, 11, 9, 13, 15, 16, 17
7, 8, 5, 11, 9, 14, 15, 16, 17
7, 8, 5, 13, 9, 14, 15, 16, 17

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	9 1 2 2 3 4 5 5 6 7 8 8 9 2 5 5 8	1
2	17 1 2 2 3 4 5 5 6 7 8 8 9 2 5 5 8 10 11 11 12 13 9 9 14 15 16 16 17 11 9 9 16	10