A. 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

B. Kitobsevar BILAG’ON

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Download Bilag'on APK latest version Game by Uzbros for android devices

Bilag’on kitob o’qishni juda ham yaxshi ko’radi, shuning uchun ham uning otasi har oylik ish maoshidan ma’lum bir qismini Bilag’onga kitoblar olish uchun sarflaydi. Bilag’onning otasi bu galgi oylik ish maoshidan Bilag’onga kitob olish uchun ko’pi bilan \(S\) so’mini sarflamoqchi. Bilag’onning otasi kitob do’koniga kirib qarasi u yerda faqat \(N\) ta kitob qolgan ekan, har bir kitobning narxi \(A_i(1 ≤ i ≤ N)\) so’m ekanligi kitoblarning muqovasiga yopishtirib qo’yilgan. Bilag’onga qancha ko’p kitob sovg’a qilinsa shuncha ko’p xursand bo’lishini inobatga olgan holda Bilag’onning otasi imkoni boricha ko’p sondagi kitob olmoqchi, unga kitob uchun ajratgan \(S\) so’mi bilan ko’pi bilan nechta kitob olishi mumkinligini topishda yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son, \(N(1 ≤ N ≤ 10^5)\) va \(S(1 ≤ S ≤ 10^9)\). Ikkinchi satrida bo’sh joy bilan ajratilgan holda \(N\) ta butun son, \(A_i (1 ≤ i ≤ N, 1 ≤ A_i ≤ 10^9)\) – har bir kitobning narxi kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, Bilag’onning otasi ko’pi bilan nechta kitob sotib olishi mumkinligini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 7 1 2 3 4	3
2	5 15 3 7 2 9 4	3
3	7 50 1 12 5 111 200 1000 10	4

C. Lochinbek va Z-funksiya

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Lochinbek so'ngi kunlarda Z-funksiya mavzusida ko'p bilimlarga ega bo'ldi. U bilib olgan narsalari quyidagilar edi.

1. \(S\) satr deb \(S_1S_2S_3....S_{|s|}\) ko'rinishdagi satrga aytiladi. Bu yerda \(S_i\) bu \(S\) satrning elementlari \(|S|\) esa \(S\) satrning uzunligi.
2. \(S[i..j] (1 ≤ i ≤ j ≤ |S|)\) qism satr deb \(S_iS_{i + 1}...S_j\) ko'rinishdagi satrga aytiladi.
3. \(S\) satrning \(L (1 ≤ L ≤ |S|)\) uzunlikdagi prefiksi deb \(S[1..L]\) satrga aytiladi.
4. \(S\) satrning \(L (1 ≤ L ≤ |S|)\) uzunlikdagi suffiksi deb \(S[|S|-L+1..|S|]\) satrga aytiladi.

Sizning vazifangiz \(S\) satrda ham prefiks, ham suffiks bo'la oladigan qism satrlar nechtaligini qaniqlash.

Kiruvchi ma'lumotlar:

Bitta qatorda kichik lotin harflaridan tashkil topgan \(S_1S_2...S_{|s|} (1 ≤ |S| ≤ 10^5)\) satr.

Chiquvchi ma'lumotlar:

Birinchi qatorda \(K\) soni. \(K\)-ham prefiks ham suffiks bo'la oladigan satrlar soni.
Keyingi \(K\) ta qatorda esa \(L_i C_i\) sonlari. \(Li\) ham prefiks ham suffiks bo'luvchi satr uzunligi \(C_i\) esa shu prefiks(suffiks) \(S\) satrda jami necha marotaba qism satr bo'lib kelganligi. \(L_i C_i\) juftliklari \(L_i\) o'sish tartibiga ko'ra chiqarilsin.

Izoh:

1-testda:
"sasrsas" so'zida "s" prefiksi bir paytni o'zida ham suffiks bo'lib kelmoqda va bunday qism satrlar soni 4 ta, "sas" bir paytni o'zida ham suffiks bo'lib kelmoqda va bunday qism satrlar soni 2 ta, "sasrsas" so'zining o'zi ham bir paytni o'zida ham suffiks bo'lib kelmoqda va bunday qism satrlar soni 1 ta.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	sasrsas	3 1 4 3 2 7 1
2	sss	3 1 3 2 2 3 1

D. Polindrom to’rtlik

Xotira: 4 MB, Vaqt: 500 ms

Masala

Sizga ingliz alifbosining kichik harflaridan iborat \(S ( 1 \le |S| \le 10^6)\) satr berilgan, siz quyidagi shartni qanoatlantiruvchi \((A, B, C, D)\) to’rtliklar sonini toping:

\(0 \le A < B < C < D < |S|\)
\(S_A = S_D\)
\(S_B = S_C\)

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining yagona satrida \(S\) kiritiladi

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida shartlarni qanoatlantiradigan \((A,B,C,D)\) to’rtliklar sonini \(10^9+7\) ga bo’lgandagi qoldiqni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	aaaaaac	15
2	obbo	1

E. HTTS

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Masalani to'liq nomi: Har tomonlama toq sonlar.

Sizga \(N\) soni beriladi, siz \(N\) sonini HTTS shartiga tekshirishingiz kerak bo'ladi.
\(HTTS\) sharti quydagicha:

\(N\) sonining barcha raqamlari toq bo'lishi kerak.
\(N\) sonining uzunligi ham toq bo'lishi kerak.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son \(N\) kiritiladi,\(N\)\((1 \le N \le 10^{18})\)

Chiquvchi ma'lumotlar:

Chiqish faylida \(N\) soni \(HTTS\) shartlarini qanoatlantirsa ″YES″ so'zini, aks holda ″NO″ so'zini chop eting.Bunda har bir harf istalgan formatda bo'lishi mumkin.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	13579	YES