A. Uy vazifasi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Isfandiyorga bu safar kvadrat tenglamalar mavzusida uy vazifasi berildi: \(ax^2+bx+c=0\) tenglamaning ildizlarini topish. Tabiiyki, Isfandiyor bu tenglamani osongina yechdi va sizdan o’zining yechimini tekshirib berishni so’radi.

Kiruvchi ma'lumotlar:

Bitta qatorda \(a\),\(b\),\(c\) va \(x\) butun sonlar kiritiladi. \((|a|, |b|, |c|, |x| \leq 100, a \neq 0)\)

Chiquvchi ma'lumotlar:

Agar \(ax^2+bx+c=0\) bo’lsa “YES”, aks holda “NO” chiqaring.

Izoh:

Birinchi misolda \(2^2-5 \times 2 + 6 = 0\), demak javob “YES”
Uchinchi misolda \(2 \times 5^2 + 6 \times 5 - 4 \neq 0\), demak javob “NO”

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 -5 6 2	YES
2	1 -5 6 3	YES
3	2 6 -4 5	NO
4	24 -100 -100 5	YES

B. Ko'paytma

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga uzunligi \(n\) ga teng \(a\) massiv berilgan. Massivning go’zalligi deb uning elementlari ko’paytmasiga aytiladi. Bitta operatsiyada massivning ixtiyoriy elementini qiymatini oshirib qo’yishingiz mumkin. Ko’pi bilan \(k\) ta operatsiyadan so’ng, massivning hosil qilish mumkin bo’lgan eng katta go’zalligini \(10^9+7\) ga bo’lgandagi qoldig’ini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) va \(k\) butun sonlar \((1 \leq n, k \leq 100)\)
Keyingi qatorda \(n\) ta butun son, \(a_1,a_2,...,a_n\) kiritiladi \((1 \leq a_i \leq 100)\)

Chiquvchi ma'lumotlar:

Bitta qatorda masalaning javobini \(10^9+7\) ga bo’lgandagi qoldig’ini chiqaring.

Izoh:

\(a_1\) ning qiymatini oshirsak, ko’paytma \(2 \times 5 \times 3 = 30\). Ko’rish mumkinki, 30 dan katta javob hosil qilib bo’lmaydi.

Misollar:

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

C. Ajoyib ketma-ketliklar

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Uzungligi \(m\) ga teng \(b_1,b_2,...,b_m\) ketma-ketlik ajoyib bo’lishi uchun, uning ikki chetidagi elementlari qolgan \(m-2\) ta elementdan qat’iy katta bo’lishi kerak. Boshqacha qilib aytganda \(\min (b_1,b_m) > \max (b_2,b_3,...,b_{m-1})\) shart bajarilishi kerak. E’tibor bering, \(m \leq 2\) bo’lsa ketma-ketlik ajoyib hisoblanadi.

Sizga uzunligi \(n\) ga teng \(a\) massiv berilgan. Sizning vazifangiz massivni bir nechta oraliqlarga bo’lish, bunda har bir element aynan bitta oraliqqa tegishli bo’ladi va har bir oraliqdagi elementlar ajoyib ketma-ketlikni tashkil qiladi. Yuqoridagi shartlar bajarilishi uchun minimal oraliqlar sonini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) kiritiladi \((1 \leq n \leq 200000)\)
Ikkinchi qatorda \(a_1, a_2, ..., a_n\) kiritiladi \((1 \leq a_i \leq 10^9)\).

Chiquvchi ma'lumotlar:

Bitta qatorda minimal oraliqlar sonini chiqaring.

Izoh:

Birinchi misolda massivni \([4,1,5], [3], [9,5,7,8,9]\) ko’rinishida bo’lish mumkin.
Ikkinchi misolda massivni \([2, 2], [2]\) ko’rinishida bo’lish mumkin.
Uchinchi misolda butun massiv ajoyib hisoblanadi, demak minimal javob 1.

Misollar:

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

D. Liplandiya

Xotira: 512 MB, Vaqt: 3000 ms

Masala

Isfandiyor Liplandiya davlatiga asos soldi. Liplandiya \(n\) ta shahar va ular orasida \(n-1\) ta yo’l bor (Liplandiyani daraxt – oddiy, bog’lamli va sikllarsiz graf deyishimiz mumkin).

Isfandiyor Liplandiyaning poytaxtini \(1\) – shahar deb nomladi. So’ngra u \(1\)-shahardan eng yaqin hali raqamlanmagan (agar eng yaqinlari bir nechta bo’lsa ixtiyoriysiga bordi) shaharga bordi va o’sha shaharni \(2\)-shahar deb nomladi. So’ngra \(2\)-shaharga eng yaqin hali raqamlanmagan shaharga borib uni \(3\)-shahar deb nomladi. Shu tartibda shaharlarga \(1...n\) sonlar bilan raqamlab chiqdi.

\(dist(a,b)\) deb \(a\) shahardan \(b\) shaharga boruvchi eng qisqa yo’lning uzunligini ataymiz. Sizga \(q\) ta so’rovda \(x\) soni beriladi. Sizning vazifangiz \(dist(a,b) \geq x\) bo’lgan leksikografik eng kichik \((a,b)\) juftlikni topish.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) natural son \((2 \leq n \leq 200000)\).
Keyingi \(n-1\) ta qatorda 𝑎 va 𝑏 qo’shni shaharlar raqamlari beriladi \((1 \leq a, b \leq n, a \neq b)\).
Keyingi qatorda \(q\) natural son \((1 \leq q \leq 200000)\).
Keyingi \(q\) ta qatorda \(x\) butun son \((0 \leq x < n)\).

Kiritilgan graf daraxt ekanligi va shaharlar Isfandiyor xohlaganiday raqamlangani kafolatlanadi.

Chiquvchi ma'lumotlar:

Har bir so’rov uchun agarda bunday juftlik mavjud bo’lsa, leksikografik eng kichigini, aks holda ikkita \(-1\) ni chop eting.

Misollar:

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

E. Super massiv

Xotira: 64 MB, Vaqt: 2000 ms

Masala

Uzunligi \(m\) ga teng \(b\) massiv super massiv deyiladi, agar \(b_1 \oplus b_2 \oplus ... \oplus b_m = b_1 \& b_2 \& ... \& b_m\) shart bajarilsa. Bu yerda \(\oplus\) - bitwise XOR, \(\&\) - esa bitwise AND amali.

Sizga uzunligi \(n\) ga teng \(a\) massiv berilgan. Massivga ko’pi bilan 3 ta \([1 ... 2^{30}-1]\) oralig’idagi son qo’shib uni super massiv qiling. Bunda siz massivga umuman son qo’shmasligingiz ham mumkin.

E’tibor bering, qo’shiladigan sonlar sonini kamaytirish shart emas, shunchaki ko’pida 3ta son qo’shib super massiv yasash yetarli. Agar to’g’ri javoblar bir-nechta bo’lsa, ixtiyoriysini chiqarishingiz mumkin.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) butun son \((1 \leq n \leq 10^5)\)
Ikkinchi qatorda \(a_1,a_2,...,a_n\) kiritiladi \((1 \leq a_i \leq 2^{30}-1)\)

Chiquvchi ma'lumotlar:

Birinchi qatorda \(k\) – qo’shiladigan sonlar sonini chiqaring \((0 \leq k \leq 3)\).
Agar \(k>0\) bo’lsa, ikkinchi qatorda qo’shiladigan sonlarni probel bilan ajratgan holda chiqaring.

Agar to’g’ri javoblar bir-nechta bo’lsa, ixtiyoriysini chiqarishingiz mumkin.

Izoh:

Birinchi misolda 2 va 15 qo’shilgandan so’ng \(a=[3,1,7,13,5,2,15]\). \(a_1 \oplus a_2 \oplus ... \oplus a_7 = a_1 \& a_2 \& ... \& a_7 = 0\)
Ikkinchi misolda shunaqasiga ham \(a_1 \oplus a_2 \oplus a_3 = a_1 \& a_2 \& a_3 = 0\)

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 1 7 13 5	2 2 15
2	3 1 2 3	0

F. Qismsatr

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bu interaktiv masala!

Uzunligi \(n\) ga teng \(a_1,a_2,...,a_n\) nomanfiy butun son yashirilgan. Siz bitta so’rovda uning ixtiyoriy o’rindagi raqamini so’rashingiz mumkin. Ko’pi bilan 2ta so’rov yordamida, sonning 3ga bo’linadigan qismsatri bor yoki yo’qligini toping.

Ya’ni, shunday \(l\) va \(r\) \((1 \leq l \leq r \leq n)\) sonlar mavjudmi, bunda \(a_la_{l+1}...a_r = a_l \times 10^{r-l} + a_{l+1} \times 10^{r-l-1} + ... + a_r\) butun son 3 ga qoldiqsiz bo’linadi.

So'rov berish tartibi:
Sonning qaysidir raqamini bilish uchun ? i ko'rinishida ekranga chiqaring, javob tariqasida alohida qatorda \(a_i\) ning qiymatini olasiz. Agar so'rolar soni 2 tadan oshib ketsa Wrong Answer verdiktini olasiz.
Javobni topganingizdan so'ng, agar shartni qanoatlantiruvchi \(l\) va \(r\) mavjud bo'lsa ! YES, aks holda ! NO chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) butun son kiritiladi \((1 \le n \le 100)\)

Har bir berilgan so'rov uchun \(a_i\) ning qiymatini olasiz.

Chiquvchi ma'lumotlar:

So'rov berish uchun ? i, javob berish uchun ! YES yoki ! NO chiqaring. Siz ko'pida 2 marta so'rov va aynan 1 marta javob berishingiz kerak.

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()

Izoh:

74325 soni o’ylangan edi. “? 1” so’roviga 7 va “? 3” so’roviga 3 javob berildi. \(𝑙=𝑟=3\) bo’lgan qismsatr = 3 va u 3ga bo’linadi. Demak javob YES.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 7 3	? 1 ? 3 ! YES