A. Katta muammo

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Siz maktabingizda yangi sinfga ko'chib o'tdingiz. Yangi sinfga borishingizdan avval u sinfni ikki kun davomida kuzatgansiz. Sinfda 1 dan n gacha raqamlangan o'rindiqlar bor. Siz ikkala kunda ham bo'sh bo'lgan joylargagina o'tirsa bo'ladi deb hisoblaysiz (Birinchi kundan yangi sinfda janjallashishni xoxlamaysiz). Endi siz o'tirish uchun nechta variantingiz borligini hisoblab ko'rmoqchisiz.

Kiruvchi ma'lumotlar:

Birinchi qatorda n - o'rindiqlar soni kiritiladi. (1≤n≤105)(1\le n\le 10^5)

Keyingi ikki qatorda har birining uzunligi n ga teng bo'lgan ikkita satr kiritiladi. Mos ravishda birinchi va ikkinchi kundagi o'rindiqlarning holati.

Satr faqat O va _ belgilaridan tashkil topgan bo'lib, bunda O - band o'rindiq,  _ esa bo'sh o'rindiq ekanini ifodalaydi.

Chiquvchi ma'lumotlar:

Yagona qatorda masala javobini chop eting.

Izoh:

1-testda birinchi va uchinchi o'rindiqlar har ikkala kunda ham bo'sh, shuning uchun faqat shu joylarga o'tirish mumkin

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

B. Qism satr

Xotira: 64 MB, Vaqt: 1000 ms
Masala

substring() funksiyasi — ko‘pchilik dasturlash tillarida mavjud bo‘lgan va matnlar bilan ishlashda keng qo‘llaniladigan amal. U matnning bir qismini olish uchun ishlatiladi. Funksiya ikkita parametr — boshlang‘ich pozitsiya (start offset) va uzunlik (length) qabul qiladi. U aynan shu pozitsiyadan boshlab, berilgan uzunlikdagi yangi matnni qaytaradi.

Endi bir o‘ziga xos holatni ko‘rib chiqamiz: bitta matnga ushbu funksiya ketma-ket juda ko‘p marta qo‘llanildi. Har safar biz substring(s, start, length) funksiyasidan foydalanib, matnning bir qismini olib, uni keyingi matn sifatida ishlatdik. Natijada, ehtimol ancha qisqargan yakuniy matn qolgan.

Barcha ketma-ket bajarilgan substring() amallari natijasida hosil bo‘lgan yakuniy matnni aniqlang.

Kiruvchi ma'lumotlar:
  • 1-qator: ss — dastlabki matn beriladi 1≤∣s∣≤1061\le \lvert s\rvert \le 10^6
  • 2-qator: nn — bajariladigan amallar soni beriladi (1≤n≤106)(1\le n\le 10^6)
  • Keyingi n qatorda — har bir qatorda ikkita butun son startistart_i va lengthilength_i beriladi:
    • 0≤starti<lengthi−10\le start_i < length_{i-1} — har bir yangi startistart_i oldingi natijadan tanlanadi.
    • 1≤starti+lengthi≤lengthi−11\le start_i+length_i\le length_{i-1} — substring chegaradan chiqib ketmasligi kerak. 
Chiquvchi ma'lumotlar:

Oxirgi amaldan so‘ng hosil bo‘lgan yakuniy matnni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
helloworld
2
1 9
0 5
 
ellow
2 
abcdefghijklmnopqrstuvwxyz
8
1 24
1 22
1 20
1 18
1 16
1 14
1 12
1 10
 
ijklmnopqr

C. Dori vositalari

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Bu vazifada farmatsevt Intizorga yordam berish kerak. U ishlab chiqargan yangi dori vositasini N ta dorixonaga yetkazib berishi lozim.

Intizor N ta flakon (butilka) doriga ega, va i-chi flakonda dastlab aia_i ml dori bor.

Ba’zi dorixonalar boshqalarga qaraganda ancha ko‘p dori olmasligi kerak, shuning uchun Intizor ayrim flakonlardan boshqalariga dori quyishga qaror qildi.

Muammo shundaki, bu jarayonda juda aniq ishlash kerak va uni faqat maxsus shprits yordamida bajarish mumkin. Har safar Intizor dorini bir flakondan boshqasiga quyishda aniq K tomchi dori o‘tkazishi kerak (Kam yoki ko‘proq o‘tkazish mumkin emas).

Intizor bu jarayonni istalgancha takrorlashi mumkin va uning maqsadi barcha dorixonalarga deyarli teng miqdorda dori yetkazishdir.

Aniqroq qilib aytganda, eng ko‘p va eng kam miqdorda dori olgan dorixonalar orasidagi maksimal farqni minimal qilish lozim.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita natural son N va K (1≤N≤105,1≤K≤109)(1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10⁹) - dorixonalar soni va bir marta o'tkaziladigan dorining miqdori beriladi.

Ikkinchi qatorda N ta natural son ai(1≤ai≤109) a_i (1 ≤ aᵢ ≤ 10⁹) - har bir flakondagi dori miqdori kiritiladi.

Chiquvchi ma'lumotlar:

Yagona qatorda dorixonalar o‘rtasidagi dorining eng katta va eng kichik miqdori orasidagi minimal maksimal farqni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 1
46 35
 
1
2 
2 2
38 10
 
0
3 
5 5
6 13 1 8 36
 
5

D. Massivni tiklash

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Do'stingizda n + 1 ta elementdan tashkil topgan kamaymaydigan s massivi bor edi.

U s massivdan yangi n ta elementdan iborat a massivini hosil qildi. (1≤i≤n, a[i]=s[i]+s[i+1]2)(1\le i\le n,  a[i] = \frac{s[i] + s[i+1]}{2})

Endi u sizga a massivini berib, undan s massivni hosil qilishning variantlar sonini so'rayapti.

Kiruvchi ma'lumotlar:

Birinchi qatorda n natural soni kiritiladi. (1≤n≤5∗106)(1\le n\le 5*10^6)

Ikkinchi qatorda n ta butun son - a massiv elementlari kiritiladi. (1≤i≤n,0≤a[i]≤109)(1\le i\le n, 0\le a[i]\le 10^9)

Chiquvchi ma'lumotlar:

Do'stingiz bergan savolga javob bering.

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

E. Psevdokod

Xotira: 256 MB, Vaqt: 3000 ms
Masala

Nyuboy CP(Competitive Programming)ga qiziqadi. U hozir bitta masalani ishlayotgan edi. Nyuboy ushbu masalani 2-urinishda hal qildi. Sizga Nyuboyning 1-yechimi beriladi. Siz ushbu masalani ishlay olasizmi?

!!! Nyuboyning 1-yechimidagi yagona muammo Time Limit edi.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int n, q; cin >> n >> q;
	vector <int> a(n + 1);
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	while (q --){
		int l, r, k;
		cin >> l >> r >> k;
		vector <int> b;
		for (int i = l; i <= r; ++ i) b.push_back(a[i]);
		sort(b.begin(), b.end());
		cout << b[k - 1] << '\n';
	}
	return 0;
}
Kiruvchi ma'lumotlar:

Birinchi qatorda n va q natural sonlari kiritiladi. (n,q≤105)(n, q \le 10^5)

Ikkinchi qatorda n ta natural son kiritiladi. (1≤i≤n , a[i]≤105)(1 \le i \le n  ,  a[i] \le 10^5)

Keyingi q ta qatorning har birida l, r va k natural sonlari kiritiladi.

(1≤l≤r≤n, k≤r−l +1)(1 \le l \le r \le n,   k \le r - l  + 1)

Chiquvchi ma'lumotlar:

Masalaning javobini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 4
3 2 1 5 4
1 4 3
1 5 2
1 1 1
3 5 3
 
3
2
3
5
Kitob yaratilingan sana: 08-Jul-25 04:44