A. Juftliklarni o’chirish

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Minimanda SS 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(1S100000)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 SS so’mini sarflamoqchi. Bilag’onning otasi kitob do’koniga kirib qarasi u yerda faqat NN ta kitob qolgan ekan, har bir kitobning narxi Ai(1iN)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 SS so’mi bilan ko’pi bilan nechta kitob olishi mumkinligini topishda yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son, N(1N105)N(1 ≤ N ≤ 10^5) va S(1S109)S(1 ≤ S ≤ 10^9). Ikkinchi satrida bo’sh joy bilan ajratilgan holda NN ta butun son, Ai(1 iN,1Ai109)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. SS satr deb S1S2S3....SsS_1S_2S_3....S_{|s|} ko'rinishdagi satrga aytiladi. Bu yerda SiS_i  bu SS satrning elementlari S|S| esa SS satrning uzunligi.
2. S[i..j] (1ijS)S[i..j] (1 ≤ i ≤ j ≤ |S|) qism satr deb SiSi+1...SjS_iS_{i + 1}...S_j ko'rinishdagi satrga aytiladi.
3. SS satrning L (1LS)L (1 ≤ L ≤ |S|)  uzunlikdagi prefiksi deb S[1..L]S[1..L] satrga aytiladi.
4. SS satrning L (1LS)L (1 ≤ L ≤ |S|)  uzunlikdagi suffiksi deb S[SL+1..S]S[|S|-L+1..|S|] satrga aytiladi.

Sizning vazifangiz SS satrda ham prefiks, ham suffiks bo'la oladigan qism satrlar nechtaligini qaniqlash.

Kiruvchi ma'lumotlar:

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

Chiquvchi ma'lumotlar:

Birinchi qatorda KK soni. KK-ham prefiks ham suffiks bo'la oladigan satrlar soni.
Keyingi KK ta qatorda esa Li CiL_i C_i sonlari. LiLi ham prefiks ham suffiks bo'luvchi satr uzunligi CiC_i esa shu prefiks(suffiks) SS satrda jami necha marotaba qism satr bo'lib kelganligi. Li CiL_i C_i juftliklari LiL_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(1S106)S ( 1 \le |S| \le 10^6) satr berilgan, siz quyidagi shartni qanoatlantiruvchi (A,B,C,D)(A, B, C, D) to’rtliklar sonini toping:

  • 0A<B<C<D<S0 \le A < B < C < D < |S|
  • SA=SDS_A = S_D
  • SB=SCS_B = S_C
Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining yagona satrida SS kiritiladi

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida shartlarni qanoatlantiradigan (A,B,C,D)(A,B,C,D) to’rtliklar sonini 109+710^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 NN soni beriladi, siz NN sonini HTTS shartiga tekshirishingiz kerak bo'ladi.
HTTSHTTS sharti quydagicha:

  • NN sonining barcha raqamlari toq bo'lishi kerak.
  • NN sonining uzunligi ham toq bo'lishi kerak.
Kiruvchi ma'lumotlar:

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

Chiquvchi ma'lumotlar:

Chiqish faylida NN soni HTTSHTTS 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
Kitob yaratilingan sana: 06-Jun-25 17:29