A. Yo’l vazni

Xotira: 16 MB, Vaqt: 2000 ms

Masala

Sizga \(N\) ta tugundan iborat daraxt berilgan. Daraxtning har bir tugunida nomanfiy qiymat mavjud, bu qiymat shu tugunni bosib o’tish uchun qancha energiya sarflanishini anglatadi. \(\text{Vazn}(A,B)\) deb \(A\) tugundan \(B\) tugunga borish yo’li davomida bosib o’tiladigan (\(A\) va \(B\) tugundan tashqari) barcha tugunlardagi qiymatlar yig’indisiga aytiladi. Sizda daraxt tugunlaridagi qiymatlarni ixtiyoriy nomanfiy qiymatga o’zgartirish imkoniyati bor. Siz \(\sum_{A=1}^{N} \sum_{B=1}^{N} \text{Vazn}(A,B) = 0\) ayniyat to’g’ri bo’lishi uchun kamida nechta tugunning qiymati o’zgartirilishi kerakligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 10)\) testlar soni kiritiladi.

Har bir test uchun:

Dastlabki satrida bitta butun son, \(N(1 \le N \le 10^5)\) daraxt tugunlari soni kiritiladi.

Keyingi \(N-1\) ta satrda \(U\) va \(V(1 \le U, V \le N, U \neq V)\) juftliklar kiritiladi, bu juftliklar daraxtning \(U\) va \(V\) tugunlari orasida yo’l mavjuligini ifodalaydi.

Oxirgi qatorda esa \([0, 10^9]\) oralig’idagi \(N\) ta butun son, daraxt tugunlarida keltirilgan qiymatlar.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda \(\sum_{A=1}^{N} \sum_{B=1}^{N} \text{Vazn}(A,B) = 0\) ayniyat to’g’ri chiqishi uchun eng kamida nechta tugunning qiymatini nomanfiy butun songa almashtirish kerakligini chop eting

Misollar:

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

B. Sonni izlab top!

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Bu interaktiv masala!

Hakamlar hay’ati dasturi \(N(1 ≤ N ≤ 10^9)\) sonini o’ylaydi. Sizning dasturingiz ko’pi bilan 100 ta so’rovda hakamlar hay’ati dasturi o’ylagan sonni izlab topishi talab etiladi. Har bir so’rovda dasturingiz hakamlar hay’atining dasturiga “\(? \space X\)” ko’rinishida so’rov jo’natishi mumkin(bu yerda \(X(1 ≤ X ≤ 10^9)\) butun son), bunga javoban hakamlar hay’ati dasturi sizning dasturingizga \(X \space mod \space N\) ning qiymatini kiritadi.

Dasturingiz so’ngida siz “\(! \space X\)” ko’rinishida hakamlar hay’ati dasturi o’ylagan sonni chop etishingiz kerak.

Kiruvchi ma'lumotlar:

Kirish oqimida sizning \(?\) belgisi yordamida so’ragan har bir so’rovingizga alohida qatorda hakamlar hay’atining dasturiga bergan \(X\) soningizga mos \(X \space mod \space N\) ning qiymati kiritiladi.

Chiquvchi ma'lumotlar:

Ko’pi bilan 100 ta so’rovdan foydalangan holda hakamlar hay’atining dasturi o’ylagan sonni izlab toping.

ESLATMA: Interaktiv masalada sizning javobingizni hakamlar hay’ati qabul qila olishi uchun siz har bir so’rovingiz oxirida

Agar Pascal tilida ishlagan bo’lsangiz: flush(output)
Agar C/C++ tilida ishlagan bo’lsangiz fflush(stdout) yoki cout.flush()
Agar Java tilida ishlagan bo’lsangiz System.out.flush()
Agar pythonda ishlagan bo’lsangiz sys.stdout.flush()
Agar C# tilida ishlagan bo’lsangiz Console.Out.Flush()

Buyruqlardan birini yozishingiz kerak bo’ladi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 0 0	? 10 ? 8 ? 4 ! 4

C. Massivdan o’chirish o’yini

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Kunlardan bir kun Eshmat zerikib qoldi va ukasi Toshmatni o’yin o’ynash uchun chaqirib oldi. O’yin har xil qiymatlardan tashkil topgan massiv ustida o’ynaladi. O’yin qoidalari quyidagichi:

Toshmat doim o’yinni birinchi bo’lib boshlab beradi.
Har bir yurishda o’yinchi massiv ichidan maksimum elementni tanlab oladi hamda maksimum element va undan keyingi barcha massiv elementlarini massivdan o’chiradi. Misol uchun massiv [2, 4, 5, 3, 1] holatda bo’lsa [5, 3, 1] o’chganidan so’ng massivda [2,4] qoladi.
O’yinchilar o’z yurishlarini navbatma-navbat amalga oshiradilar.
Yurishni amalga oshira olmagan o’yinchi (o’z navbati kelganida massiv bo’sh bo’lsa yurishni amalga oshirib bo’lmaydi) o’yinda yutqazadi.

Eshmat va Toshmat jami T marotaba o’yin o’ynashdi, har bir o’yin uchun o’yinda kim g’olib bo’lganligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 100)\) soni kiritiladi. Keyingi qatordan boshlab, har bir o’yin uchun alohida ikkita qatorning birinchi satrida bitta butun son, \(N(1 \le N \le 10^5)\) o’yin boshidagi massiv elementlari soni kiritiladi, ikkinchi satrida esa \(N\) ta butun son, massiv elementlari (\([1, 10^9]\) oralig’idagi sonlar) kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir o’yin uchun alohida qatorda, o’yin g’olibini chop eting!

Misollar:

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

D. Sonlar fayli

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Abdulla natural \(X\) sonidan boshlab ketma-ket joylashgan \(K(K > 1)\) ta sonni ketma-ketligini buzmagan holda faylga yozdi. Ming afsuski u yozgan sonlari orasiga bo’sh joy tashlashni unutibdi. Faylning ichidagi ma’lumotdan foydalanib \(X\) ning qiymatini aniqlang!

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 10)\) testlar soni kiritiladi. Har bir test uchun alohida satrda faqat raqamlardan iborat bo’lgan \(S(1 \le |S| \le 32)\) satri, ya’ni fayldagi satr kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda, agar kiritilgan satr Abdullaning faylidagi satr bo’lsa \(\text{YES X}\), aks holda \(\text{NO}\) deb chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7 1234 91011 99100 101103 010203 13 1	YES 1 YES 9 YES 99 NO NO NO NO

E. Toq sonlar guruhi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Musbat toq sonlar qiymati jihatidan o’sish tartibida \((1,3,5,7,9,11,13,15,19, \dots)\) joylashtirildi, hamda \((1), (3,5), (7,9,11),(13,15,17,19), \dots\) shaklida guruhlarga taqsimlangan, ya’ni \(k\)-tartibli guruhda navbati kelgan \(k\) ta toq son joylashgan. Sizga \(k\) soni beriladi, siz \(k\)-guruhdagi sonlar yig’indisini chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida bitta butun son, \(k(1 \le k \le 10^6)\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona son, \(k\)-guruhdagi sonlar yig’indisini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3	27

F. Sichqon va Mushuklar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Ikkita mushuk va bitta sichqon to’g’ri chiziq bo’ylab turli xil nuqtalarda joylashgan. Sizga ularning boshlang’ich nuqtalari berilgan. Sichqon pishloq iste’mol qilish bilan ovora bo’lganligi uchun mushuklarni ko’rmagan, shuning uchun u mushuklardan qochmasdan o’z o’rnidan qimirlamaydi, Ikkala mushukning tezligi bir xil, qaysi mushuk sichqonning oldiga birinchi yetib kelsa sichqonni o’sha mushuk qo’lga kiritadi. Agar ikkala mushuk ham sichqonni oldiga bir vaqtda yetib kelishsa sichqonni ustiga o’zaro tortishib qolishadi va paytdan foydalangan holda sichqon qochib qoladi. Sizning vazifangiz:

Agar birinchi mushuk sichqonni qo’lga kiritsa “1-mushuk”
Agar ikkinchi mushuk sichqonni qo’lga kiritsa “2-mushuk”
Agar sichqon qochib qolsa “sichqon”

deb xabar chiqarishdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida 3 ta butun son, \(A, B\) va \(C (1 \le A,B,C\le100)\) sonlari berilgan, bu sonlar mos ravishda 1-mushukning, 2-mushukning va sichqonning boshlang’ich nuqtalari hisoblanadi.

Chiquvchi ma'lumotlar:

So’ralgan javobni chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 2 3	2-mushuk
2	1 3 2	sichqon