A. Polindrom?

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Sizga s satri beriladi. U faqat ‘0’, ‘1’ va ‘?’ belgilaridan turadi. Siz bu amalni hohlagan marta bajarishingiz mumkin:

s satridagi hohlagan ‘?’ belgisini tanlab uni hohlagan belgiga o'zgartirasiz.

Siz s satrini palindrom qila olsangiz, ushbu satrni chiqaring. Aks holda “No” so'zini chiqaring

Kiruvchi ma'lumotlar:

Yagona qatorda s satri(Uzunligi \(2*10^5\) dan oshmaydi). Satr faqat ‘0’, ‘1’ va ‘?’ belgilaridan turishi kafolatlanadi!

Chiquvchi ma'lumotlar:

Yagona qatorda, hohlagan polindrom s satrini, agar satrni polindrom qilish mumkin bo'lsa, aks holda “No” so'zini chiqaring! Agar javob “No” chiqsa siz uni hohlagan registr da("No", “NO”, “nO”) chiqarishingiz mumkin!

Izoh:

Birinchi testda faqat 1 ta javob bor.
Amallar ketma-ketligi:

1 - chi elementni ‘1’ soniga aylandiramiz.
2 - chi elementni ‘1’ soniga aylandiramiz.
3 - chi elementni ‘1’ soniga aylandiramiz.

Ikkinchi testta biz faqat birinchi elementni ‘0’ ga aylandirsak yetarli. Bu yerda ‘0000000’ satri ham javob bo'lishi mumkinligini ko'rish mumkin!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	???000111	111000111
2	??0?0?0	0?0?0?0
3	00?	000
4	01	No

B. Kim yutadi?

Xotira: 32 MB, Vaqt: 1000 ms

Masala

ilanoxaJ va rumiT o'yin o'ynashayotgan edi. O'yin sharti quydagicha:

O'yin boshida taxtada n ta ko'pto'k bo'ladi.
O'yinni Robocontest.uz saytida reytingi balandroq bo'lgan ishtirokchi boshlaydi!
Bir yurishda o'yinchilar 1 ta yoki 2 ta ko'pto'kni taxtadan olib tashlashadi.
Kim eng ohirgi bo'lib yursa shu ishtirokchi yutqazadi.

Agar ikkala ishtirokchilar ham optimal o'ynasa, o'yinda kim yurishini aniqlang!

Kiruvchi ma'lumotlar:

Birinchi qator \(T(1≤T≤10^5)\), testlar soni kiritiladi.

Keyingi T ta qatorda \(N(1≤N≤10^9)\) ko'pto'klar soni kiritiladi.

Chiquvchi ma'lumotlar:

Agar ikkala ishtirokchi ham optimal o'ynasa, kim yutishi aniqlang! Agar ilanoxaJ yutsa “ilanoxaJ”, aks holda “rumiT” deb chiqaring. Siz javobni hohlagan registrda chiqarishingiz mumkin, yani “rumit”, "RumiT", “rUMit”, “ilAnOxaj”, “ILANOXAJ” to'g'ri javob deb hisoblanadi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 5 10	rumiT ilanoxaJ rumiT

C. Yetadimi?

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga n ta sonnan iborat sonlar toplami beriladi.

Ulardan har qanday ikkita sonni m ga bo'lganda bir xil qoldiq chiqadigan qilib k sonni tanlash kerak yoki buni amalga oshirish mumkin emasligini aniqlash kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda 3 ta natural son n, k, m (\(2≤k≤n≤\)\(10^5\), \(1≤m≤\)\(10^5\)) - to'plamdagi raqamlar soni, tanlanishi kerak bo'lgan raqamlar soni va istalgan ikkita tanlangan raqamning farqining zarur bo'luvchisi.

Ikkinchi qatorda n ta son a1, a2, ..., an (0 ≤ ai ≤ \(10^9\)).

Chiquvchi ma'lumotlar:

Agar k ta sonni quyidagi shartlar bilan tanlashni iloji bo'lmasa “No” ni chop eting. Aks holda, “Yes” ni chop eting. Siz javoblarni hohlagan registrda chiqarishingiz mumkin “YES”, "YeS", “nO”, “NO” to'g'ri javob bo'lib hisoblanadi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 2 3 1 8 4	Yes
2	3 3 3 1 8 4	nO
3	4 3 5 2 7 7 7	YES

D. Robotlar o'yini.

Xotira: 256 MB, Vaqt: 2000 ms

Masala

ravraS virtual o'yinlarni juda sevadi, va u ko'p vaqtlardan beri o'z o'yinini yaratish uchun harakat qilib yurgandi. Va yaratdi, o'yin sharti quyidagicha:

Sizga \(n\) ta sondan iborat massiv beriladi. Massivdagi \(i(1≤i≤n)\)-element, \(i\)-robotning narxini bildiradi.
Har qanday robot qo'shni robotga urush e'lon qilishi mumkin(qoshni robot-o'ngdagi yoki chapdagi eng yaqin robot, agarda o'ngda yoki chapda robot bo'lsa).
Agar \(X\) narxga ega robot, \(Y\) narxga ega robotga urush e'lon qilsa, urush e'lon qilgan robot yutadi va uning narxi \(X-Y\) ga aylanadi, yutqazgan robot esa yo'q bo'lib ketadi.
O'yinda yutish uchun faqat bitta robot qolishi va narxi maksimal bo'lishi shart.

ravraSning ukasi sirakeB ham virtual o'yinlarni juda yaxshi koradi va u bunaqa oyinni oynamay qolishi mumkin emas edi.

Ammo u bu oyinda yutishga juda qiynaliyapti, va sizdan yordam soramoqda.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n(1≤n≤10^6)\)-robotlar soni.

Ikkinchi qatorda \(n\) ta butun son \(aᵢ(-10^9≤aᵢ≤10^9)\), \(aᵢ\) - bu \(i\)-robotning narxi.

Chiquvchi ma'lumotlar:

Bitta butun son - oxirgi robotning maksimal narxi.

Izoh:

1-testta. 1-robot 2-robotga urush e'lon qiladi va o'yin tugaydi. Javob: 1-(-2)

2-testta. 2-robot 3-robotga urush e'lon qiladi. 2-robot narxi = -1-1 Robotlar narxi = [2,-2]. 1-robot 2-robotga urush e'lon qiladi. 1-robot narxi = 2-(-2). Robotlar narxi = [4]. O'yin tugaydi. Javob: 4.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 1 -2	3
2	3 -2 -1 1	4
3	4 2 2 -2 0	6

E. Chiroyli massiv

Xotira: 512 MB, Vaqt: 2000 ms

Masala

Uzunligi 2*K bolgan massivni boshida K element va ohridagi K elementini yig'indisi S dan o'tmasa chiroyli deb ataladi.
Sizga uzunligi N bolgan massiv berilgan. Siz har bir element uchun shu element submassivni eng chapdagi bolsadigan eng uzun chiroyli submassivni toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va S sonlari \((1 \le N \le 2 \cdot 10^5, 1\le S \le 10^{12})\) - massivni uzunligi va yig'indini eng katta qiymati

Ikkinchi qatorda N ta son \((0 \le A_i \le 2^{32})\)

Chiquvchi ma'lumotlar:

N ta son, har bir element uchun eng katta chiroyli submassiv uzunligi.

Misollar:

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

F. nidtamasI ning sevimli massivi

Xotira: 256 MB, Vaqt: 2000 ms

Masala

nidtamasI da n uzunlikdagi a massivi bor edi. U o'z massivini zo'r deb hisoblardi, lekin u uni q ta operatsiya orqali judayam zo'r qilmoqchi! U har bir operatsiyada:

l va r sonlarini tanlab, har bir \(i(l≤i≤r)\) uchun a massivining i- elementiga \((i-l+1)\) sonini qo'shadi, yani \(a[i]:=a[i]+(i-l+1)\) qiladi!

Siz hamma operatsiyani qilib bo'lgannan so'ng, nidtamasI ning a massivini chop eting!

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n(1≤n≤2*10^5)\) soni kiritiladi.

Ikkinchi qatorda \(n\) ta \(aᵢ(1≤aᵢ≤10^6)\) soni kiritiladi.

Uchinchi qatorda \(q(1≤q≤2*10^5)\) soni kiritiladi.

Keyingi \(q\) ta qatorda \(lᵢ\) va \(rᵢ(1≤lᵢ≤rᵢ≤n)\) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Yagona qatorda hamma operatsiya qilib bo'lingandan keyingi nidtamasI ning a massivini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 2 1 2 1 1 2 2	3 2
2	2 2 1 2 2 2 1 1	3 2
3	1 1 2 1 1 1 1	3
4	1 2 2 1 1 1 1	4