A. Sehrli son
Xotira: 32 MB, Vaqt: 1000 msKunlardan 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 \(n\) soni beriladi.
- U shunday musbat \(x\) sonini topishi kerakki, \(x\leq n\) shart bajarilishi kerak.
- Topilgan \(x\) ning raqamlari yig'indisi eng katta bo'lishi kerak.
Sehirgar bu muammoni hal qilish uchun sizga murojaat qildi. Sehrli qasrning sirini ochish uchun sehrli \(x\) ni topishda yordam bering va sehrgar sizni o‘zining eng yaxshi do‘sti deb e'lon qiladi! 🎩✨
Kirish faylining dastlabki satrida \(n(1\leq n\leq 10^{18})\) butun soni beriladi.
Chiqish faylida raqamlari yig'indisi eng katta bo'ladigan sonni chop eting, agar yechimlar bir nechta bo'lsa eng katta \(x\) ni tanlashingiz zarur bo'ladi.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
100 |
99 |
2 |
948 |
899 |
B. O'rindiqlar
Xotira: 32 MB, Vaqt: 1000 msAytaylik, 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 \(n\) qator va \(m\) ustundan iborat o'rindiqlar bor. Sinfni \(n\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 \(k\) 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.
Kirish faylida \(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\times m\) matritsa beriladi sinf xona tasvirlanadi. Matritsa ikki xil belgidan tashkil topgan bo'lib, \(«.»\) bo'sh joyni va \(«*»\) band joyni bildiradi.
Chiqish faylida barcha mumkun bo'lgan tanlashlar sonini \(k\) ta satr yoki ustun bo'yicha qo'shni bo'sh joylar soni chop eting.
Birinchi testda barcha mumkun bo'lgan tanlashlar soni quyida keltiriladi.
- \((1,3)\), \((2,3)\)
- \((2,2)\), \((2,3)\)
- \((2,1)\), \((2,2)\)
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
2 3 2 **. ... |
3 |
2 |
3 3 4 .*. *.* .*. |
0 |
C. Robot va manipulyator
Xotira: 32 MB, Vaqt: 1000 msRobot \(2D\) koordinata tekislikda harakatlanadi va o'z yo'nalishini belgilar orqali boshqaradi. Harakat boshlang'ich nuqta \((0,0)\) dan boshlanadi va quyidagi buyruqlarni bajaradi:
- \(L\) – bir birlik chapga qadam tashlash.
- \(R\) – bir birlik o'ngga qadam tashlash.
- \(U\) – bir birlik yuqoriga qadam tashlash.
- \(D\) – 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)\).
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.
Bitta qatorda uzunligi \(1 \leq |s| \leq 100\,000\) bo'lgan \(s\) satr berilgan – bu Robotning harakatlari ketma-ketligi.
Agar Robotni boshlang'ich nuqtaga qaytarish imkonsiz bo'lsa, chiqishda \(-1\) ni chop eting. Aks holda, Robotni qaytarish uchun minimal manipulyator ishlatish sonini chop eting.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
RRU |
-1 |
2 |
UDUR |
1 |
D. Robot muhandissi
Xotira: 32 MB, Vaqt: 1000 msUzoq kelajakda siz robotni dasturlash bo'yicha yetakchi muhandissiz. Sizga yangi vazifa topshirildi.
Robotga berilgan butun son \(n\) ni shunday bo'laklarga ajratish kerakki, u bo'laklar raqamlari faqat \(0\) va \(1\) 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 \(n\) ni imkon qadar minimal bo'laklar soniga ajratishingiz kerak.
Bo'laklash shartlari:
- Robot bo'laklarni yig'ib, sonni qayta tiklay olishi kerak \(a_1+a_2+...+a_k=n\).
- Har bir bo'lak \(a_i\) faqat \(0\) va \(1\) raqamlaridan tashkil topgan son (masalan, \(1,10,11,100,...\)) bo'lishi kerak. Boshqa raqamlar (masalan, \(2,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.
Kirish faylining yagona satrida \(n(1\leq n\leq 10^6)\) butun soni beriladi.
Chiqish faylining dastlabki satrida minimal \(k\) sonini chop eting, kiyingi satrda probil bilan ajratilgan holda \(a_1,a_2,...,a_k\) ni chop etasiz. Agar bir nechta yechim mavjud bo'lsa ulardan birini chop etishingiz mumkun.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
4 |
4 1 1 1 1 |
2 |
21 |
2 10 11 |
E. Yangi qavslar
Xotira: 32 MB, Vaqt: 1000 msQavslar 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 \(n\) ta ochiluvchi va yopiluvchi qavslardan tashkil topgan \(s\) 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:
- Chizishda qavslarning balandligi minimal bo'lishi kerak.
- Qavslar orasida faqat bitta bo'sh joy qoldiring, birlashib ketmasligi uchun.
- 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.
Kirish faylining dastlabki satrida \(n(2\leq n\leq 1000)\) juft butun soni beriladi. Kiyingi satrda muvozanatlashgan \(s\) satr beriladi. Berilgan satr faqat \([\) va \(]\) qavslardan tashkil topgan. Satrning muvozanatliligi kafolatlanadi.
Chiqish faylida masalaning yechimini chop eting ortiqcha belgilarsiz.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
6 [[][]] |
+- -+ |+- -++- -+| || || || |+- -++- -+| +- -+ |
2 |
6 [][[]] |
+- -++- -+ | ||+- -+| | ||| || | ||+- -+| +- -++- -+ |
F. Chigirtkalar ligasi
Xotira: 45 MB, Vaqt: 1000 msTasavvur qiling, “Chigirtkalar Ligasi” bo‘lib o‘tmoqda. Uzunligi \(m\) 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 \(n\) ta chigirtka joylashgan bo‘lib, ularning har biri poyga boshida \(s_i\) pozitsiyada turibdi va \(d_i \in [L, R]\) yo'nalishda bir vaqtda barcha chigirtka harakatni boshlaydi. Pozitsiyalar soat strelkasiga qarama-qarshi yo‘nalishda \(1\) dan \(m\) gacha raqamlangan.
Biroq bu oddiy poyga emas! Aylana ustida maxsus qoidalar amal qiladi:
- 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).
- Agar bir vaqtning o‘zida bir nechta to‘qnashuvlar yuz bersa, barchasi bir vaqtda o'z yo'nalishini qarama-qarshisiga o'zgartiradi.
- Harakat davomida chigirtka \(1\) pozitsiyadan o‘tganda \(m\) pozitsiyaga qaytadi, va aksincha.
Sizning vazifangiz poyga \(t\) birlik vaqt o‘tgach, har bir chigirtkaning yakuniy pozitsiyasini aniqlang.
Kirish faylining dastlabki satrida \(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 \(n\) ta satrda \(s_i,d_i(1\leq s_i \leq m, d_i\in [L,R])\) mos ravishda \(i-\)chigirtka joylashgan pozitsiya va chigirtka yo'nalishi. \(L\) va \(R\) mos ravishda soat yo'nalishi bo'yicha va soat miliga teskari yo'nalishga mos keladi.
Chiqish faylida \(t\) vaqt birligidan so'ng, dastlabki chigirtkadan boshlab oxirgi chigirtkagacha barcha pozitsiyalarni bitta satrda probil bilan ajratilgan holda chop eting.
# | 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 msSizga ikkilik sanoq sistemasidagi \(s\) satr beriladi. Siz ushbu satr ustida quyidagi ikki amalni istalgancha bajarishingiz mumkun:
- \(s\) satrning istalgan \([l,r]\) oralig'ini teskarisiga aylantirishingiz mumkun, faqat \(x\) energiya sarf qilasiz. Misol \(1\underline{011}001\rightarrow 1\underline{110}001\).
- \(s\) satrning istalgan \([l,r]\) oralig'idagi 1 larni 0 ga va 0 larni 1 ga almashtirishingiz mumkun, faqat \(y\) energiya sarf qilasiz. Misol \(1\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.
Kirish faylida ikkita \(x, y(0\leq x,y\leq 10^9)\) butun sonlari beriladi. Kiyingi qatorda \(s(1\leq |s| \leq 3000000)\) ikkilik satr beriladi.
Chiqish faylida masalaning yechimini chop eting.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
1 10 01000 |
11 |
2 |
10 1 01000 |
2 |
H. Satr ichidagi sarguzashtlar
Xotira: 32 MB, Vaqt: 1000 msSizga bir sirli satr \(s\) 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 \(q\) ta so'rov beriladi, har bir so'rov quyidagi ikki turdan biriga tegishli:
1-tur: “Belgini almashtirish”
So'rov \(1 \space{} i \space{} c \space{} -\) ko'rinishida berilsa \(s\) satrning \(i-\)pozitsiyadagi joylashgan belgini \(c\) ga almashtirish kerak.
2-tur: “Substring izlash”
So'rov \(2 \space{} l \space{} r \space{} y \space{} -\) ko'rinishida berilsa \(s_l + s_{l+1}+... +s_r\) satr ichida \(y\) 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”).
Kirish faylining dastlabki satrida \(s(1\leq |s|\leq 100000,s_i\in [a,b,...,z])\) satr beriladi.
Kiyingi satrda so'rovlar soni \(q(1\leq q\leq 100000)\) beriladi.
Kiyingi \(q\) ta satrda yuqorida aytib o'tilgan ikki turga mansub so'rovlar beriladi.
- \(1,i,c(1\leq i\leq |s|, c\in[a,b,...,z])\);
- \(2,l,r,y(1\leq l\leq r\leq |s|, 1\leq |y|\leq 10^5)\);
Barcha so'rovlar uchun \(|y|\) larning yig'indisi \(10^5\) dan oshmasligi kafolatlanadi
Chiqish faylida har bir ikkinchi turga mansub so'rovga javobni alohida satrlarda chop eting.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
ababababa 3 2 1 7 aba 1 5 c 2 1 7 aba |
3 1 |