A. A+B

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizga ikkita natural son beriladi. ularning yig‘indisini hisoblash kerak.

Kiruvchi ma'lumotlar:

Kirish oqimida ikkita butun son, \(A\) va \(B\) beriladi. Har ikkala son ham \(10^9\) dan kichik.

Chiquvchi ma'lumotlar:

Berilgan ikkita sonning yig‘indisini ekranga chiqaring.

Izoh:

Python dasturlash tilida ushbu masalani yechish uchun e'tibor bering: ikkita son bitta qatorda kiritiladi. Shu sababli, int(input()) buyrug‘idan foydalanish noto‘g‘ri bo‘lishi mumkin. Buning o‘rniga, quyidagi kodni ishlatishni tavsiya qilamiz:

a, b = map(int, input().split())

Bu buyruq ikkita sonni bitta qatordan o‘qib, ularni butun songa aylantiradi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 3
 
5

B. Katta-kichik

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sonlar ustida amallarning eng muximlaridan biri bu - taqqoslashdir. Ushbu masalada sizga qo'yilgan talab, ikkita butun sonni taqqoslash kerak bo'ladi.

Kiruvchi ma'lumotlar:

Kirish oqimida ikkita butun son \(A\) va \(B\) berilgan bo'ladi, va ularning absolyut qiymati \(2 \times 10^9\) dan kichik bo'ladi.

Chiquvchi ma'lumotlar:

Chiqarish oqimida bitta belgi chiqarish kerak. Agar \(A > B\) bo'lsa \(>\), agar \(A = B\) bo'lsa \(=\), yoki \(A < B\) bo'lganda \(<\) belgisini.

 

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
0 0
 
=
2 
34 43
 
<
3 
-34 -43
 
>

C. Ko'paytma

Xotira: 16 MB, Vaqt: 1000 ms
Masala

\(X, Y \in Z;\)
\(X \le Y;\)
\(X * Y = Z\)
shartlarini qanoatlantiruvchi \((X, Y)\) juftliklar sonini aniqlang!

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida yagona butun son, \(Z(-10^9 \le Z \le 10^9)\)  soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT faylida yagona son, yuqoridagi shartlarni qanoatlantiruvchi \((X,Y)\) juftliklar sonini chop eting, agar bunday juftliklar cheksiz bo'lsa \(-1\) chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
-2
 
2

D. ASCII

Xotira: 2 MB, Vaqt: 1000 ms
Masala

Sizga ASCII jadvalidan bitta belgi beriladi siz uning u jadvaldan nechanchi o'rinda turishini yoping.

Kiruvchi ma'lumotlar:

ASCII dagi belgilardan biri.

Chiquvchi ma'lumotlar:

Berilgan belgining nechanchi o'rinda turganligi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
a
 
97

E. Knight game

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Ali va Vali quyidagich o'yin o'ynashmoqda. \(n \times n\) shaxmat doskasi mavjud ular navbat bilan doskaga bittadan otni bir birini ura olmaydigan qilib joylashtiradilar. Oxirgi bo'lib otni joylashtirgan o'yinchi o'yinda g'olib bo'ladi. Ikkala o'yinchi ham optimal o'ynagan taqdirda kim g'olib bo'lishini aniqlang. O'yinni Ali boshlab beradi.

Kiruvchi ma'lumotlar:

Kirish faylida 1-qatorda \(T(1 \le T \le 1000)\) testlar soni. Keyingi T ta qatorda \(n(1 \le n \le 10^4)\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda, agar Ali yutsa 0 aks holda 1 ni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
2
1
 
1
0

F. Nuqta

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Dekard koordinatalar sistemasidagi \(A(A_x, A_y)\) va \(B(B_x, B_y)\) nuqtalarning koordinatalari berilgan.
Shu nuqtalardan hosil bo'lgan kesmaning A nuqtasini B nuqta atrofida soat strelkasi bo'ylab 180o burgandan keyingi A nuqtaning koordinatalarini aniqlang.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki qatorida bitta butun son, \(N (1 ≤ N ≤ 15)\) testlar soni kiritiladi.
Keyingi \(N\) ta qatorning har birida to'rttadan butun son, har bir test uchun \(A_x, A_y, B_x, B_y (-100 ≤ A_x, A_y, B_x, B_y ≤ 100)\) kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda ikkitadan butun son, A nuqtani B nuqta atrofida soat strelkasi bo'ylab 180o burgandan keyingi A nuqtaning koordinatalarini chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
0 0 2 2
1 1 2 2
 
4 4
3 3

G. Uy raqami

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Megatoy bitlandiyada istiqomat qiladi. Uning fikricha o’z uyining raqamiga uy raqamining oxirgi ikki xonasini qo’shganda hosil bo’ladigan son uning telefon raqamiga teng bo’lgandagina telefon raqami chiroyli hisoblanadi. Shuning uchun Megatoy o’zi chiroyli hisoblaydigan telefon raqami ishlatadi. Sizga Megatoyning telefon raqami beriladi, siz u qaysi xonadonda istiqomat qilishi mumkinligini aniqlang.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida bitta [100,999] oralig’idagi butun son, Megatoyning telefon raqami kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida Megatoy istiqomat qilishi mumkin bo’lgan uyning raqamini chiqaring. Agar bunday uylar bir nechta bo’lsa ularni bo’sh joy bilan ajratgan holda qiymati eng kichigidan kattasiga qarab tartiblab chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
202
 
151 201

H. Kinguru

Xotira: 16 MB, Vaqt: 1000 ms
Masala

To’g’ri chiziqda birinchi kinguruning boshlang’ich kordinatasi x1 va uning tezligi bir sakrashda v1 metr, ikkinchi kinguruning boshlang’ich kordinatasi x2 va uning tezligi bir sakrashda v2 metr. Ikkala kinguru ham bir sakrash uchun bir xil vaqt sarflaydi. Kingurular qaysidir vaqtda to’g’ri chiziqning bitta nuqtasida bo’lib qolishi yoki yo’qligini aniqlang.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida bitta qatorda to’rtta butun son, x1, v1, x2, v2 (0 ≤ x1 < x2 ≤ 10000, 1 ≤ v1, v2 ≤ 10000) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida, agar kingurular qaysidir vaqtda to’g’ri chiziqning bitta nuqtasida bo’lishsa YES aks holda NO so’zini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
0 3 4 2
 
YES
2 
0 2 5 3
 
NO

I. Shifrlash 1

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Siz juda maxfiy kompaniyada ishlaysiz va sizga bitta so'z va ushbu so'zning yozilishi shifrlangan holda yuborilgan xat kelgan. Ushbu kompaniyaning direktori ushbu kishiga xatni qaytarib yubormoqchi edi, shuning uchun sizning vazifangiz ushbu shifrlash usulini bilib olish va shifrlangan shaklda pochta yuborgan kishiga direktordan xabar yuborishdir.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining yagona qatorida lotin alifbosidagi kichik harflardan iborat bo’lgandirektorning xabari berilgan.

Chiquvchi ma'lumotlar:

Quyidagi naqsh bo'yicha shifrlangan xabarni chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
hello


5
1101000
1100101
1101100
1101100
1101111

J. Pentatop

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Azamjon Paskal uchburchaklari va tetraedral sonlarni urganish mobaynida Pentatop sonlar ketma ketligini topib oldi va uning umumiy hadi quyidagicha edi:

 \(PT_n  = \dbinom {n+3} {4}\)

Azamjon Pentatop sonlarni har bir hadini hisoblay olishi uchun siz unga yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylida yagona butun son \(n(1 ≤ N ≤ 10^{18})\) soni kiritiladi.

Chiquvchi ma'lumotlar:

\(PT_n\) ni \(10^9 + 7\) ga boʻlgandagi qoldigʻini chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
 
5

K. Birinchi bo'linuvchi

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizga \(a\) va \(b\) sonlari beriladi.

Siz \(a\) dan kichik bo’lmagan \(b\) ga bo’linuvchi birinchi sonni topishingiz kerak bo’ladi.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida yagona qatorda, \(a,b(1 ≤ a,b ≤ 10^{18})\) soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, masala yechimini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
32 17
 
34
2 
33 17
 
34

L. Password Random

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Quvonchbek robocontest.uz parolini o'zgartirishga qaror qildi, lekin u o'zi yangi parolni o'ylab topishga juda qiynaladi. Shuning uchun u sizga yordam so'rab murojaat qildi.

Quvonchbek ixtiro qilingan parol quyidagi shartlarga asosan tuzilgan bo'lishi kerak:

  • parol uzunligi n ga teng bo'lishi kerak.
  • parol faqat kichik lotin harflaridan iborat bo'lishi kerak.
  • paroldagi alohida belgilar soni k ga teng bo'lishi kerak.
  • paroldagi har qanday ketma-ket ikkita belgi boshqacha bo'lishi kerak.

Sizning vazifangiz Quvonchbekga yordam berish va unga tavsiflangan barcha shartlarga loyiq keladigan yangi parolni o'ylab topishdir. 

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita musbat butun son n va k\((2 \le n \le 100, 2 \le k \le min(n, 26))\) mavjud — parol uzunligi va undagi turli belgilar soni.

Tepadagi shartlarni bajaradigan parol har doyim mavjud.

Chiquvchi ma'lumotlar:

Quvonchbek barcha shartlariga javob beradigan har qanday parolni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 3
 
abca
2 
3 2
 
aba

M. Tartib

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizga \(A, B, C\) sonlari aralash tartibda berilgan. Sonlar aralash tartibda berilgani bilan sizga ma’lumkin \(A < B < C\) shart o’rinli. Shu uchchala sonni ko’rsatilgan tartibda chop eting:

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida uchta butun son, \(A, B, C (1 \le A, B, C \le 100)\) ning qiymatlari aralash tartibda beriladi. Keyingi satrda esa berilgan sonlarni qaysi tartibda chop etish kerakligi ko’rsatiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona satrda kirish ma’lumotlariga mos holda natijani chop eting

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 5 3
ABC
 
1 3 5

N. Kesishishlar soni

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizga n burchakli qavariq ko'p burchak berilgan. Uning dioganallari jami nechta nuqatada kesishishini toping.

Kiruvchi ma'lumotlar:

Kirish faylida yagona qatorda natural son n\((3 \le n \le 100)\) kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona qatorda masala javobini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
 
5

O. IP Adres

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Internet va lokal tarmog'idagi qurilmalar bir-biri bilan IP protokoli orqali bir-birini IP adreslariga ma'lumot junatish orqali aloqa qilishadi. IP adresda 4ta son nuqlatar bilan bo’lingan bo’ladi va sonlar qiymati 255dan oshmaydi. Misol uchun:

  1. 127.0.0.0
  2. 192.168.0.01
  3. 255.000.255.0255

Sizning vazifangiz berilgan IP adres to'g'riligini aniqlashdan iborat

Kiruvchi ma'lumotlar:

Kirish faylida bitta qatorda nuqtalar bilan bo’lingan 4ta son beriladi, va sonlarning qiymati 106 dan oshmaydi.

Chiquvchi ma'lumotlar:

Agar kiritilgan ma’lumot IP adres bo’la olsa “YES”, aks holda “NO” so’zlarini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
192.168.0.01
 
YES
2 
098.1342.23.31
 
NO

P. Kutubxona

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Mirzo Ulug’bek kitob o’qishni judayam yaxshi ko’radi, shuning uchun u har doim shahar kutubxonasidan ma’lum muhlatda qaytarib berish evaziga kitoblarni olib o’qib turadi. Kitobxonlar kitoblarni kechiktirmasdan olib kelishlari uchun kutubxonaga kitob muhlatidan keyin qaytarilsa quyidagi shaklda jarimaga tortiladi:

  • Agar kitob o’z muhlatida, yoki undan ertaroq qaytarilgan bo’lsa jarima miqdori 0 ga teng.
  • Agar kitob belgilangan muhlatdagi yil va oyda qaytarilsayu kun bo’yicha kechiktirilsa har bir kechiktirilgan kun uchun 15 dinordan jarima hisoblanadi.
  • Agar kitob kelishilgan yilda qaytarilsayu oy bo’yicha kechikkan bo’lsa har bir kechikkan oy uchun 500 dinordan jarima hisoblanadi
  • Agar kitob kelishilgan yildan kechiktirilgan holda qaytarilsa jami 10000 dinor jarima hisoblanadi.

Masalan kitob 2020-yilning 1-yanvarida qaytarilishi kerak bo’lsa, yoki 2020-yilning 31-dekabrida qaytarilishi kerak bo’lsa ammo kitob 2021-yilning 1-yanvarida qaytarilsa kechikish yil bo’yicha hisoblanadi va jami 10000 dinor jarima hisoblanadi.

Mirzo Ulug’bek kitobni kutubxonaga topshirganida unga necha dinor miqdorida jarima hisoblanishini aniqlang.

Kiruvchi ma'lumotlar:

Dastlabki satrda 3 ta butun son, \(k_1, o_1, y_1\) – kitob kutubxonaga qaytarilgan kun, oy, yil ni ifodalaydi.

Keyingi qatorda 3 ta butun son, \(k_2, o_2, y_2\) – kitob kutubxonaga qaytarilishi belgilangan kun, oy, yil ni ifodalaydi.

\(1 ≤ k_1, k_2 ≤ 31\)
\(1 ≤ o_1, o_2 ≤ 12\)
\(1 ≤ y_1, y_2 ≤ 3000\)

Sanalar Grigorian kalendariga mos kelishi kafolotlanadi.

Chiquvchi ma'lumotlar:

Mirzo Ulug’bek necha dinor jarimaga tortilishini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
6 6 2020
9 6 2021
 
0
2 
9 6 2020
6 6 2020
 
45

Q. Paskal uchburchagi #2

Xotira: 16 MB, Vaqt: 500 ms
Masala

Paskal uchburchagi haqida yetarlicha ma'lumot olgan bo'lsangiz, endigi ishingiz paskal uchburchagining dastlabki \(n\)-gacha bo'lgan qavatlari elementlarini \(10^9+7\)ga bo'lgandagi qoldiqni bosh joy bilan ajratilgan holda chop eting. (Qavatlarni indexlash 0 dan boshlanadi)

Kiruvchi ma'lumotlar:

\(0 \le n \le 333\) butun soni.

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1
 
1
1 1
2 
5
 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

R. Karta

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Suhrobjon pullarini kartada saqlaydi. U uyida kuniga qancha vaqt chiroq ishlatsa, shunga qarab bank uning hisobidan pul yechib oladi. Ammo uning baxtiga agar bir nechta chiroqlar bir vaqtda yonib turgan taqdirda ham, bittasi yonib tursa qancha olsa, shuncha miqdor talab qilinadi. Bugun uning N so'm puli bor. Suhrobjon ertaga ertalab turib kartasiga qaraganda qancha puli qolganini ko'radi!?

Kiruvchi ma'lumotlar:

Birinchi qatorda N, S va M mos ravishta kartadagi puli (so'mda), Har bir daqiqa uchun ketadigan pul (so'mda) va ishlatilgan chiroqlar soni. (1 ≤ N ≤109 , 1 ≤ S ≤ 103, 1 ≤ M ≤10)

Keyingi M ta qatorda har bir chiroqning qachondan qachongacha ishlatilgani beriladi(masalan 12:00-13:30)

Chiquvchi ma'lumotlar:

Yagona qatorda masalaning javobini chop eting!

Izoh:

Karta hech qachon minusga chiqmasligini inobatga oling.Agar mablag' yetarli bo'lmasa Kartada bor pulni yechib oladi!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
120 1 2
12:00-13:30
12:30-13:30
 
30

S. Farqlar ketma-ketligi

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Dilnura maktabda endi qo’shish va ayirishni o’rgandi. Kunlardan bir kun u maktabga o’qituvchi va boshqa bolalardan ertaroq borib qolganida doskada \(N\) ta son bitta qatorda yozilganligini ko’rdi. U o’rgangan bilimlarini mustahkamlash maqsadida doskaga yozilgan sonlar ketma-ketligidan har yonma-yon joylashgan sonlarning farq (kattasidan kichigini ayirilgan qiymat)ini hisoblamoqchi bo’ldi. U barcha yonma-yon joylashgan sonlar uchun ularning farqini bir qator qilib yozib chiqdi, so’ngra dastlabki sonlar qatorini doskadan o’chirdi. Shundan so’ng doskada jami \(N-1\) ta son qoldi, ya’ni Dilnura hisoblagan yonma-yon sonlar farqi doskada qoldi. U shu ishini doskada bitta son qolguniga qadar davom ettirdi.

Siz doskada qolgan sonning qiymatini aniqlang.

 

Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida bitta butun son, \(N\)(\(2 \le N \le 2000\)) soni kiritiladi, keyingi qatorda qiymati \([0,10^9]\) oralig’idagi \(N\) ta butun son, ya’ni doskada yozilgan sonlar ketma-ketligi kiritiladi.

 

Chiquvchi ma'lumotlar:

Chiqish oqimida yagona butun son, doskada qolib ketgan sonni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
3 1 4 1
 
1
2 
2
2 4
 
2
3 
6
2 7 5 3 3 11
 
3

T. Omonat

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Azimjon va Davlatbek 2022 yili robocontest.uz tomonidan o'tkazilgan olimpiadada n dollardan pul mukofoti yutib olishdi. Endi shu pullarni ular bankka qo'yib ko'paytirishmoqchi. Azimjon pullarini Davr bankka qo'ydi, Davr bankda pullaringizni qo'yganingizdan so'ng har juft sonli yilda jami pullaringizga a dollar qo'shiladi, har toq sonli yilda esa jami pullaringiz ikki barobar oshadi.
Davlatbek o'zining pullarini Anor bankka qo'ydi. Anor bankda pullaringizni qo'yganingizdan so'ng har toq sonli yilda jami pullaringizga a dollar qo'shiladi, har juft sonli yilda esa jami pullaringiz ikki barobar oshadi.

Sizning vazifangiz m yildan so'ng kimning pullari ko'p bo'lganini aniqlash.

Kiruvchi ma'lumotlar:

Bitta qatorda n, a va m natural sonlari.

(1 <= n,a,m <= 10)

Chiquvchi ma'lumotlar:

Bitta qatorda m yildan keyin puli ko'payib ketgan odamning jami pulini, agar pullari teng bo'lsa ixtiyoriy odamning jami pullarini chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 1 1
 
2
2 
2 2 2
 
8

U. Kuzatuv kamerasi

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Baytlandiya mamlakati bir o’lchovli kesmada joylashgan. Unda jami N ta xonadon mavjud. Har bir xonadon sonlar o’qidan qaysidir bir koordinatada joylashgan. Baytlandiya qiroli o’z davlatidagi barcha xonadonni kuzatib turish uchun mamlakat bo’ylab kameralar o’rnatishga qaror qildi. Har bir kamera mamlakatdagi qaysidir bir xonadonning tomiga o’rnatiladi, va o’rnatilgan koordinatasidan turib K masofani kuzata oladi. Mamlakatdagi barcha xonadonni kuzata olishi uchun Baytlandiya qiroliga eng kamida nechta kamera kerak bo’lishini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida ikkita butun son, N va K (1 ≤ N, K ≤ 105) sonlari kiritiladi. Ikkinchi satrida N ta [1, 105] oralig’idagi butun son, har bir xonadon joylashgan koordinata kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, mamlakatdagi barcha xonadonni kuzata olishi uchun Baytlandiya qiroliga eng kamida nechta kamera kerakligini chop eting.

Izoh:

1-test:

k-nearest(2).png

2-test:

k-nearest2(2).png

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 1
1 2 3 4 5
 
2
2 
8 2
7 2 4 6 5 9 12 11
 
3

V. Naqshlar

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizda \(N \times M\) katakchalardan iborat maydon bor, bu maydonda ba’zi  katakchalar kulrang rangda bo’yalgan va qolgan katakchalar bo’sh. Siz shu bo’sh kataklarni quyidagi 9 turdagi naqshlardan xoxlaganingizcha foydalanib to’ldirishingiz kerak:

Yagona shart naqshlarni burish mumkin emas, ya’ni 3-turdagi naqshni burgan holda 4-turdagi naqsh shaklini hosil qilib bo’lmaydi. 

Misol uchun quyidagi \(4 \times 3\) maydonni 6 xil usulda naqshlar bilan to’ldirish mumkin:

Sizga \(N \times M\) maydonning dastlabki holati berilgan, siz bu maydonga naqshlarni necha xil usulda joylashtirib to’ldirish mumkinligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkida butun son, \(N(1 \leq N \leq 40)\)va \(M(1 \leq M \leq 8)\) sonlari berilgan. Keyingi \(N\) ta satrda \(M\)  ta butun son, 0 yoki 1 sonlari kiritiladi, bunda 0 bo’sh katakchani, 1 esa kulrang katakchani ifodalaydi.

Chiquvchi ma'lumotlar:

Chiqish faylining yagona satrida bitta butun son, berilgan maydonga naqshlarni necha xil usulda joylashtirib to’ldirish mumkinligini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 3
1 0 0
0 0 1
0 0 1
1 1 1
 
6
2 
2 2
0 0
0 0
 
4
3 
1 8
0 0 0 0 0 0 0 0
 
1

W. Persistent Segment Tree (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Ushbu masalada massivlar soni ko'payib boradi.

Sizga dastlab N va Q mos ravishda N ta elementdan iborat A massiv uzunligi va shu massiv ustida amalga oshiriladigan Q ta so'rovlar soni beriladi, quyidagi so'rovlarning 3-turida massiv yana bittaga ko'payadi.

Sizning vazifangiz quyidagi so'rovlarga javob beruvchi ma'lumotlari tuzilmasini tuzish albatta o'z o'rnida har bir 2-turdagi so'rovga javob qaytarish:

  • 1 ID X Y bu so'rovda siz ID-massivning X-elementini Y ga o'zgartirishing
  • 2 ID L R bu so'rovda siz ID-massivning [L, R] oraliqdagi elementlari yig'indisini chiqarish
  • 3 ID bu so'rovda siz ID-massivda yana bir nusxa oling shunda sizning massivlaringiz soni yana bittaga ko'payadi
Kiruvchi ma'lumotlar:

 Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (1 ≤ A[i] ≤ 10^9)\) sonlari.

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 2 * 10^5\)
\(1 ≤ A[i], Y ≤ 10^9\)
\(1 ≤ L ≤ R, X ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda 2-turdagi so'rovlar uchun mos javobni chiqaring

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 15
1 2 3
3 1
3 2
3 3
3 4
1 1 1 5
1 2 1 50
1 3 1 500
1 4 1 5000
1 5 1 50000
2 1 1 3
2 2 1 3
2 3 1 3
2 4 1 3
2 5 1 3
3 5
 
10
55
505
5005
50005

X. Oraliqga qo'shish va o'zgartirish (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov berilgan, so'rovlar quyidagicha:

  1. \(L \space R \space X\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlarga \(X\) sonini qo'shish
  2. \(L \space R \space X\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlar qiymatini \(X\) soniga tenglashtirish
  3. \(L \space R\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlar yig'indisini chiqarish
Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (1 ≤ A[i] ≤ 10^6)\) sonlari

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:

\(1 ≤ N, Q ≤ 2 * 10^5\)
\(1 ≤ A[i], X ≤ 10^6\)
\(1 ≤ L ≤ R ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir 3-turdagi so'rov uchun berilgan \([L, R]\) oraliqdagi massiv elementlari yig'indisini chiqaring!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 3
1 2 3
1 1 2 3
2 2 3 1
3 1 3
 
6

Y. Snake game

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Eski telefonlarda "Iloncha" oyinini o'ynaganmisiz? Agar o'ynamagan bo'lsangiz hozir sizga o'yin qoidalarini tanishtiraman.
1. Dastlab iloncha 1 birlik uzunlikka ega bo'ladi.
2. Har bir yeyilgan olmachalar uchun uning uzunligi 1 birlikka oshib boradi.
3. Yangi qo'shiladigan ilonchaning bo'lagi, uning oxirgi bo'lagining harakat yo'nalishiga mos ravishta va shu bo'lak ketidan joy oladi.
4. Iloncha yo'lida to'siq bo'lmagan hollarda o'ngga, chapga, yuqoriga va pastga harakat qila oladi.
Iloncha o'yini \(8 \times 8\) maydonida bo'ladi va iloncha \(1 \times 1\) katakchadan o’yinni boshlaydi. Sizga mos ravishta ketma-ket paydo bo'luvchi N ta olmachalarning kordinatalari beriladi. Ilonchaning vasifangiz barcha olmachalarni yeb bitirish, ammo buning uchun ilonchaning boshi eng kam masofani bosib o’tishi kerak bo'ladi. (Ilonchaning tanasi va maydonning chetki qismlari to'siqlar hisoblanadi)

Kiruvchi ma'lumotlar:

Birinchi qatorda olmachalar soni \(N\). Keyingi \(N\) ta qatorda esa ketma-ket paydo bo'luvchi olmachalarning kordinatalari \(x_i​,y_i\)​. \((1 \le N \le 10, 1 \le x_i​,y_i​ \le 8)\)

Chiquvchi ma'lumotlar:

Barcha olmachalarni yeyish uchun ilonchaning boshi sarflaydigan eng qisqa yo'lning uzunligini toping. (masala yechimga ega ekanligi kafolatlanadi.)

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
1 8
8 8
8 1
 
21
2 
2
8 1
2 1
 
15
3 
2
2 1
8 1
 
7

Z. Labirint

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga UTF-16 belgilaridan hosil qilingan labirint beriladi. Siz labirintning \(A\) nuqtasidan \(B\) nuqtasiga olib boradigan yo’lni chizishingiz kerak bo’ladi. Labiring o’z ichiga \(N×M\) yacheykani qamrab oladi va misollarda ko’rsatilgandek ifodalanadi. Har bir yacheykani ifodalash uchun balandligiga 1 ta belgi, eniga 3 ta belgidan foydalanilgan. Labirintda siz quyidagi belgilardan foydalanishingiz mumkin:

№

belgi

UTF-16

1

SPACE

0x0020

2

─

0x2500

3

│

0x2502

4

┌

0x250C

5

┐

0x2510

6

└

0x2514

7

┘

0x2518

8

├

0x251C

9

┤

0x2524

10

┬

0x252C

11

┴

0x2534

12

┼

0x253C

13

╴

0x2574

14

╵

0x2575

15

╶

0x2576

16

╷

0x2577

 

Siz labirintda \(A\) nuqtadan \(B\) nuqtaga borish yo’lini misollarda ko’rsatilgandek ifodalang. \(A\) nuqtadan chiqish va \(B\) nuqtaga yetib borishda siz faqatgina №13, №14, №15, №16 dagi belgilardan foydalanishingiz mumkin.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son, \(N(0 < N < 50)\) va \(M(0 < M < 100)\) mos ravishda labirintning qatorlar soni va ustunlar soni kiritiladi. Keyingi \(2×N+1\) qatorda \(4×M+1\) tadan UTF-16 belgilari berilib labirint tasvirlanadi. Labirintning chekka qismi har doim yopiq hisoblanadi. \(A\) va \(B\) belgilar labirintning \(N×M\) yacheykalarining ixtiyoriy birida yacheyka markazida joylashganligi kafolotlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida labirintda \(A\) nuqtadan \(B\) nuqtaga boradigan yo’lni misollarda ko’rsatilgan shaklda tasvirlang.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
8 8
┌───┬───────────────────┬───────┐
│ A │                   │       │
│   ╵   ┌───────────┐   ├───╴   │
│       │           │   │       │
├───────┴───────╴   │   ╵   ╷   │
│                   │       │   │
│   ╷   ┌───────┐   ├───────┤   │
│   │   │     B │   │       │   │
├───┘   │   ╶───┤   │   ╷   │   │
│       │       │   │   │   │   │
│   ╶───┴───┐   ╵   └───┘   │   │
│           │               │   │
│   ╶───┐   ├───────────────┘   │
│       │   │                   │
├───╴   │   ╵   ╶───────────────┤
│       │                       │
└───────┴───────────────────────┘
 
┌───┬───────────────────┬───────┐
│ A │ ┌───────────────┐ │       │
│ ╷ ╵ │ ┌───────────┐ │ ├───╴   │
│ └───┘ │           │ │ │ ┌───┐ │
├───────┴───────╴   │ │ ╵ │ ╷ │ │
│     ┌───────────┐ │ └───┘ │ │ │
│   ╷ │ ┌───────┐ │ ├───────┤ │ │
│   │ │ │ ┌─╴ B │ │ │       │ │ │
├───┘ │ │ │ ╶───┤ │ │   ╷   │ │ │
│ ┌───┘ │ └───┐ │ │ │   │   │ │ │
│ │ ╶───┴───┐ │ ╵ │ └───┘   │ │ │
│ └───────┐ │ └───┘         │ │ │
│   ╶───┐ │ ├───────────────┘ │ │
│       │ │ │ ┌───────────────┘ │
├───╴   │ │ ╵ │ ╶───────────────┤
│       │ └───┘                 │
└───────┴───────────────────────┘
2 
8 8
┌───┬───────────────────┬───────┐
│ A │                   │       │
│   ╵   ┌───────────┐   ├───╴   │
│       │           │   │       │
├───────┴───────╴   │   ╵   ╷   │
│                   │       │   │
│   ╷   ┌───────┐   ├───────┤   │
│   │   │       │   │       │   │
├───┘   │   ╶───┤   │   ╷   │   │
│       │       │   │   │   │   │
│   ╶───┴───┐   ╵   └───┘   │   │
│           │               │   │
│   ╶───┐   ├───────────────┘   │
│       │   │                   │
├───╴   │   ╵   ╶───────────────┤
│       │                     B │
└───────┴───────────────────────┘
 
┌───┬───────────────────┬───────┐
│ A │ ┌───────────────┐ │       │
│ ╷ ╵ │ ┌───────────┐ │ ├───╴   │
│ └───┘ │           │ │ │ ┌───┐ │
├───────┴───────╴   │ │ ╵ │ ╷ │ │
│                   │ └───┘ │ │ │
│   ╷   ┌───────┐   ├───────┤ │ │
│   │   │       │   │       │ │ │
├───┘   │   ╶───┤   │   ╷   │ │ │
│       │       │   │   │   │ │ │
│   ╶───┴───┐   ╵   └───┘   │ │ │
│           │               │ │ │
│   ╶───┐   ├───────────────┘ │ │
│       │   │ ┌───────────────┘ │
├───╴   │   ╵ │ ╶───────────────┤
│       │     └─────────────╴ B │
└───────┴───────────────────────┘
3 
4 3
┌───────┬───┐
│ B     │   │
├───╴   │   │
│       │   │
│   ┌───┘   │
│   │ A     │
│   └───╴   │
│           │
└───────────┘
 
┌───────┬───┐
│ B ╶─┐ │   │
├───╴ │ │   │
│ ┌───┘ │   │
│ │ ┌───┘   │
│ │ │ A ╶─┐ │
│ │ └───╴ │ │
│ └───────┘ │
└───────────┘
4 
13 8
┌───┬───────┬───────────┬───────┐
│   │       │           │       │
│   ╵   ╷   │   ┌───╴   │   ╷   │
│       │   │   │       │   │   │
├───────┤   ╵   │   ╶───┤   │   │
│       │       │       │   │   │
│   ╷   └───────┴───┐   ╵   │   │
│   │     A         │       │   │
│   ├───────┬───┐   └───────┤   │
│   │       │   │           │   │
│   ╵   ╷   ╵   │   ╶───────┤   │
│       │       │           │   │
├───────┴───┐   ├───────┐   ╵   │
│           │   │       │       │
│   ╶───┐   │   └───╴   ├───────┤
│       │   │           │       │
│   ╷   │   ├───────┐   ╵   ╷   │
│   │   │   │ B     │       │   │
│   │   │   ╵   ┌───┴───────┤   │
│   │   │       │           │   │
├───┘   ├───────┘   ╷   ╶───┘   │
│       │           │           │
│   ╶───┤   ┌───────┴───────┬───┤
│       │   │               │   │
│   ╷   ╵   └───────╴   ╷   ╵   │
│   │                   │       │
└───┴───────────────────┴───────┘
 
┌───┬───────┬───────────┬───────┐
│   │       │           │       │
│   ╵   ╷   │   ┌───╴   │   ╷   │
│       │   │   │       │   │   │
├───────┤   ╵   │   ╶───┤   │   │
│ ┌───┐ │       │       │   │   │
│ │ ╷ │ └───────┴───┐   ╵   │   │
│ │ │ └─╴ A         │       │   │
│ │ ├───────┬───┐   └───────┤   │
│ │ │ ┌───┐ │   │           │   │
│ │ ╵ │ ╷ │ ╵   │   ╶───────┤   │
│ └───┘ │ └───┐ │           │   │
├───────┴───┐ │ ├───────┐   ╵   │
│ ┌───────┐ │ │ │       │       │
│ │ ╶───┐ │ │ │ └───╴   ├───────┤
│ └───┐ │ │ │ └───────┐ │ ┌───┐ │
│   ╷ │ │ │ ├───────┐ │ ╵ │ ╷ │ │
│   │ │ │ │ │ B     │ └───┘ │ │ │
│   │ │ │ │ ╵ ╷ ┌───┴───────┤ │ │
│   │ │ │ └───┘ │ ┌───┐     │ │ │
├───┘ │ ├───────┘ │ ╷ │ ╶───┘ │ │
│ ┌───┘ │ ┌───────┘ │ └───────┘ │
│ │ ╶───┤ │ ┌───────┴───────┬───┤
│ └───┐ │ │ │               │   │
│   ╷ │ ╵ │ └───────╴   ╷   ╵   │
│   │ └───┘             │       │
└───┴───────────────────┴───────┘

AA. Kadane (so'rovli) (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov beriladi, har bir so'rovda massivning \(K\)-elementi qiymati \(X\) ga o'zgaradi.

Sizning vazifangiz o'zgargan massivdan eng katta yig'indiga ega qism massiv topish (bu turdagi masalani eng tez yechib beruvchi algoritm nomi: Kadane) !

Siz qism massiv summasini chop eting

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.
Keyingi qatorda \(N\) ta butun \(A[i] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.
Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 2 * 10^5\)
\(-10^9 ≤ A[i], X ≤ 10^9\)
\(1 ≤ K ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir so'rovdan keyin massivda eng katta Kadane qiymatini chiqarish!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 1
1
1 10
 
10

AB. Super chiptalar

Xotira: 128 MB, Vaqt: 2500 ms
Masala

Shermatning tug’ilgan kunida unga avtobus uchun chiptalar sovg’a qilishdi. Shermat boshida ozroq xafa bo’lgandi, lekin chiptalar oddiy emas balki super chiptalar ekanligini ko’rganidan keyin ancha taskin topdi.

Hozirda uning qo’lida \(m\) ta chipta bor va chiptalar 3 xil turga bo’linadi:
1. Bu chipta orqali \(a\) bekatdan \(b\) bekatgacha borsa bo’ladi.
2. Bu chipta orqali \(a\) bekatdan \([l,r]\) oraliqdagi ixtiyoriy bekatga borsa bo’ladi.
3. Bu chipta orqali esa \([l,r]\) oraliqdagi ixtiyoriy bekatdan \(a\) bekatga borsa bo’ladi.

Har bir chipta uchun avtobus qancha vaqt harakatlanishi ko’rsatilgan. Bekatlar soni jami \(n\) ta bo’lib, dastlab Shermat \(s\) - bekatda turibdi. Shermat \(s\) - bekatdan qolgan bekatlarga eng kamida qancha vaqt sarflab yetib olish mumkinligiga qiziqmoqda. Shaharda avtobus reyslari shunchalik ko’pki bekatdan bir avtobusdan tushib boshqasiga o’tirishga ketgan vaqtni 0 deb hisoblash mumkin.

Kiruvchi ma'lumotlar:

Birinchi qatorda 3 ta butun son - \(n\), \(m\), va \(s\) – bekatlar soni, chiptalar soni va Shermat turgan bekat beriladi \((1 ≤ n, m ≤ 10^5, 1 ≤ s ≤ n)\). Keyingi \(m\) ta qatorda chiptalar tavsifi kiritiladi va ular quyidagicha ifodalanadi:

  • \(1 \space a \space b \space t\) - bu birinchi turli chipta bo'lib, bu chipta orqali \(a\) bekatdan \(b\) bekatga \(t\) vaqtda borish mumkin.
  • \(2 \space a \space l \space r \space t\) - bu ikkinchi turli chipta bo'lib, bu chipta orqali \(a\) bekatdan \([l, r]\) oraliqdagi ixtiyoriy bekatga \(t\) vaqtda borish mumkin.
  • \(3 \space a \space l \space r \space t\) - bu uchinchi turli chipta bo'lib, bu chipta orqali \([l, r]\) oraliqdagi ixtiyoriy bekatdan \(a\) bekatga \(t\) vaqtda borish mumkin.
Chiquvchi ma'lumotlar:

Yagona qatorda probel bilan ajratilgan \(n\) ta sonni chiqaring, \(i\) - son \(s\) bekatdan \(i\) - bekatgacha borish mumkin bo'lgan eng qisqa vaqtga teng bo'lsin, agar borishni iloji yo'q bo'lsa \(-1\) chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17

0 28 12

AC. Prefix yig'indi (so'rovli) (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov berilad, so'rovlar quyidagicha:

  • 1 \(K\) \(X\) turdagi so'rovda \(K\)-o'rindagi massiv elementini \(X\) ga almashtirish
  • 2 \(L\) \(R\) turdagi so'rovda berilgan oraliqdagi eng katta prefix summani topish
Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 2 * 10^5\)
\(-10^9 ≤ A[i], X ≤ 10^9\)
\(1 ≤ L ≤ R, K ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda 2-turdagi so'rovlar uchun mos javobni chiqaring

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 1
1
2 1 1
 
1
Kitob yaratilingan sana: 28-Oct-25 23:05