A. Daraxtni bo’yash #3

Xotira: 16 MB, Vaqt: 1000 ms

Masala

\(n\) ta tugundan iborat ildizga ega binar daraxt berilgan (rooted binary tree). Ya’ni daraxtning har bir tugunini ko’pi bilan ikkita bolasi bo’lishi mumkin.
Berilgan daraxtda iloji boricha ko’p tugunlarni bo’yash kerakki, bo’yalganidan so’ng daraxt muvozanatlangan bo’lib qolsin.

Muvozanatlangan daraxt deb quyidagi shartni qanoatlantiruvchi daraxtga aytiladi:
- har bir ikkita bolasi bor \(u\) tugun uchun, shu bolalarini \(x\) va \(y\) bilan belgilaydigan bo’lsak, ildizi \(x\) da bo’lgan va ildizi \(y\) da bo’lgan qism daraxtlardagi bo’yalgan tugunlar soni teng bo’lsin.

Masalan, quyidagi daraxt muvozanatlangan daraxtga misol bo’la oladi:

- 3-tugunni ikkala bolasidagi qism daraxtda 1 tadan bo’yalgan tugun bor.
- 1-tugunni ikkala bolasidagi qism daraxtda 2 tadan bo’yalgan tugun bor.
- 4-tugunni bolalari soni 1 ta bo’lgani sabab, uni e’tiborga olish shart emas.

Kiruvchi ma'lumotlar:

Birinchi qatorda tugunlar soni \(n\) kiritiladi \((1 ≤ n ≤ 10^5)\). Ikkinchi qatorda daraxt qirralarini ifodalovchi \(n - 1\) ta \(u\) va \(v\) ko’rinishidagi sonlar juftligi beriladi \((1 ≤ u, v ≤ n, u \ne v)\). Daraxt ildizi doim 1-tugun bo’ladi.

1-subtask(9 ball): Har bir tugunning ko’pi bilan bitta bolasi bor, \(n ≤ 100\)
2-subtask(20 ball): \(n ≤ 15\)
3-subtask(31 ball): Har bir tugunning 0 ta yoki 2 ta bolasi bor \(n ≤ 10^5\)
4-subtask(40 ball): \(n ≤ 10^5\)

Chiquvchi ma'lumotlar:

Bitta butun son - bo’yash mumkin bo’lgan maksimal tugunlar sonini chiqaring.

Izoh:

Birinchi misoldagi daraxt yuqoridagi rasmda keltirilgan. Faqat qo’shimchasiga 1-tugunni ham bo’yash imkoni bor, shuning uchun javob 5.

Misollar:

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

B. A+B

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Ikkita butun son A va B ning yig'indisini hisoblang

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining alohida qatorlarida ikkita manfiy bo'lmagan butun sonlar berilgan, sonlar 10¹⁰⁰ dan oshmaydi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylining yagona satrida berilgan ikki sonning yig'indisini(boshlang'ich nollarsiz) chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4	7

C. A+B #3

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Ikkita sonni bir biriga qo'shing, lekin sizga sonlar o'rniga lotin alifbosining katta harflari beriladi.
1, 2, 3 ... sonlari o'rniga 'A', 'B', 'C', ... harflari beriladi.
Sizga lotin alifbosining nechanchi o'rnidagi harf berilgan bo'lsa har o'sha songa teng deb hisoblanadi. Masalan 1 = 'A' , 2 = 'B' , .... 26 = 'Z'.

Kiruvchi ma'lumotlar:

Bitta qatorda 2 ta belgi. Belgilar lotin alifbosining katta harflaridan biri bo'ladi.

Chiquvchi ma'lumotlar:

Berilgan harflarning songa o'tkazgandagi yig'indisini toping

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	A B	3
2	A Z	27

D. A+B

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Kiruvchi ma'lumotlar:

1ta qatorda a va b

Chiquvchi ma'lumotlar:

.

Misollar:

#	INPUT.TXT	OUTPUT.TXT

E. Kanfetlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Qopda N xil turdagi kanfetning har biridan cheksiz miqdorda mavjud. Qopdan bir marotabada K ta kanfet olishning necha xil turi bor?

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining birinchi satrida bitta butun son, \(T(1 ≤ T ≤ 200)\) testlar soni.
Keyin har bir test uchun alohida qatorda ikkitadan butun son, \(N\) va \(K(1 ≤ N, K < 1000)\) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda masala javobini chiqaring. Javob juda katta bo'lishi mumkin, shuning uchun siz javobning \(10^9+7\) ga bo'lgandagi qoldig'ini chiqaring.

Misollar:

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