A. Oraliqlar daraxti

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Azimjon N ta har xil elementdan iborat(qiymatlari takrorlanmaydigan) A massiv uchun 2×N-1 ta elementdan iborat T oraliqlar daraxti orqali minimum qiymatni hisoblash uchun quyidagi tartibda tuzdi:

for i in range(0, N): T[i+N-1] = A[i]

for i in range(N-2, -1, -1): T[i] = min(T[i*2+1], T[i*2+2])

Shundan so’ng o’zining A massivini tashlab yubordi va o’ziga 2×N-1 ta elementdan iborat T massivni saqlab qoldi. Azimjon uyda yo’qligidan foydalanib uning ukasi Azimjonning T massiv elementlarini qiymatlarini tartibini almashtirib qo’ydi, va hattoki ba’zi elementlarining qiymatini o’zgartirib ham qo’ygan bo’lishi mumkin. Bundan xabar topgan Azimjon o’zining T massivini qiymatlari almashgan bo’lsada yuqoridagi qonuniyatiga mos keladigan holda qayta tiklamoqchi bo’ldi. Qayta tiklaganida ham A massivga mos keladigan elementlar unikal(yagona)ligini saqlab qolishi kerak. Sizning vazifangiz Azimjon buni eplay oladimi yoki yo’qligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida N=2^k shaklidagi bitta butun son, N(1 ≤ N ≤ 2¹⁸) soni kiritiladi. Keyingi satrda 2×N-1 ta son, Azimjonning ukasidan qolgan T(-10⁹ ≤ T_i ≤ 10⁹) massivining elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida agar Azimjon o’z massivini qayta tiklay olsa dastlabki satrda YES so’zini, keyingi satrda esa 2×N-1 ta elementdan iborat T massivining qayta tiklangan holatini (Agar yechimlar ko’p bo’ladigan bo’lsa leksikografik eng kichigini) chop eting, agar qayta tiklay olmasa yagona satrda NO so’zini chop eting.

Misollar:

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

B. Do’st uchlik

Xotira: 16 MB, Vaqt: 1000 ms

Masala

\(N\) ta butun sondan iborat kamaymaydigan tartibda \(A\) butun sonlar to’plami va bitta butun son, \(d\) soni berilgan. Quyidagi ikki shartni bajaradigan uchliklar sonini aniqlang.

\(i < j < k\)
\(A[j]-A[i]=A[k]-A[j]=d\)

Kiruvchi ma'lumotlar:

Dastlabki satrda ikkita butun son, \(N(1 \le N \le 10^4)\) va \(d(1 \le d \le 20)\) sonlari kiritiladi. Keyingi satrda \(N\) ta butun son, \(A(0 \le A_i \le 2*10^4)\) to’plam elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Yuqoridagi shartni qanoatlantiruvchi uchliklar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7 3 1 2 4 5 7 8 10	3

C. Juftliklarni o’chirish

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Minimanda \(S\) satri mavjud. U satr ichida yonma-yon turgan ikkita bir xil belgini ko’rsa jahli chiqadi, shuning uchun u barcha yonma-yon turgan bir xil belgilarning ikkisini ham satrdan o’chirishga qaror qildi. Ammo satr juda uzun bo’lganligi bois bu ishni kompyuterda bajarish osonligini bilgan holda dasturchi bo’lganingiz uchun sizdan unga yordam berishingizni iltimos qildi. Unga o’z satridan barcha yonma-yon turgan bir xil belgilarni o’chirishga yordam bering.

Kiruvchi ma'lumotlar:

Yagona satrda lotin alifbosining kichik harflaridan iborat \(S(1 \le |S| \le 100000)\) satri kiritiladi.

Chiquvchi ma'lumotlar:

Agar natijaviy satr bo’sh bo’lsa Empty String so’zini, aks holda natijaviy satrni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	aaabccddd	abd
2	aa	Empty String
3	baab	Empty String

**D. Plyus * Plyus**

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga \(N \times M\) o’lchamli jadval berilgan, har bir elementi yaxshi (good - G) yoki yomon (bad - B) ni ifodalaydi.

To’g’ri Plyus deb gorizontal va vertikal uzunliklari teng, bu uzunlik toq, chiziqlar o’zaro teng markazdan kesishganiga aytiladi. Plyusning yuzasi u egallab turgan yacheykalar soniga teng. Quyidagi diagrammada yashil maydonlar Plyus hisoblanadi, sariq maydonlar esa Plyus hisoblanmaydi.

Sizga berilgan jadvaldan tomonlari faqat yaxshi elementlardan iborat bo’ladigan shunday ikkita Plyusni ajratib olingki, ajratilgan Plyuslar jadvalda umumiy nuqtaga ega bo’lmasin va ikkila Plyusning yuzalari ko’paytmasi maksimal bo’lsin.

Kiruvchi ma'lumotlar:

Dastlabki satrda ikkita butun son, \(N\) va \(M(2 \le N, M \le 15)\) sonlari, jadvalning qatorlar va ustunlar soni kiritiladi. Keyingi qatordan boshlab \(N\) ta qatorning har birida \(M\) tadan belgi, jadvalning elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Umumiy koordinataga ega bo’lmagan holda ajratib olingan ikkita Plyusning yuzalari ko’paytmasi maksimal necha bo’lishini chop eting.

Izoh:

Quyidagi rasmning chap tomonidagi jadvalda 1-test, o’ng tomondagi jadvalda 2-test bo’yicha ikkita Plyus qanday ajratib olinganligini ko’rishingiz mumkin:

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 6 GGGGGG GBBBGB GGGGGG GGBBGB GGGGGG	5
2	6 6 BGBBGB GGGGGG BGBBGB GGGGGG BGBBGB BGBBGB	25