A. Hasan va Ikkilik Funksiya
Xotira: 32 MB, Vaqt: 1000 msQuyidagi ikkilik satri berilgan bo'lib, u 0 yoki 1 dan iborat; ikkilik satrda ba'zi bir butun son ning ikkilik ko'rsatilishi ifodalangan. Sizdan quyidagi ifodani hisoblash so'raladi:
: dan kichik yoki teng maksimal butun sonni bildiradi, masalan = , .
Misol uchun, bo'lsa, u ni ifodalaydi va bo'ladi.
NOTE :
Birinchi qatorda bitta butun son berilgan: – test holatlarining soni.
Har bir test holatining birinchi qatori bitta butun sondan iborat: – satrining uzunligi.
Har bir test holatining ikkinchi qatori uzunlikdagi ikkilik satr ni o‘z ichiga oladi.
Shuningdek, testlarning umumiy yig‘indisi dan oshmasligi kafolatlangan.
Har bir test holati uchun bitta butun son: .
Birinchi test holatida shunday qilib, .
Ikkinchi test holatida shunday qilib, .
To'rtinchi test holatida shunday qilib, .
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
5 2 10 3 111 5 10011 6 111110 6 011010 |
1 2 4 5 4 |
B. Hasan va Go'zal!
Xotira: 32 MB, Vaqt: 1000 msBerilgan: butun sonlardan tashkil topgan massivi, uzunligi bo‘lgan va bir butun son .
Sizdan bo‘sh bo‘lmagan (ya’ni, kamida bitta elementdan iborat) qism massiv ni tanlab, quyidagi operatsiyalardan birini bajarishingiz talab qilinadi:
1. Tanlangan qism massivning barcha elementlarini ga ko‘paytirish, ya’ni .
2. Tanlangan qism massivning barcha elementlarini ga bo‘lish, natijani pastga yaxlitlash bilan, ya’ni .
ga teng yoki undan kichik bo‘lgan eng katta butun sonni ifodalaydi. Masalan, va .
massividagi barcha qism massivlar orasida, bitta bo‘sh bo‘lmagan qism massivni tanlab, unga yuqoridagi operatsiyalardan birini qo‘llagandan keyin tanlangan massiv yig‘indisining maksimal qiymati qancha bo‘lishi mumkin operatsiyani qo'llashdan keyin faqat bir marta?
Birinchi qatorda bitta butun son berilgan:
– test holatlarining soni.
Har bir test holatining birinchi qatori ikkita butun sondan iborat:
, (, ) – massiv uzunligi va butun son .
Har bir test holatining ikkinchi qatori ta ajratilgan butun sonlarni o‘z ichiga oladi: () – massiv .
Shuningdek, ning yig‘indisi barcha testlarda dan oshmasligi kafolatlangan.
Har bir test holati uchun bitta butun sonni chiqarish kerak: tanlangan qism massivning maksimal yig'indisi.
Birinchi test holatida, butun massivni tanlash optimal bo'ladi, natijada .
Ikkinchi test holatida, butun massivni tanlab, ko'paytirish amali bajarish optimal bo'ladi, .
Uchinchi test holatida, massivini tanlab, uni ga ko'paytirish optimal bo'ladi, natijada javob bo'ladi.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
3 5 1 10 5 10 5 10 5 3 10 -5 10 -5 10 3 4 1 -1 -2 |
40 60 4 |
C. Hasan va Maxsus O'chirish
Xotira: 1000 MB, Vaqt: 1000 msQuyidagi massiv berilgan: uzunligi bo'lgan butun sonlardan iborat. Keling, massivning funksiyasini aniqlaymiz, u massivdagi turli xil (unikal) butun sonlar soniga teng bo'ladi .
Masalan, , chunki unda uchta turli xil son mavjud: .
Siz faqat bitta amalni bajarishga ruxsat berilgansiz: uzunligi bo'lgan istalgan qism massivni tanlab, uni olib tashlash.
Masalan, agar va , bo'lsa, agar 3-chi va 4-chi elementlarni olib tashlasak, hosil bo'lgan massiv bo'ladi va
Operatsiyani bajargandan so‘ng, .
Birinchi qatorda bitta butun son berilgan:
– test holatlarining soni.
Har bir test holatining birinchi qatori ikkita butun sondan iborat:
va () – mos ravishda massiv uzunligi va olib tashlanadigan qism massiv uzunligi.
Har bir test holatining ikkinchi qatori
ta butun sonni o‘z ichiga oladi:
().
Shuningdek, ning yig‘indisi dan oshmasligi kafolatlangan.
Har bir test holati uchun bitta butun sonni chiqarish kerak:
.
Birinchi test holati uchun:
Qaysi qism massivni tanlamang, natija har doim ga teng bo'ladi.
Ikkinchi test holati uchun:
Qism massivni tanlashning ikki usuli mavjud: yoki ,
va hosil bo'lgan massiv ikkala holatda ham ta turli xil sonlarga ega bo'ladi.
To‘rtinchi test holati uchun:
Siz ni tanlashingiz kerak va hosil bo'lgan massiv
bo‘ladi, bu holda qiymat ga teng bo‘ladi.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
4 3 2 1 2 3 5 2 1 2 4 4 2 6 1 1 1 4 5 1 4 10 3 2 1 4 7 4 8 3 6 4 7 |
1 2 2 4 |
D. Hasan va Indeks Sanash
Xotira: 32 MB, Vaqt: 500 msBerilgan butun son , uzunligi bo'lgan nechta permutatsiya mavjudligini hisoblang, unda faqat bitta indeks mavjud bo'lib, u shartini qanoatlantiradi . Javobni ga bo'lgandagi qoldig'ini hisoblang.
Birinchi qatorda bitta butun son — testlar soni.
Har bir testning faqat bitta qatori bor, unda bitta butun son — permutatsiyasining uzunligi.
Bitta butun son – shunday permutatsiyalarning soni, ga nisbatan moduli.
uchun, amalga oshirilgan permutatsiyalar:
1. , bu yerda
2. , bu yerda
3. , bu yerda
4. , bu yerda
Javob: 4.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
1 3 |
4 |
E. Kvadrat uchburchak
Xotira: 512 MB, Vaqt: 1000 msSizga jadval berilgan, va sehirgar agar siz ta so'rov ga javob bersangiz shokolad beraman deb vada berdi, afsuski sehirgar uhlashni juda hohlab turgani uchun siz unga tez javob berishingiz kerak har bir so'rov da:
va beriladi sizni vazifangiz shunday lar summasini topshingiz kerak sharti bajariladi. Rasmiy ravishda:
Birinchi qatorda va ( , ) - satr va qatorni uzunligi va so'rovlar soni.
Keyingi qatorda jadval ().
Keyingi qatorda so'rovlar, har bir so'rovda va beriladi()
Har bir so'rovga javobni chiqaring - bitta butun son.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
3 5 15 19 11 18 20 3 9 4 4 1 2 1 1 1 2 3 3 2 2 |
54 15 54 4 20 |
2 |
6 7 2 1 1 1 19 5 16 13 16 7 19 8 10 2 14 14 16 13 3 7 3 16 10 4 8 12 12 1 16 17 18 12 10 6 5 4 4 4 4 5 3 6 2 3 4 4 1 2 1 5 |
16 42 124 43 16 16 165 |
F. Behruzbek va XOR so‘rovlar
Xotira: 512 MB, Vaqt: 2000 msBehruzbek massivlarda XOR operatsiyasini bajarishni juda ham yoqtiradi. Bir kuni uning oldiga do'sti Temur kelib, uzunligi bo'lgan massiv hamda turdagi ta so'rovlar berdi . Har bir so'rov uchun Behruzbekdan qismida joylashgan va qiymatlari oralig'ida bo'lgan elementlarning XOR ni topishni so'radi. Behruzbek bu muammoni bir o'zi hal qila olmadi, shuning uchun sizdan yordam umid qilmoqda. Unga Temurning barcha savollariga javob berishga yordam bering.
Birinchi qatorda bitta butun son mavjud - testlar soni.
Har bir test uchun birinchi qatorida ikkita butun son mavjud ) - massiv uzunligi va so'rovlar soni.
Keyingi qatorda ta butun sonlar - massiv elementlari kiritiladi.
Keyingi ta qatorning har birida ta butun son kiritiladi.
umumiy testlar summasi dan oshmasligi kafolatlangan.
Har bir so'rov uchun javobni yangi qatorda chop eting.
- -so'rov massivini oladi. Elementlardan faqat bittasi oralig'ida. Javob: .
- -so'rov massiv va diapazonni oladi. Javob: .
- -so'rov pastki qator (subarray) va oraliqni oladi. Javob: .
- -so'rov pastki qator (subarray) va diapazonni oladi. Javob: .
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
1 5 4 5 1 4 2 3 1 5 1 1 1 5 1 100 1 3 2 100 2 3 2 100 |
1 1 1 4 |
G. Hasan va Adolatli Bo'linish
Xotira: 64 MB, Vaqt: 1000 msBir musobaqada ta ishtirokchi bor, har birining kuchi bo'lib, va har bir ishtirokchining kuchi noyob (har bir o'yinchida faqat bitta noyob qiymat mavjud). Ishtirokchilar ikki jamoaga bo'linadi va ular o'yinni iloji boricha adolatli qilishni xohlaydi, shuning uchun ular jamoalarining kuchi teng bo'lishini istaydi. Biror jamoaning kuchi quyidagicha aniqlanadi:
Birinchi jamoaning kuchi va ikkinchi jamoaning kuchi o'rtasidagi minimal nisbatni aniqlang (Nisbat har doim butun son bo'lishini unutmang). Javob katta bo'lishi mumkin, shuning uchun uni ga bo'lganda chiqaring.
E'tibor bering, uchun javob 1 ga teng.
Birinchi qatorda bitta butun son — test holatlari soni.
Har bir test holatining yagona qatorida bitta butun son — ishtirokchilar soni.
Bu miqdor kafolatlangan oshmaydi .
Bitta butun son, minimal nisbati moduli bo'yicha.
uchun eng yaxshi bo'linish quyidagicha:
javob quyidagicha bo'ladi:
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
1 4 |
6 |
H. Qo'shish
Xotira: 512 MB, Vaqt: 1500 msJahonali oson masalarni yechishdan zerikdi, shuning uchun u qiyinroq masala o'ylab topdi. U boshida bo'sh massivga ega(). Shundan so'ng, ta hodisa sodir bo'ladi Har bir hodisa quyidagilardan biri bo'lishi mumkin:
- yangi element ni va orasiga qo'shish. Yangi massiv shunday bo'ladi:
- -chi elementni chiqarish ya'ni .
Dastlab, Jahonali bu masalani oson deb o‘yladi. Biroq, biroz o‘ylab ko‘rgach, u buni yecha olmasligini tushundi. Jahonalining do‘sti sifatida, sizga ushbu masalani hal qilish topshirildi
- Bu yerda massivni uzunligi.
Birinchi qatorda () - hodisalar soni.
Keyingi ta qatorda quyidagi berilgan hodisalardan bitta bo'ladi har bir hodisa uchun:
(, ) - yangi element ni va orasiga qo'shish.
() - -chi elementni chiqarish ya'ni .
- Bu yerda massivni uzunligi.
Har bir turdagi so'rovga - bitta natural son chiqaring.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
15 1 0 17 2 1 1 0 1 2 1 2 2 1 2 5 1 3 4 1 3 9 1 3 6 1 4 6 1 4 8 1 5 9 1 3 5 2 10 2 9 |
17 1 17 4 9 |
I. Yana so'rovlar?
Xotira: 256 MB, Vaqt: 5000 msSizga do'stingiz ta tugundan tashkil topgan daraxt bergan. Har bir tugunda sonlar yozilgan ya'ni -chi tugun uchun unda yozilgan son - , sizga ta so'rovga javob berishingiz kerak. Har bir so'rovda , va () berilgan. Aytaylik qanaqadir va tugunlar uchun ular orasidagi ma'sofani deb belgilab olaylik, sizni vazifangiz shunday lar yig'indisini topishingiz kerak sharti bajarilishi kerak. Rasmiy ravishda:
Birinchi qatorda ikkita natural sonlar va (, ) - Daraxtdagi tugunlar soni va so'rovlar soni.
Ikkinchi qatorda ta natural sondan tashkil topgan massiv ().
Keyingi ta qatorda daraxtni ikkita tugunlari va() - va ni bog'lab turuvchi yo'l.
Keyingi ta qatorda , va (, ). Agar oralig'ida qaysidir tugun yo'q bolsa u tugundagi qiymatini deb olib ketishingiz mumkin.
Har bir so'rovga javobni chiqaring.
Birinchi so'rovni illyustratsiyasi:

# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
9 5 1 2 4 8 16 32 64 128 256 3 5 1 7 4 5 4 6 2 4 1 8 5 8 1 9 1 2 3 2 4 4 3 2 2 4 1 5 1 1 4 |
28 1 136 503 510 |