A. #

Xotira: 32 MB, Vaqt: 1000 ms

Masala

S satr beriladi va bu satrda # belgisi orasidagi barcha belgilarni ekranga chiqarish talab etiladi. AI yoki ko'chirmachilik qilmasandan dasturni tuzib bering :).

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^5)\)

Keyingi t ta qatorda S satr beriladi. \((1≤len(S)≤10^6)\)

Chiquvchi ma'lumotlar:

# orasidagi barcha harflarni alohida qatorlarda chop eting.

Izoh:

S satrda faqat 2 ta # bo'lishi kafolatlangan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 Salom#Otabek#Xushkelibsiz Chiter#Robocontest#Yomon #Master#	Otabek Robocontest Master

B. MasterRobotTest

Xotira: 32 MB, Vaqt: 1300 ms

Masala

Bu masala shundan iborat: berilgan matn (harflar to'plami) ichida ma'lum bir so'zni qanchalik ko'p marta hosil qilish mumkinligini hisoblash kerak. Matndagi harflarni ixtiyoriy tartibda qayta joylashtirishga ruxsat beriladi, lekin har bir harfni faqat matnda mavjud bo'lgancha ishlatish mumkin.

Masalan, sizga berilgan harflar to'plami "robomaster" bo'lsa va siz quyidagi so'zlarni qidiryapsiz:

master
robot
test

Bu so'zlarni matnda ketma-ket ravishda (ya'ni, uzluksiz qism sifatida) hosil qilish mumkin bo'lgan maksimal sonini topish kerak.

Kiruvchi ma'lumotlar:

S satr beriladi. \((1≤len(S)≤10^6)\)

Chiquvchi ma'lumotlar:

Masala javobini avval master, keyin robot va test so'zlari necha marta hosil bo'lishini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 robocontest masterotabek robocoding	0 1 1 1 0 1 0 0 0

C. XYZ

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Sizga N soni beriladi va sizdan x, y, va z ning barcha mumkin bo'lgan juftliklar sonini topishingiz so'raladi, bunda bu juftliklar quyidagi tenglikni qanoatlantiradi:

\(xy+yz+zx=N\)

x, y, va z — musbat yoki nol butun sonlar (ya'ni, ular 0 yoki musbat bo'lishi mumkin).

Kiruvchi ma'lumotlar:

Natural N soni beriladi. \((1≤N≤10^8)\)

Chiquvchi ma'lumotlar:

Maslani javobini chop eting.

Izoh:

1-testda
0 1 2

0 2 1

1 0 2

1 2 0

2 0 1

2 1 0

jami mumkin bo'lgan hollar ya'ni 6 ta.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2	6
2	3	7

D. Ketma-ket sum

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Javlonbek 2 ta musbat butun son N va X sonlardan quyidagi shartlarni qanoatlantiradigan N uzunlikdagi natural sonlar qatori \(A_1,A_2,…,A_N\) ni topmoqchi bo'ldi. Bu ketma-ketlik quyidagi shartni bajaraishi kerak:

\(0<A_1<A_2<⋯<A_N\) ya'ni qator o'suvchi tartibda bo'lishi kerak.
Ketma-ketlikning barcha elementlari yig'indisi X ga teng bo'lishi kerak: \(A_1+A_2+⋯+A_N=X\)

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^3)\)

Keyingi T ta qatorda N va X sonlar beriladi. \((1≤N≤2×10^5)\), \((1≤X≤10^{9})\)

Chiquvchi ma'lumotlar:

Agar shunday qator mavjud bo'lsa:

Shartlarni qanoatlantiradigan barcha qatorlardan lug'at tartibida eng kichikini toping va chop eting. Agar bunday qator mavjud bo'lmasa, -1 ni chop eting.

Misollar:

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

E. Raqam izlash

Xotira: 32 MB, Vaqt: 1300 ms

Masala

1 dan N-gacha bo'lgan sonlarda K raqam necha marta qatnashganini topish kerak.

Kiruvchi ma'lumotlar:

Dastlabki qatorda T butun soni beriladi. \((1≤T≤10^6)\)

Keyingi T ta qatorda N natural soni beriladi. \((1≤N≤10^{18})\)

Chiquvchi ma'lumotlar:

Har bir so'rov uchun natijalarni yig'indisini \(10^9+7\) ga bo'lgandagi natijani chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 100 3 180 2 1245 7	402

F. Bo'linadimi ?

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Bizda juda katta bir X soni mavjud. Faqatgina shuni bilamizki, X soni bir nechta \(A_1,A_2,…,A_N\) sonlarining har biriga bo'linadi. Shu ma'lumotlardan foydalanib, X soni K soniga bo'linadimi yoki yo'qmi, aniqlashimiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va K natural sonlar beriladi. \((1≤N≤5×10^5)\), \((1≤K≤10^{18})\)

Ikkinchi qatorda N ta massiv elementlari beriladi. \((1≤A_1,A_2,A_3,..,A_N≤10^{18})\)

Chiquvchi ma'lumotlar:

Agar bo'linsa “Ha” aks holda “Yo'q” so'zlarini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 6 1 2 3 4	Ha
2	3 5 1 2 3	Yo'q

G. Marafon

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Marafonda N nafar ishtirokchi qatnashmoqda. Har bir ishtirokchiga 1 dan N gacha bo'lgan tartib raqami berilgan. Ishtirokchilarning joylashuvi \(A\) massivida berilgan bo'lib, \(A[i]\) ishtirokchining finish chizig'idan qancha uzoqda ekanligini ko'rsatadi (masofa kichik bo'lsa, finishga yaqinroq).

Sizga \(T\) ta so'rov beriladi. Har bir so'rovda ikki ishtirokchining raqami (x, y) beriladi. Siz quyidagini aniqlashingiz kerak:

Agar x ishtirokchisi y ishtirokchisiga yetib olishi kerak bo'lsa, x ishtirokchisi finishga yaqinlashish davomida nechta ishtirokchini ortda qoldirishi kerakligini hisoblang.
Agar x ishtirokchisi allaqachon y ishtirokchisidan yaqinroq yoki teng masofada bo'lsa, natija 0 bo'ladi.

Kiruvchi ma'lumotlar:

Birinchi qator N va T sonlar beriladi. (N — ishtirokchilar soni, T — so'rovlar soni). \((1≤N,T≤10^5)\)

Ikkinchi qator: \(A_1,A_2, ..., A_N\) lar beriladi. (Ishtirokchilarning finish chizig'idan masofalari)

Keyingi T ta qatorda: x va y lar beriladi. \((1≤x,y≤N)\)

Chiquvchi ma'lumotlar:

Masala javobi alohida qatorlarda chop eting.

Izoh:

1-test.
4 3

7 20 14 8

1-so'rov (2, 1): 2-ishtirokchi finishga yetguncha, 3 va 4-ishtirokchilarni ortda qoldirishi kerak (javob: 2).

2-so'rov (3, 1): 3-ishtirokchi finishga yetguncha, faqat 4-ishtirokchini ortda qoldiradi (javob: 1).

3-so'rov (4, 1): 4-ishtirokchi allaqachon 1-ishtirokchidan yaqinroq (javob: 0).

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 7 20 14 8 2 1 3 1 4 1	2 1 0

H. Xato masalami ?

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Ismoil ismli o'quvchiga 2-lik sanoq tizimida sonlarni qo‘shish berilgan. Ismoil sonlarni qo‘shish jarayonida har bir xonani alohida hisoblaydi, lekin dildagini sonni doim unutib qo'yadi. Shuning uchun hisobda dildagi sonni hisobga olmaydi. Sizdan Ismoil tomonidan noto‘g‘ri hisoblangan natijani 10-lik sanoq tizimida chiqarishingiz so‘raladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^5)\)

Keyingi T ta qatorda 2 ta son A va B beriladi, ular 2-lik sanoq tizimida ifodalangan faqat 0 va 1 lardan tashkil topgan qiymat beriladi. \((1\leq len(A), len(B) < 10^4)\)

Chiquvchi ma'lumotlar:

Ismoil ishlagan xato javobni \(10^9+7\) ga bo'lgandagi qoldiqni alohida qatorlarda chop eting.

Izoh:

1-testda
kabi hisoblagan va \(110_2=6_{10}\)

kabi hisoblagan va \(0_2=0_{10}\). Bunda 1+1=10 deb 0 yozib 1 dilda doim unutib qoldirilgan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 10 100 111 111	6 0

I. Uzinliklar soni

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Berilgan N butun soni uchun quyidagi shartlarni qanoatlantiradigan sonlar ketma-ketliklarining uzunliklari sonini toping:

Ketma-ketlikdagi barcha sonlarning yig‘indisi N-ga teng bo‘lishi kerak.
Ketma-ketlikdagi sonlar faqat ikkita turdagi qo‘shni butun sonlardan iborat bo‘lishi kerak
Ketma-ketlikdagi sonlari istalgan tartibda joylashishi mumkin.
Ketma-ketlik uzunligi har xil bo‘lishi kerak (faqat har xil uzunliklar hisobga olinadi).

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^4)\)

Keyingi T ta qatorda N ketma-ketlik sonlarining yig‘indisi beriladi. \((1 ≤ N ≤ 10^9)\)

Chiquvchi ma'lumotlar:

Ketma-ketliklarning har xil uzunliklari sonini aniqlang va bitta butun sonni alohida qatorlarda chop eting.

Izoh:

1-testda N=8 bo'lsa:

[3,3,2] uzunligi 3,

[1,2,2,2,1] uzunligi 5,

[1,2,1,2,1,1] uzunligi 6,

[1,1,2,1,1,1,1] uzunligi 7.
Jami uzunligi har xil bo'lgan 4 ta hol mavjud ekan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 8 12	4 6

J. Matematika #2

Xotira: 32 MB, Vaqt: 1000 ms

Masala

\(f(x)=\frac{1}{x^2 + 6x + 8}\) ifodan berilgan. \(f(1)+f(2)+f(3)+....+f(n)\) ifodani hisoblash dasturi tuzisin.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^5)\)

Keyingi T ta qatorda N natural son beriladi. \((1≤N≤10^{18})\)

Chiquvchi ma'lumotlar:

Masala javobini \(10^{-4}\) aniqlikda alohida qatorlarda chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 3 5	0.1369 0.1736

K. Summa

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Sizga n uzunlikdagi a massivi beriladi. Siz q ta savolga javob berishingiz kerak:
Savollar ikki hilda:

1 - a massivini i-elementini v ga almashtirasiz
2 - a massivini summasini chiqarasiz

Kiruvchi ma'lumotlar:

Birinchi qatorda n,q sonlari kiritiladi

Ikkinchi qatorda a massivi kiritiladi

Keyingi q ta qatorda 1 i v yoki 2 sonlari kiritiladi

Chegaralar:

\(1≤n,q≤\)\(2*10^5\)

\(1≤a[i],v≤10^9\)

\(1≤i≤n\)

Chiquvchi ma'lumotlar:

Masala javobi

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 1 3 2	3
2	7 3 5 4 3 2 1 6 7 2 1 5 2 2	28 29

L. O'rin almashtirishlar soni

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga \(N\) ta elementdan tashkil topgan \(A\) massiv berilgan. Siz quyidagi amalni istalgancha bajarishingiz mumkin.

Istalgan elementni qo'shni element bilan almashtira olasiz.

Siz bu amalni minimal marta bajarib turib massivdagi hamma bir xil elementlarni yonma-yon joylashtirishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(N(3≤N≤10^6).\)

Keyingi qatorda \(N\) ta butun son \(A_i(1≤A_i≤16).\)

Chiquvchi ma'lumotlar:

Ekranga minimal amallar sonini chop eting.

Izoh:

Birinchi test uchun izoh:

[1,2,1,4,4,3,4] massivi berilgan.

[2,1,1,4,4,3,4] shu holatga keladi.
[2,1,1,4,4,4,3] keyin shu holatga keladi.

Natijada minimal amallar soni 2 bo'ladi.

Misollar:

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

M. Query

Xotira: 512 MB, Vaqt: 2000 ms

Masala

Massiv beriladi.

q ta savol beriladi

Har bir savol:

1 i v - a[i] = v qilishingiz kerak
2 l r - [l,r] oralig'idagi har hil sonlar summasini chop eting

Kiruvchi ma'lumotlar:

n va q sonlari

a massivi

q ta qatorda 2 hil turdagi savol

Chegaralar:

\(1≤n,q≤2*10^5\)

\(1≤a[i]≤40\)

\(1≤i≤n\)

\(1≤v≤40\)

\(1≤l≤r≤n\)

Chiquvchi ma'lumotlar:

Masala javobi

Izoh:

1-savoldan song massiv [3,5,4,2,2]

2-savoldan song massiv [3,5,4,5,2]

3-savolda [1,4] oralig'ida [3,5,4,5] dagi har hil sonlar bu 3,4,5. 3+4+5=12

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 2 5 4 2 2 1 1 3 1 4 5 2 1 4	12
2	5 4 7 6 3 9 10 1 2 2 2 1 4 1 5 1 2 5 5	21 1
3	5 4 10 3 9 7 1 1 4 2 2 5 5 2 1 4 2 1 2	1 24 13
4	5 4 1 7 2 9 1 1 1 8 2 3 5 1 1 7 2 1 4	12 18

N. Query #2

Xotira: 512 MB, Vaqt: 2000 ms

Masala

Massiv beriladi.

q ta savol beriladi

Har bir savol:

1 i v - a[i] = v qilishingiz kerak
2 l r - [l,r] oralig'idagi har hil sonlar summasini chop eting

Kiruvchi ma'lumotlar:

n va q sonlari

a massivi

q ta qatorda 2 hil turdagi savol

Chegaralar:

\(1≤n,q≤2*10^5\)

\(1≤a[i]≤10^9\)

\(1≤i≤n\)

\(1≤v≤10^9\)

\(1≤l≤r≤n\)

Chiquvchi ma'lumotlar:

Masala javobi

Izoh:

1-savoldan song massiv [3,5,4,2,2]

2-savoldan song massiv [3,5,4,5,2]

3-savolda [1,4] oralig'ida [3,5,4,5] dagi har hil sonlar bu 3,4,5. 3+4+5=12

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 4 7 6 3 9 10 1 2 2 2 1 4 1 5 1 2 5 5	21 1
2	5 4 10 3 9 7 1 1 4 2 2 5 5 2 1 4 2 1 2	1 24 13
3	5 4 1 7 2 9 1 1 1 8 2 3 5 1 1 7 2 1 4	12 18
4	5 4 9 10 5 5 6 1 3 1 1 5 8 1 3 1 2 4 5	13
5	5 4 8 4 5 7 5 1 1 3 1 3 2 2 5 5 2 2 3	5 6

O. Remont

Xotira: 32 MB, Vaqt: 1000 ms

Masala

O‘z kvartirasini sotib olganidan keyin Boriy har bir xonaga oboylar yopishtirishga qaror qildi. Boriyning kvartirasida n ta xona bor, har biri to‘rtburchak parallelepiped shakliga ega. Har bir xona uchun devorlarning uzunligi, eni va balandligi metrda ma'lum (turli xonalar har xil o‘lchamlarga ega bo‘lishi, shu jumladan balandligi ham farq qilishi mumkin).

Boriy m turdagi oboylarni tanladi, ular bilan u xonalarining devorlarini yopishtirishni rejalashtirmoqda (lekin hamma turlarini ishlatish shart emas). Har bir oboy turi o‘ralgan rulonlarda sotiladi, rulonlarning uzunligi va eni aniq belgilangan (albatta, rulon to‘liq yozilgan holatda o‘lchanadi). Bundan tashqari, har bir turdagi rulonning narxi ham ma'lum.

Har bir oboy turida chiziqlar bor, ular rulonning uzunligi bo‘ylab vertikal joylashgan. Yopishtirilganda chiziqlar faqat qattiq vertikal joylashishi kerak (shuning uchun rulonni aylantirib bo‘lmaydi, hattoki uning uzunligi kenglikdan qisqa bo‘lsa ham). Rulonlarni erkin kesish mumkin, lekin yopishtirilgan qismlarning tutashuvlari ham vertikal bo‘lishi shart. Bundan tashqari, har bir xonada faqat bir turdagi oboy ishlatilishi kerak va bitta rulonning qismlarini turli xonalarga yopishtirish mumkin emas, ya’ni har bir xona uchun rulonlar alohida xarid qilinadi. Ba'zi rulonlardan to‘liq foydalanilmasligi ham mumkin.

Kvartira sotib olgandan keyin Boriyning moliyaviy ahvoli yaxshi emas, shuning uchun u oboylarga minimal mablag‘ sarflashni xohlaydi. Unga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda n (1 ≤ n ≤ 500) — Boriyning kvartirasidagi xonalar soni beriladi.

Keyingi n qatorning har birida 3 ta bo‘shliq bilan ajratilgan natural sonlar keltiriladi — navbatdagi xonaning devorlarining uzunligi, eni va balandligi (metrlarda).

Keyingi qatorda m (1 ≤ m ≤ 500) — mavjud oboy turlari soni keltiriladi.

Keyingi m qatorning har birida 3 ta bo‘shliq bilan ajratilgan natural sonlar keltiriladi — navbatdagi oboy turining uzunligi, eni (metrlarda) va bitta rulonning narxi.

Kiritish ma'lumotlaridagi barcha sonlar 500 dan oshmaydi. Har bir xonani mavjud oboy turlari yordamida yopishtirish mumkinligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Bitta sonni chiqaring — rulonlarning minimal umumiy qiymati. Agar buni iloji bo'lmasa -1.

Izoh:

1-testda 3-xonaga hech qaysi rulonni qo'yib bo'lmaydi.

2-testda 1-xonaga 1-turdagi rulonni tanlasak 5 ta pul ketadi, 2-xonaga 1-turdagi rulonni tanlasak 1 pul ketadi va 3-xonaga 1-turdagi rulonni tanlasak 3 ta pul ketadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 5 2 1 4 5 1 4 3 5 1 3 2 4	-1
2	3 5 5 4 1 1 2 3 3 4 3 5 4 1 4 1 4 5 4 1	9
3	4 4 3 4 4 5 3 5 2 4 2 2 3 3 4 3 4 1 3 1 1 3 4	76

P. Permutation matrix

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga n soni beriladi.

Siz bu shartlarga javob beradigan martix ni chiqaring:

Har bir i(1≤i≤n) uchun [a[i][1],a[i][2],a[i][3],…,a[i][n]] n uzunlikdagi permutation bo'lishi kerak.
Har bir j(1≤j≤n) uchun [a[1][j],a[2][j],a[3][j],…,a[n][j]] n uzunlikdagi permutation bo'lishi kerak.

a massivi permutation bo'lishi uchun,a massivi sortlanganda har bir i(1≤i≤n) uchun a[i]=i bo'lishi kerak.

Kiruvchi ma'lumotlar:

n soni

Chegaralar:

\(1≤n≤10^3\)

Chiquvchi ma'lumotlar:

Masala javobi

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1	1
2	2	1 2 2 1

Q. EKUK #1

Xotira: 32 MB, Vaqt: 1000 ms

Masala

N uzunlikdagi ketma-ketliklarni tashkil qilish kerak, ya'ni har bir ketma-ketlikda N ta musbat butun son bo'lishi kerak. Bu ketma-ketliklar orasidan eng kichik umumiy bo'luvchi (EKUB) M ga teng bo'lgan ketma-ketliklar sonini topish kerak.

Kiruvchi ma'lumotlar:

Birinchi N va M natural sonlar beriladi. \((1 ≤ N,M ≤ 10^{18})\)

Chiquvchi ma'lumotlar:

Masala javobini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.

Izoh:

1-testda.
N=2 M=4. Demak uzunligi 2 va EKUK i 4 bo'ladigan sonlar kerak. Bular:
(1,4), (4,1), (2,4), (4,2), (4,4) jami 4 ta ekan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 4	5

R. Bo'linmas sonlar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

\(A_i\) va \(B_i\) ikkita musbat butun son bo'lib, \(A_i \neq B_i\) va \(K_i\) son beriladi. \(A_i\) va \(B_i\) bilan bo'linmaydigan, eng kichik bo'lgan \(K_i\)-chi sonni toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤t≤10^{5})\)

Keyingi T ta qatorda A, B va K natural sonlar berialdi. \(2≤Ai,Bi≤10^9\), \((1≤K_i≤10^{18})\)

Chiquvchi ma'lumotlar:

Masala javobini alohida qatorlarda chop eting.

Izoh:

1=testda
A=3, B=5, K=7 da

3 va 5 ga bo'linmaydigan sonlar: 1,2,4,7,8,11,13,… Shulardan 7-chi son 13, shuning uchun javob 13.

A = 10, B=20, K=1 da

Bu holatda A va B ga bo'linmaydigan sonlar ketma-ket 1,2,3,4,5,6,7,… K=1 uchun 1-chi son 1 bo'ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 5 7 10 20 1 18 12 100 314 159 2653	13 1 112 2677