A. MP3 Player

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Komiljon musiqani eshitishni yoqtiradi. Ammo uning telefonidagi musiqa dasturi g‘alati ishlaydi. Komiljonning telefonidagi mp3 player shunday tuzilganki, agar foydalanuvchi hozirda KK-musiqani eshitayotgan bo‘lsa, maxsus tugmalarni bosish orqali u K+1K + 1K1K - 1K+2K + 2K2K - 2 musiqalardan biriga o‘tishi mumkin.

Komiljon hozir XX-musiqani tinglamoqda, lekin u do‘sti Adhambekka YY-musiqani namoyish etmoqchi. U buni amalga oshirish uchun kamida necha marta maxsus tugmalardan foydalanishi kerak ekanligi toping.

Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida bitta butun son - X(1X500)X(1 \leq X \leq 500) Komiljon hozir tinglayotgan musiqa tartib raqami kiritiladi.

Kirish oqimining ikkinchi qatorida bitta butun son - Y(1Y500)Y(1 \leq Y \leq 500) Komiljon do‘sti Adhambekka namoyish etmoqchi bo‘lgan musiqa tartib raqami kiritialdi.

Chiquvchi ma'lumotlar:

Masala javobini ekranga chiqaring.

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

B. Tubga bo'linmas

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga N(1N300)N(1 \leq N \leq 300) soni beriladi. 1 dan farqli shunday eng kichik natural sonni topingki, u birinchi NN ta tub songa bo‘linmasin.

1 va o‘zidan farqli bo‘luvchisiga ega bo‘lmagan son tub son hisoblanadi. 19 va 2 sonlari tub sonlar hisoblanadi, 49 va 4 sonlari esa tub emas.

Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida bitta butun son - NN soni kiritiladi.

Chiquvchi ma'lumotlar:

Masala javobini ekranga chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
4
11

C. Olma uzish

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Komiljon va uning do‘stlarining jami NN kishilik do‘stlar davrasini tashkil qiladi. ii-bolada AiA_i ta olma bor. Agar barcha bolada bir xil sondagi olmalar bo‘lmasa kimdir xafa bo‘lishi mumkin. Shuning uchun ham har bir bola bog‘dagi daraxtga bir marta chiqib o‘zidan tashqari barcha do‘stlariga bittadan olma uzib tushishi mumkin. Hech kim xafa bo‘lmasligi uchun daraxtga kamida necha marta chiqib tushishga to‘g‘ri keladi?

Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida bitta butun son - N(1N2105)N(1 \leq N \leq 2 \cdot 10^5) jami bolalar soni kiritiladi.

Kirish oqimining ikkinchi qatorida probel bilan ajratilgan NN ta butun son - Ai(1Ai109)A_i(1 \leq A_i \leq 10^9) ii - boladagi olmalar soni kiritiladi.

Chiquvchi ma'lumotlar:

Daraxtga chiqib tushishlar minimal sonini chiqaring.

Izoh:

1-testda: 1-bola 1 marta, 3-bola 2 marta daraxtga chiqib tushishi kerak.
2-testda: barcha bolalarda olmalar soni teng.

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

D. Binar satr

Xotira: 256 MB, Vaqt: 1500 ms
Masala

SS binar satr berilgan. F(l,r)F(l, r) deb S[l..r]S[l ..r]qism satrning lik sanoq sistemasidagi qiymatiga aytiladi. SS satrning uzunligi NN bo‘lsa, barcha N(N+1)2N(N+1) \over 2 ta F(l,r)F(l, r) qiymatlari ichidan mavjud bo‘lmagan eng kichik nomanfiy butun sonni toping.

Kiruvchi ma'lumotlar:

Kirish oqimida yagona qatorda SS satr kiritiladi. (1S2105)(1 \le |S| \le 2 \cdot 10^5)

Chiquvchi ma'lumotlar:

Barcha F(l,r)F(l, r) qiymatlarning orasida mavjud bo‘lmagan eng kichik nomanfiy butun sonni chiqaring.

Izoh:

1-testda: F(l,r)F(l, r) qiymatlar ichida 02=00_2=012=11_2=1102=210_2=2112=311_2 = 31002=4100_2=4 sonlari mavjud. Ammo 1012=5101_2=5 mavjud emas. Demak, javob 5.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
100110
5
2
1111
0

E. Mamlakatlar va shaharlar

Xotira: 256 MB, Vaqt: 2000 ms
Masala

KKta mamlakatda jami NNta shahar bor. Birinchi mamlakatda a1a_1ta, ikkinchi mamlakatda a2a_2ta, KK-mamlakatda aKa_Kta shahar bor va ular ketma-ket raqamlangan. Xususan: 
1-mamlakat shaharlari 11dan a1a_1gacha; 
2-mamlakat shaharlari a1+1a_1+1dan a1+a2a_1+a_2gacha;

K-mamlakat shaharlari a1+a2+...+aK1+1a_1+a_2+...+a_{K-1} + 1dan NNgacha.

Shaharlar orasida harakatlanish uchun yo‘llar qurilgan. Bunda ixtiyoriy 1i<N1 \leq i < N uchun ii va i+1i+1-shaharlar o‘rtasida yo‘l bor. Undan tashqari, MMta qo‘shimcha yo‘l bir mamlakat ichidagi ikkita shaharni bog‘lab turadi. 

Sizga QQta so‘rovda har xil mamlakatda joylashgan XX va YY shaharlar beriladi. Vazifangiz XX shahardan YY shaharga boruvchi eng qisqa yo‘llar sonini topish. Javob katta bo‘lib ketishi mumkinligi sababli, javobni 109+710^9+7ga bo‘lgandagi qoldig‘ini chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda uchta butun son - K,N,MK, N, M sonlari kiritiladi. (1K,N,M3105;KN)(1 \le K, N, M \le 3 \cdot 10^5; K \le N)

Ikkinchi qatorda a1,a2,...,aKa_1,a_2,...,a_K beriladi. (ai1;a1+a2+...+aK=N)(a_i \ge 1; a_1+a_2+...+a_K=N)

Keyingi MMta qatorning har birida ikkitadan butun son - uu va vv beriladi, bu uu va vv shaharlar o‘rtasida qo‘shimcha yo‘l borligini anglatadi. (1u,vN;uv2)(1 \le u, v \le N; |u-v| \ge 2). Qo‘shimcha yo‘llar bog‘lovchi shaharlar bitta davlatda joylashganligi kafolatlanadi. 

Keyingi qatorda bitta butun son QQ beriladi. (1Q3105)(1 \le Q \le 3 \cdot 10^5)

Keyingi QQta qatorda XX va YY shaharlar beriladi. (1X,YN)(1 \le X, Y \le N). Bunda ular har xil mamlakatda ekanligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Har bir so‘rov uchun bitta yangi qatorda so‘rovlarga javobni 109+710^9+7ga bo‘lingandagi qoldig‘ini chiqaring.

Izoh:

Rasmda 3ta mamlakat va 13ta shahar bor. 1, 2, 3-shaharlar A mamlakatga; 4, 5, 6, 7, 8, 9-shaharlar B mamlakatga va 10, 11, 12, 13-shaharlar C mamlakatga tegishli. Shuningdek 1-3, 2-4, 5-7, 6-8, hamda 10-13 shaharlar o‘rtasida qo‘shimcha yo‘llar mavjud.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
3 13 5
4 5 4
1 3
4 2
8 6
10 13
5 7
3
7 12
4 5
1 13
2
1
4
Kitob yaratilingan sana: 06-Jun-25 11:54