A. Sehrli son

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Kunlardan bir kun sehrgar sehrli qasrda o‘zining sirli topshiriq kitobini ochib qoldi. Kitobda quyidagicha topshiriq bor edi:

“Sehrli Qasr Vazifasi”

Sehrli qasrda yashovchi Azimjon qasrdan chiqib ketmoqchi. Lekin u qasrdan chiqish uchun qasrning sirli qoidalariga amal qilishi kerak. Qoidalar quyidagicha:

  • Azimjonga nn soni beriladi.
  • U shunday musbat xx sonini topishi kerakki, xnx\leq n shart bajarilishi kerak.
  • Topilgan xx ning raqamlari yig'indisi eng katta bo'lishi kerak.

Sehirgar bu muammoni hal qilish uchun sizga murojaat qildi. Sehrli qasrning sirini ochish uchun sehrli xx ni topishda yordam bering va sehrgar sizni o‘zining eng yaxshi do‘sti deb e'lon qiladi! 🎩✨ 

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida  n(1n1018)n(1\leq n\leq 10^{18}) butun soni beriladi. 

Chiquvchi ma'lumotlar:

Chiqish faylida raqamlari yig'indisi eng katta bo'ladigan sonni chop eting, agar yechimlar bir nechta bo'lsa eng katta xx ni tanlashingiz zarur bo'ladi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
100
99
2
948
899

B. O'rindiqlar

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Aytaylik, siz har kuni universitetga darsga borasiz. Har safar dars boshlanishidan oldin oxirgi daqiqalarda yetib kelasiz va sinfdagi ba'zi o'rindiqlar band. Masalan, bugun darsga do'stlaringiz sizdan oldin kelishgan va ba'zi bir o'rindiqlarni egallab band qilishgan.

Sinfda nn qator va mm ustundan iborat o'rindiqlar bor. Sinfni n×mn\times m ko'rinishidagi matritsa ko'rinishida ifodalash mumkun. Bo'sh joylar «.»«.» bilan, band joylar esa «»«*» belgisi bilan ifodalanadi. Sizning vazifangiz ixtiyoriy ustun yoki satrda kk ta yonma yon bo'sh joylarni. Tanlash mumkun bo'lgan barcha joylar sonini hisoblashingiz zarur bo'ladi. Tanlashingiz mumkun bo'lgan barcha joylar bir biridan farq qilishi kerakligini unitmang.

Kiruvchi ma'lumotlar:

Kirish faylida n,m,k(1n,m,k2000)n,m,k(1\leq n,m,k\leq 2000) uchta butun son, mos ravishda sinf xona o'lchami va topishingiz kerak bo'lgan bo'sh joylar soni.

Kiyingi satrlarda n×mn\times m matritsa beriladi sinf xona tasvirlanadi. Matritsa ikki xil belgidan tashkil topgan bo'lib, «.»«.» bo'sh joyni va «»«*» band joyni bildiradi.

Chiquvchi ma'lumotlar:

Chiqish faylida barcha mumkun bo'lgan tanlashlar sonini kk ta satr yoki ustun bo'yicha qo'shni bo'sh joylar soni chop eting.

Izoh:

Birinchi testda barcha mumkun bo'lgan tanlashlar soni quyida keltiriladi.

  • (1,3)(1,3)(2,3)(2,3)
  • (2,2)(2,2)(2,3)(2,3)
  • (2,1)(2,1)(2,2)(2,2)
Misollar:
# INPUT.TXT OUTPUT.TXT
1
2 3 2
**.
...
3
2
3 3 4
.*.
*.*
.*.
0

C. Robot va manipulyator

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Robot 2D2D koordinata tekislikda harakatlanadi va o'z yo'nalishini belgilar orqali boshqaradi. Harakat boshlang'ich nuqta (0,0)(0,0) dan boshlanadi va quyidagi buyruqlarni bajaradi:

  • LL – bir birlik chapga qadam tashlash.
  • RR – bir birlik o'ngga qadam tashlash.
  • UU – bir birlik yuqoriga qadam tashlash.
  • DD – bir birlik pastga qadam tashlash.

Robot maqsadi – barcha buyruqlarni bajargandan keyin yana boshlang'ich nuqtaga qaytish. Robot manipulyator deb ataladigan moslamaga ega. Bu manipulyator bir harakatni boshqa istalgan harakatga almashtiradi (L,R,U,D)(L,R,U,D).

Manipulyatordan foydalanish robotga noqulay bo'lganligi sababli, uni ishlatish imkon qadar kamroq amalga oshirilishi kerak. Agar boshlang'ich nuqtaga qaytishning iloji bo'lmasa, bu haqda xabar berish kerak.

Kiruvchi ma'lumotlar:

Bitta qatorda uzunligi 1s1000001 \leq |s| \leq 100\,000 bo'lgan ss satr berilgan – bu Robotning harakatlari ketma-ketligi.

Chiquvchi ma'lumotlar:

Agar Robotni boshlang'ich nuqtaga qaytarish imkonsiz bo'lsa, chiqishda 1-1 ni chop eting. Aks holda, Robotni qaytarish uchun minimal manipulyator ishlatish sonini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
RRU
-1
2
UDUR
1

D. Robot muhandissi

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Uzoq kelajakda siz robotni dasturlash bo'yicha yetakchi muhandissiz. Sizga yangi vazifa topshirildi.

Robotga berilgan butun son nn ni shunday bo'laklarga ajratish kerakki, u bo'laklar raqamlari faqat 00 va 11 dan iborat bo'lsin. Robot bu bo'laklarni yig'ib, asosiy maqsadni bajarishi kerak. Robot qancha ko'p bo'lak ishlatsa, uning energiya sarfi shuncha yuqori bo'ladi. Shuning uchun siz nn ni imkon qadar minimal bo'laklar soniga ajratishingiz kerak.

Bo'laklash shartlari:

  • Robot bo'laklarni yig'ib, sonni qayta tiklay olishi kerak a1+a2+...+ak=na_1+a_2+...+a_k=n.
  • Har bir bo'lak aia_i faqat 00 va 11 raqamlaridan tashkil topgan son (masalan, 1,10,11,100,...1,10,11,100,...) bo'lishi kerak. Boshqa raqamlar (masalan, 2,5,92,5,9) robotning tizimida xatolik keltirib chiqaradi.
  • Robot bo'laklarning sonini minimal qilishga intilishi kerak.

Sizga berilgan topshiriq shundan iboratki, yuqoridagi shartlarni qonoatlantiradigan dasturni robotga yozib berishdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida n(1n106)n(1\leq n\leq 10^6) butun soni beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylining dastlabki satrida minimal kk sonini chop eting, kiyingi satrda probil bilan ajratilgan holda a1,a2,...,aka_1,a_2,...,a_k ni chop etasiz. Agar bir nechta yechim mavjud bo'lsa ulardan birini chop etishingiz mumkun.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
4
4
1 1 1 1
2
21
2
10 11

E. Yangi qavslar

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Qavslar ketma-ketligi to'g'ri hisoblanadi, agar ochiluvchi va yopiluvchi qavslar soni teng bo'lsa hamda har qanday prefiks ichida yopiluvchi qavslar soni ochiluvchi qavslardan oshib ketmasa. Masalan, [[]]\texttt{[[]]}"[[][[]]]"{\texttt{"[[][[]]]"}} yoki [[[[]]]]\texttt{[[[[]]]]} ketma-ketliklari to'g'ri, ammo []]\texttt{[]]}[[][]]]\texttt{[[][]]]} yoki [[[]]]]]]\texttt{[[[]]]]]]} ketma-ketliklari to'g'ri emas. 

Sizga nn ta ochiluvchi va yopiluvchi qavslardan tashkil topgan ss satr beriladi. Szining vazifangiz berilgan kvadrat qavslar ketma-ketligini minimal balandlikdagi minimal psevdografik tasvirida chizishdan iborat. Tasvirlash uchun “+” va “-” (gorizontal) va “|” (vertikal) belgilaridan foydalanishingiz mumkun.

Masalan, [[][]][]\texttt{[[][]][]} ketma-ketlikni quyidagicha tasvirlash mumkun.

+-        -++- -+|+- -++- -+||   |||   ||   |||   ||+- -++- -+||   |+-        -++- -+\textcolor{#e83e8c}{\texttt{+-        -++- -+} \\ \texttt{|+- -++- -+||   |} \\ \texttt{||   ||   |||   |} \\ \texttt{|+- -++- -+||   |} \\ \texttt{+-        -++- -+}}

Qavslarni tasvirlashda quyidagicha cheklovlarga amal qiling:

  1. Chizishda qavslarning balandligi minimal bo'lishi kerak.
  2. Qavslar orasida faqat bitta bo'sh joy qoldiring, birlashib ketmasligi uchun.
  3. Ichma-ich joylashgan qavslar tashqi qavsdan kichikroq bo'lishi kerak.

Qavslarni tasvirlashda barcha qoidalarni hisobga oling va tasvirni eng ixcham shaklda chizing. Bu usul yordamida har qanday to'g'ri kvadrat qavslar ketma-ketligi yagona va aniq tarzda tasvirlanadi.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida n(2n1000)n(2\leq n\leq 1000) juft butun soni beriladi. Kiyingi satrda muvozanatlashgan ss satr beriladi. Berilgan satr faqat [[ va ]] qavslardan tashkil topgan. Satrning muvozanatliligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida masalaning yechimini chop eting ortiqcha belgilarsiz.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
6
[[][]]
+-        -+
|+- -++- -+|
||   ||   ||
|+- -++- -+|
+-        -+
2
6
[][[]]
+- -++-   -+
|   ||+- -+|
|   |||   ||
|   ||+- -+|
+- -++-   -+

F. Chigirtkalar ligasi

Xotira: 45 MB, Vaqt: 1000 ms
Masala

Tasavvur qiling, “Chigirtkalar Ligasi” bo‘lib o‘tmoqda. Uzunligi mm birlik bo‘lgan aylana ustida bir nechta chigirtka poygada qatnashmoqda. Har bir chigirtka bir xil tezlikga ega, har sekundda 1 birlik masofa bosib o‘tadi. Lekin ularning xarakteri o‘zgacha: dastlab ba’zilari harakatni chap (L), ba’zilari esa harakatni o‘ng (R) yo'nalishda sakrash bilan boshlaydi.

Aylana ustida nn ta chigirtka joylashgan bo‘lib, ularning har biri poyga boshida sis_i pozitsiyada turibdi va di[L,R]d_i \in [L, R] yo'nalishda bir vaqtda barcha chigirtka harakatni boshlaydi. Pozitsiyalar soat strelkasiga qarama-qarshi yo‘nalishda 11 dan mm gacha raqamlangan.

Biroq bu oddiy poyga emas! Aylana ustida maxsus qoidalar amal qiladi:

  1. Agar ikki chigirtka to‘qnashib ketsa, ular birdaniga yo‘nalishlarini teskari tomonga o‘zgartiradi (etibor bering chigirtkalar vaqt birligining yarmi uchun qandaydir yo'nalishda va vaqt birligining yana yarmi uchun teskari yo'nalishda harakatlanishi mumkin).
  2. Agar bir vaqtning o‘zida bir nechta to‘qnashuvlar yuz bersa, barchasi bir vaqtda o'z yo'nalishini qarama-qarshisiga o'zgartiradi.
  3. Harakat davomida chigirtka 11 pozitsiyadan o‘tganda mm pozitsiyaga qaytadi, va aksincha.

Sizning vazifangiz poyga tt birlik vaqt o‘tgach, har bir chigirtkaning yakuniy pozitsiyasini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida n,m,t(2n3105,2m109,0t1018)n,m,t(2\leq n\leq 3*10^5,2\leq m\leq 10^9,0\leq t\leq 10^{18}) - mos ravishda chigirtkalar soni, doira uzunligi va vaqt birligi.

Kiyingi nn ta satrda si,di(1sim,di[L,R])s_i,d_i(1\leq s_i \leq m, d_i\in [L,R]) mos ravishda ii-chigirtka joylashgan pozitsiya va chigirtka yo'nalishi. LL va RR mos ravishda soat yo'nalishi bo'yicha va soat miliga teskari yo'nalishga mos keladi. 

Chiquvchi ma'lumotlar:

Chiqish faylida tt vaqt birligidan so'ng, dastlabki chigirtkadan boshlab oxirgi chigirtkagacha barcha pozitsiyalarni bitta satrda probil bilan ajratilgan holda chop eting.  

Misollar:
# INPUT.TXT OUTPUT.TXT
1
2 4 8
1 R
3 L
1 3
2
4 8 6
6 R
5 L
1 R
8 L
7 4 2 7
3
4 8 2
1 R
5 L
6 L
8 R
3 3 4 2

G. Ikkilik qator

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga ikkilik sanoq sistemasidagi ss satr beriladi. Siz ushbu satr ustida quyidagi ikki amalni istalgancha bajarishingiz mumkun:

  • ss satrning istalgan [l,r][l,r] oralig'ini teskarisiga aylantirishingiz mumkun, faqat xx energiya sarf qilasiz. Misol 101100111100011\underline{011}001\rightarrow 1\underline{110}001.
  • ss satrning istalgan [l,r][l,r] oralig'idagi 1 larni 0 ga va 0 larni 1 ga almashtirishingiz mumkun, faqat yy energiya sarf qilasiz. Misol 101100111000011\underline{011}001\rightarrow 1\underline{100}001.

Sizning vazifangiz faqat 1 lardan iborat satrni hosil qilish uchun minimal qancha energiya sarf qilish kerak ekanligini hisoblashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylida ikkita x,y(0x,y109)x, y(0\leq x,y\leq 10^9)  butun sonlari beriladi. Kiyingi qatorda s(1s3000000)s(1\leq |s| \leq 3000000) ikkilik satr beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida masalaning yechimini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
1 10
01000
11
2
10 1
01000
2

H. Satr ichidagi sarguzashtlar

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga bir sirli satr ss berilgan. Ushbu satr o'z ichiga qiziqarli belgilarni oladi va SamCoding jamoasi sizdan u ustida bir nechta so'rovlarga javob berishni talab qiladi. Satr bilan ishlash uchun sizga qq ta so'rov beriladi, har bir so'rov quyidagi ikki turdan biriga tegishli:

1-tur: “Belgini almashtirish”

So'rov 1 i  c  1 \space{} i  \space{} c  \space{} - ko'rinishida berilsa ss satrning ii-pozitsiyadagi joylashgan belgini cc ga almashtirish kerak.

2-tur: “Substring izlash”

So'rov 2 l  r  y  2 \space{} l  \space{} r  \space{} y  \space{} - ko'rinishida berilsa sl+sl+1+...+srs_l + s_{l+1}+... +s_r satr ichida yy substringi necha marta uchrashini hisoblash kerak.

Substring – bu berilgan satrning ketma-ket tartibda keladigan qismidir (“abc” satrning barcha substringlari “a”, “b”, “c”, “ab”, “bc” va “abc”).

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida s(1s100000,si[a,b,...,z])s(1\leq |s|\leq 100000,s_i\in [a,b,...,z]) satr beriladi. 

Kiyingi satrda so'rovlar soni q(1q100000)q(1\leq q\leq 100000) beriladi. 

Kiyingi qq ta satrda yuqorida aytib o'tilgan ikki turga mansub so'rovlar beriladi.

  • 1,i,c(1is,c[a,b,...,z])1,i,c(1\leq i\leq |s|, c\in[a,b,...,z]);
  • 2,l,r,y(1lrs,1y105)2,l,r,y(1\leq l\leq r\leq |s|, 1\leq |y|\leq 10^5);

Barcha so'rovlar uchun y|y| larning yig'indisi 10510^5 dan oshmasligi kafolatlanadi

Chiquvchi ma'lumotlar:

Chiqish faylida har bir ikkinchi turga mansub so'rovga javobni alohida satrlarda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba
3
1
Kitob yaratilingan sana: 23-Jul-25 14:01