A. To'rtburchak

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Alibek tekislikda tomonlari koordinata o'qlariga parallel bo'lgan to'g'ri burchakli to'rtburchak chizmoqchi. Buning uchun u allaqachon to'rtburchakning uchta qirrasini tanladi. Unga to'rtburchakning to'rtinchi nuqtasini tanlashda yordam bering!

Kiruvchi ma'lumotlar:

Kirish faylida uchta qatorda qiymati [1,1000] orasidagi ikkitadan butun son, to'rtburchakning tanlangan uchta koordinatalari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylining yagona satrida, bo'sh joy bilan ajratilgan holda ikkita butun son, to'g'ru burchakli to'rtburchakning to'rtinchi nuqtasi koordinatasini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 5
5 7
7 5
 
7 7
2 
30 20
10 10
10 20
 
30 10

B. Yangi yerni tozalash

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Doniyor uy qurish uchun yer sotib olishni xohlaydi. U hozirgacha bir nechta yer maydonlarini ko'rdi. Har biri to'rtburchak shaklida bo'lib, N qator va M ustundan iborat matritsani tashkil qiladi.

Doniyor yerning barcha qismlarini o'rib chiqishi kerak. Buni bajarish uchun u o't o'rish mashinasidan foydalanadi. U har qanday maydondan o'rimni boshlashi va asosiy yo'nalishlardan biriga qarab harakat qilishi mumkin (yuqoriga, pastga, chapga yoki o'ngga). Mashina faqat oldinga (qo'shni maydonlarga) harakatlanishi yoki 90 graduslik burilish qilishi mumkin.

Maqsad - mashinani minimal burilishlar bilan harakatlantirib, yerning barcha qismlarini o'rish.

Kiruvchi ma'lumotlar:

Birinchi qatorda K musbat butun soni keltirilgan. Keyingi K qatorning har birida N va M musbat butun sonlari beriladi.

\(1 \le K \le 5 \times 10^4\)

\(1 \le N, M \le 10^6\)

Chiquvchi ma'lumotlar:

Har bir maydon uchun minimal burilishlar sonini alohida qatorga chop eting.

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

C. So'zlarni topish

Xotira: 128 MB, Vaqt: 2000 ms
Masala

Ali va Vali so'z o'yinini o'ynashmoqda. Ali bir harf aytadi, Vali esa o'sha harf bilan boshlanadigan so'zni aytadi. Biroq, so'z ruxsat etilgan so'zlar ro'yxati ichida bo'lishi kerak va Vali uni eng kam marta aytgan bo'lishi kerak. Agar bir nechta variant mavjud bo'lsa, Vali leksikografik eng kichigini tanlaydi. Har bir Ali tomonidan aytilgan harf uchun, Vali so'z topa oladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita musbat butun sonlar K va N berilgan. Keyingi K qatorda kichik lotin harflaridan iborat, uzunligi 21 ta belgidan oshmaydigan so'zlar beriladi. Keyingi N qatorning har birida kichik lotin harflaridan iborat bitta harf keltiriladi.

\(1 \le K, N \le 10^5\)

Chiquvchi ma'lumotlar:

Siz N qatorda, har birida shartga mos keladigan bitta so'zni chop etishingiz kerak.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 5
toshkent
samarqand
sirdaryo
termiz
t
s
s
t
t
 
termiz
samarqand
sirdaryo
toshkent
termiz
2 
5 3
andijon
fargona
qarshi
termiz
urganch
q
f
a
 
qarshi
fargona
andijon
3 
1 3
xorazm
x
x
x
 
xorazm
xorazm
xorazm

D. Muammoli parollar

Xotira: 64 MB, Vaqt: 1000 ms
Masala

So'nggi paytlarda "HUMO" ijtimoiy tarmog'ida foydalanuvchi ma'lumotlarining o'g'irlanishi kuzatildi. Maxfiy ma'lumotlar orasida barcha foydalanuvchilarning parollari mavjud.
So'nggi paytlarda kompyuter xavfsizligini o'rganayotgan yosh talaba Begzod ijtimoiy tarmoq bilan tajriba o'tkazar ekan, u yana bir xavfsizlik buzilishini topdi! Haqiqiy parolga teng qism satrni o'z ichiga olgan har qanday satrni kiritganingizda, kirish muvaffaqiyatli bo'ladi. Misol uchun, agar paroli abc bo'lgan foydalanuvchi abc, abcd yoki imaabcnema qatorlaridan birini kiritsa, tizim unga muvaffaqiyatli kiradi, axbc uchun esa tizimga kirish muvaffaqiyatsiz bo'ladi.
Begzod, foydalanuvchi o'z parolidan foydalangan holda, ikkinchi foydalanuvchi sifatida tizimga kirishi mumkin bo'lgan turli xil foydalanuvchilarning qancha juftliklari mavjudligini bilmoqchi.

Kiruvchi ma'lumotlar:

Birinchi qatorda N - foydalanuvchilar soni kiritiladi.

Keyingi N ta qatorning har birida bittadan satr - har bir foydalanuvchining paroli kiritiladi. Parol lotin alifbosining kichik harflaridan tashkil topgan va uzunligi [1, 10] oralig'ida bo'ladi.

\(1 \le N \le 20\ 000\)

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
abb
aaa
aa
 
1
2 
3
x
xy
x
 
4

E. Super Mario (oson)

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Ushbu masalada oson va qiyin darajaning farqi N ning chegarasida, Oson holati uchun \(N \le 20\)

 

Hech o'zingizni kompyuter o'yinidagi bosh qahramon sifatida tush ko'rganmisiz? Ushbu hikoyaning qahramoni Alisher hozir aynan shunday tushni ko'rmoqda.

Alisherning tushidagi olam chapdan o'ngga ketma-ket joylashgan N ta osmono'par binolardan iborat. Har bir binoning balandligi \(H_i\)​ va tomida \(G_i\)​ oltin tangalar soni bor.

O'yin Alisherning istalgan binoga sakrashi bilan boshlanadi va bir nechta qadamdan iborat bo'ladi. Har bir qadamda Alisher o'zi turgan binodan o'ng tomonga (bir yoki bir nechta binolarni sakrab o'tib) undan baland yoki teng balandlikdagi binoga sakrashi mumkin. Har safar u binoga chiqqanda, u tomdagi barcha oltin tangalarni yig'adi.

Alisher o'yinni istalgan vaqtda to'xtatishi mumkin, ammo keyingi bosqichga o'tish uchun u kamida K tanga yig'ishi kerak.

Alisherga o'yinni o'tkazishning nechta turli yo'li borligini aniqlashda yordam bering. Agar biror binoni bir o'yinda tashrif qilgan bo'lsa, ikkinchisida tashrif qilmagan bo'lsa, ikkita o'yin bir-biridan farq qiladi

Kiruvchi ma'lumotlar:

Birinchi qatorda N va K musbat butun sonlari beriladi. Keyingi N qatorda har biri ikkita musbat butun son \(H_i\)​ (binoning balandligi) va \(G_i\)​ (tomdagi oltin tangalar soni) kiritiladi.

\(1 \le N \le 20\)

\(1 \le K \le 4 \times 10^{10}\)

\(1 \le H_i, G_i \le 10^9\)

Chiquvchi ma'lumotlar:

Alisher o'yinni turli yo'llar bilan o'tkazishi mumkin bo'lgan usullar sonini chop eting.

Izoh:

Ikkinchi test holatida quyidagi uchta o'yin Alisherni keyingi bosqichga o'tkazadi: {1, 2, 3}, {1, 4}, va {4}.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 15
5 5
5 12
6 10
2 1
 
4
2 
4 6
2 1
6 3
7 2
5 6
 
3
3 
2 7
4 6
3 5
 
0

F. Super Mario (qiyin)

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Ushbu masalada oson va qiyin darajaning farqi N ning chegarasida, Qiyin holati uchun \(N \le 40\)

 

Hech o'zingizni kompyuter o'yinidagi bosh qahramon sifatida tush ko'rganmisiz? Ushbu hikoyaning qahramoni Alisher hozir aynan shunday tushni ko'rmoqda.

Alisherning tushidagi olam chapdan o'ngga ketma-ket joylashgan N ta osmono'par binolardan iborat. Har bir binoning balandligi \(H_i\)​ va tomida \(G_i\)​ oltin tangalar soni bor.

O'yin Alisherning istalgan binoga sakrashi bilan boshlanadi va bir nechta qadamdan iborat bo'ladi. Har bir qadamda Alisher o'zi turgan binodan o'ng tomonga (bir yoki bir nechta binolarni sakrab o'tib) undan baland yoki teng balandlikdagi binoga sakrashi mumkin. Har safar u binoga chiqqanda, u tomdagi barcha oltin tangalarni yig'adi.

Alisher o'yinni istalgan vaqtda to'xtatishi mumkin, ammo keyingi bosqichga o'tish uchun u kamida K tanga yig'ishi kerak.

Alisherga o'yinni o'tkazishning nechta turli yo'li borligini aniqlashda yordam bering. Agar biror binoni bir o'yinda tashrif qilgan bo'lsa, ikkinchisida tashrif qilmagan bo'lsa, ikkita o'yin bir-biridan farq qiladi

Kiruvchi ma'lumotlar:

Birinchi qatorda N va K musbat butun sonlari beriladi. Keyingi N qatorda har biri ikkita musbat butun son \(H_i\)​ (binoning balandligi) va \(G_i\)​ (tomdagi oltin tangalar soni) kiritiladi.

\(1 \le N \le 40\)

\(1 \le K \le 4 \times 10^{10}\)

\(1 \le H_i, G_i \le 10^9\)

Chiquvchi ma'lumotlar:

Alisher o'yinni turli yo'llar bilan o'tkazishi mumkin bo'lgan usullar sonini chop eting.

Izoh:

Ikkinchi test holatida quyidagi uchta o'yin Alisherni keyingi bosqichga o'tkazadi: {1, 2, 3}, {1, 4}, va {4}.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 15
5 5
5 12
6 10
2 1
 
4
2 
4 6
2 1
6 3
7 2
5 6
 
3
3 
2 7
4 6
3 5
 
0

G. EKUB so'rovlar

Xotira: 256 MB, Vaqt: 4000 ms
Masala

Otabek yaqinda natural sonlar ketma-ketligini o'rganishni boshladi. U quyidagi shartni qondiradigan qism ketma-ketlikni qiziqarli deb hisoblaydi: qism ketma-ketlikdagi barcha elementlarining eng katta umumiy bo'luvchisi 1 dan katta bo'lishi kerak.

Kecha Otabek o'zining garajida N ta natural sonlardan iborat ketma-ketlikni topdi. U juda zerikkanligi sababli, o'zi uchun oddiy savollarni bera boshladi. Har bir savol ikki turdan biriga tegishli:

  1. X-pozitsiyadagi elementni V qiymatiga o'zgartirish.
  2. Ketma-ketlikning [L, R] intervalida joylashgan qiziqarli qism ketma-ketliklar sonini aniqlash.
Kiruvchi ma'lumotlar:

Birinchi qatorda N va Q musbat butun sonlari – ketma-ketlikdagi elementlar soni va so'rovlar soni beriladi. Keyingi qatorda N ta natural son \(A_i\) ketma-ketlikning elementlari sifatida keltirilgan. Keyingi Q qatorda har biri quyidagi shakldagi so'rovlar berilgan:

  • Agar so'rov turi 1 bo'lsa, X va V sonlari beriladi, bu holda X -pozitsiyadagi elementning qiymati V ga o'zgartiriladi.
  • Agar so'rov turi 2 bo'lsa, L va R sonlari beriladi, bu holda ketma-ketlikning L dan R gacha bo'lgan qiziqarli qism ketma-ketliklar sonini topish kerak.

\(1 \le N, Q \le 10^5\)

\(1 \le X \le N\)

\(1 \le A_i, V_i \le 10^9\)

Chiquvchi ma'lumotlar:

Har bir 2-turdagi so'rov uchun, ketma-ketlikning qiziqarli bo'laklar sonini alohida qatorda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 1
8 4 3 9 1
2 2 5
 
4
2 
5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5
 
6
1
3 
4 3
2 2 2 2
2 1 4
1 2 3
2 1 4
 
10
5
Kitob yaratilingan sana: 15-Nov-24 03:17