A. Shubhasiz
Xotira: 256 MB, Vaqt: 1000 msTATU universiteti Professori Qodirov, uy vazifalarini sun'iy intellekt yordamida bajaradigan talabalar soni keskin oshganini aniqladi. Qodirov sun'iy intellekt ba'zi so'zlarni odatdagidan ko'proq ishlatishini angladi, ayniqsa "shubhasiz" so'zini. Professor talabalarning shubhali vazifalalarini tekshirishda sizdan yordam so'ramoqda.
Kirish faylining yagona satrida ingliz alifbosining kichik harflari, probel va nuqta (.) dan tashkil topgan talabaning bajargan vazifasi kiritiladi. Matn uzunligi \(10^4\) dan oshmasligi kafolatlanadi.
Matnda nechta "shubhasiz" so'zi borligini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
shubhasiz bu kod talaba tomonidan yozilgan |
1 |
| 2 |
shubhasizshubhasizshubhasizshubhasizshubhasiz |
5 |
B. Masala ishlash
Xotira: 256 MB, Vaqt: 1000 msAzizbek va Shohruh xalqaro olimpiadaga tayyorlanmoqda. Tayyorgarlik jarayonini qiziqarliroq qilish maqsadida o'zaro musobaqa qilishdi. Musobaqa quyidagicha: \(N\) ta masala bor, Azizbek har bir masalani ishlash uchun \(T_1\) daqiqa vaqt sarflaydi, \(i-\) masalani ishlab bo'lgandan so'ng \(i \times D_1\) daqiqa dam oladi. Xuddi shunday Shohruh ham, har bir masalani ishlash uchun \(T_2\) daqiqa sarflaydi, va \(i-\) masalani ishlagandan so'ng \(i \times D_2\) daqiqa dam oladi. Agar Shohruh va Azizbek bir vaqtda masala ishlashni boshlasa, kim birinchi barcha masalani ishlab tugatadi?
Birinchi qatorda butun son \(T \ (1 \le T \le 4000)\) - testlar soni kiritiladi.
Har bir test uchun alohida qatorda beshta butun son \(N, \ T_1, \ D_1, \ T_2, \ D_2\) kiritiladi. Kiritilgan barcha qiymatlar natural son va \(10^5\) dan oshmasligi kafolatlanadi.
Har bir test uchun alohida qatorda, agar Azizbek masalalarni ishlab tugata olsa "Azizbek", Shohruh birinchi tugatsa "Shohruh", aks holda bir vaqtda tugatishsa "Durang" so'zini (qavslarsiz) chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 3 10 2 8 3 3 10 2 8 4 3 10 2 8 5 |
Shohruh Durang Azizbek |
C. Haqiqatni top!
Xotira: 256 MB, Vaqt: 2000 msXonada \(N\) ta odam bor. Ularning ba'zilari rost gapiradi, qolganlari yolg'on gapiradi. Har bir odam quyidagicha gap aytadi: Xonadagi rost so'zlovchilar soni \([a, b]\) sonlari orasida. Xonada rost gapiruvchilarning maksimal soni nechta?
Birinchi qatorda bitta butun son \(N \ (1 \le N \le 10^6)\) - xonadagi odamlar soni kiritiladi.
Keyingi \(N\) ta qatorning har birida ikkitadan butun son - \(a, b \ (0 \le a \le b \le N)\) kiritiladi.
Masala javobini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 1 1 3 4 1 5 2 2 3 5 |
3 |
| 2 |
3 0 2 1 3 2 3 |
-1 |
D. Shaxmat doskasi
Xotira: 256 MB, Vaqt: 1000 ms\(N \times N\) shaxmat doskasi berilgan. Har bir katakda ma'lum bir natural son yozilgan. Sizda cheksiz miqdorda ruxlar bor. Ruxlarni shaxmat doskasiga shunday joylashtirib chiqingki, hech qaysi rux boshqasiga hujum qilmasin. Sizning natijangiz ruxlar turgan kataklardagi sonlar yig'indisi. Natijangizni maksimallashtiring.
Birinchi qatorda bitta butun son \(N \ (1 \le N \le 20)\) - shaxmat doskasi o'lchami beriladi.
Keyingi \(N\) ta qatorning har birida \(N\) tadan butun son, shaxmat doskasidagi elementlar kiritiladi. Barcha sonlar \([1, 10^9]\) oralig'ida ekanligi kafolatlanadi.
Maksimal natijani chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 18 1 16 5 10 6 13 8 4 17 5 5 3 14 11 4 12 13 6 20 10 11 5 1 4 |
73 |
| 2 |
2 7 7 3 5 |
12 |
E. Shokoladlar
Xotira: 256 MB, Vaqt: 1000 msBir guruh bolalar do'konga shokolad sotib olish uchun keldi. \(i-\) bola \(b_i\) ta shokolad olishni xohlaydi, bunda u sotib olgan barcha shokolad turli xil bo'lishi kerak. Do'kon sotuvchisiga buning iloji bor yoki yo'qligini ayting.
Birinchi qatorda ikkita butun son \(N\) va \(M\) - do'kondagi shokolad turlari va bolalar soni kiritiladi.
Keyingi qatorda \(N\) ta butun son \(a_i\) har bir shokolad turidan nechtadan borligi kiritiladi.
Keyingi qatorda \(M\) ta butun son \(b_i\) - har bir bola xohlaydigan shokoladlar soni kiritiladi.
\(1 \le N, M \le 2 \times 10 ^ 5\)
\(1 \le a_i, b_i \le 10^6\)
Barcha bolalarning istagini bajarish mumkin bo'lsa "YES", aks holda "NO" yozuvini (qo'shtirnoqlarsiz) chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 3 3 2 1 3 2 3 3 4 |
YES |
| 2 |
4 3 3 2 1 3 1 4 4 |
NO |
F. O’suvchi daraxt
Xotira: 256 MB, Vaqt: 1000 msSiz o‘sib boruvchi daraxt bilan ishlayapsiz.
Dastlab daraxtda faqatgina 1-tugun (vertex) mavjud bo‘lib, u ildiz (root) hisoblanadi.
Har bir tugunda uning qiymati yozilgan.
Sizga ketma-ket so‘rovlar beriladi. Ularni berilgan tartibda bajarib borish kerak.
Ba’zi so‘rovlar daraxtni kengaytiradi, ba’zilari esa daraxtning ma’lum bir qismi ustida savol beradi.
Kirish faylining birinchi qatorida ikkita butun son \( Q, S \) — so‘rovlar soni va birinchi tugunning qiymati kiritiladi.
Keyingi \( Q \) ta qatorning har birida quyidagi so‘rovlarning biri kiritiladi:
- \( 1\ p\ x \) — qiymati \( x \) bo‘lgan yangi tugun \( p \) tartib raqamli tugunga ulanadi.
Bunda yangi qo‘shilgan tugun tartib raqami \( t + 1 \) deb belgilanadi, bu yerda \( t \) — ayni vaqtdagi daraxtdagi tugunlar soni. - \( 2\ v \) — tartib raqami \( v \) bo‘lgan tugunning qism daraxtidan (subtree)
bo‘sh bo‘lmagan shunday tugunlar to‘plamini tanlangki, ushbu tugunlardagi qiymatlarning
umumiy XOR qiymati minimal bo‘lsin, boshqacha aytganda:
\( k = val_{p_1} \oplus val_{p_2} \oplus \dots \oplus val_{p_l}, \; p_i \in S \)
Bu yerda:
\( S \) — \( v \) tugunining qism daraxtidagi tanlangan tugunlar to‘plami,
\( val_i \) — \( i \)-tugunning qiymatini bildiradi.
Cheklovlar:
\( 1 \le Q \le 2 \times 10^5 \)
\( 0 \le S, x \le 10^9 \)
Barcha so‘rovlarda \( p \) va \( v \) tugunlari mavjudligi va to‘g‘riligiga kafolatlanadi.
Har bir ikkinchi turdagi so‘rov uchun minimal XOR qiymatini toping.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
10 7 1 1 5 2 1 1 2 6 2 1 1 3 14 1 1 5 2 3 1 5 0 1 5 7 2 5 |
2 1 6 0 |