A. Tuxum biznesi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Shahriyor yaqinda tuxum biznesi haqida o'qib qoldi. Uyida bittagina tovug'i bor edi. Tovuq har kuni ertalab bitta tuxum qo'yadi va Shahriyor tuxumlarni yeb qo'yardi. U endi ertadan boshlab tovug'ining tuxumlarini bozorga sotishga qaror qildi. Bozordagi narxlar esa har kuni o'zgarib turadi. Shahriyorda tuxumning keyingi \(n\) kunlik narxlar jadvali bor va u shu kunlar davomida maksimal daromad topishni xohlaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n(1 \le n \le 10^5)\) natural son kiritiladi.
Ikkinchi qatorda har bir \(i\)-kun uchun bitta tuxumning \(C_i\) qiymatiga to'g'ri keladigan 1000 dan oshmaydigan \(n\) ta natural sonlar bo'sh joy bilan ajratilgan holda beriladi.

Chiquvchi ma'lumotlar:

Bitta butun son Shahriyor kelasi \(n\) kun ichida ishlay oladigan maksimal pul miqdorini chop etishingiz kerak.

Izoh:

1-testda 1 va 2-kuni tuxumlarni sotmaydi va 3-kuni 3 ta tuxumni 96 so'mdan 288 so'mga sotadi, 4 va 5-kunlik tuxumlarni 46 so'mdan 92 so'mga sotadi va jami 380 so'm daromad qiladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 73 31 96 24 46	380
2	10 1 2 3 4 5 6 7 8 9 10	100

B. O'zgacha Otlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Shaxmat doskasida 2 ta: Qizil va Yashil otlar yashaydi, va ular doskaning har yerida beparvo sakrab yurishardi. Bugun Yashil ot uchun muhim kun, ya'ni bugun uning tug'ilgan kuni! U tug'ilgan kunini yolg'iz nishonlash niyati yo'q va u buning uchun Qizil otni mehmonga chaqiradi. Ammo bu ajoyib rejani amalga oshirish uchun ular doskaning bitta katagida bo'lishlari kerak.

E'tibor bering! Qizil va Yashil shaxmat otlari qora va oqdan juda farq qiladi:

ular navbatma-navbat emas, balki bir vaqtning o'zida harakat qilishadi
agar ular bitta katakka tushib qolsa, hech kim hech kimni yemaydi

Bayramdan zavqlanish uchun ular minimum nechtadan harakat qilishlari kerak?

Kiruvchi ma'lumotlar:

Bir qatorida probel bilan ajratilgan holda ikkita so'z - standart shaxmat qoidalariga muvofiq tarzda otlarning koordinatalari beriladi. Har bir so'z quyidagilardan iborat:

a dan h gacha bo'lgan bitta kichik harf
1 dan 8 gacha bitta raqam

Chiquvchi ma'lumotlar:

Bitta butun son - masala yechimini chiqaring. Agar buning iloji bo'lmasa -1 chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	f4 g5	1
2	a7 b3	-1

C. Labirintdagi Xazina

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bolek va Lolek ni hamma yaxshi tanisa kerak. Tinib tinchimas sayohatchilarning qo'liga yashirin xazinaning xaritasi tushib qoldi. Xaritada labirint tasvirlangan bo'lib, Labirint \(n×m\) o'lchamda va atrofi devor bilan o'ralgan, unga kirish eshiklari tepadagi ikki burchakda. Dastlab aka-uka chizmani yaxshilab o'rganishdi va labirint tomon yo'lga tushishdi. Bolek o'zini aqlli deb bilgani uchun xazinani bo'lishib olishga ko'nmay janjallashdi va ikkalasi xazinani ikki tomondan izlashga qaror qildi. Lolek birinchi eshikdan kirib labirintning yuqori chap burchagidan, Bolek esa ikkinchi eshikdan kirib labirintning yuqori o'ng burchagidan yurishni boshlaydi. Ularning tezliklari bir xil bo'lib, siz xazinaga kim birinchi bo'lib borishini va aka-uka xazinagacha qancha yo'l bosishini aniqlashingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\), \(m\)\((4 \le n,m \le 2*10^3)\) mos ravishda labirint bo'yi va eni kiritiladi. Keyingi \(n\) ta qatorda \(m\) tadan belgi kiritiladi. «#» - devor, «.» - bo'sh joy, «X» xazina turgan joyni anglatadi. Tushunish uchun Izoh ga qarang.

Chiquvchi ma'lumotlar:

Birinchi qatorda Lolek va Bolek ning xazinaga yetib borgunicha minimum qancha masofa bosishi kerakligini probel bilan ajratib chiqaring. Ikkinchi qatorda g'olibning ismini, agar ikkisi bir vaqtda yetib borsa Draw! deb chiqaring.

Izoh:

Birinchi testda yurishlar taxminan mana shunday bo'ladi:

############
#L++#..+++B#
#..+++.+##.#
#..#.+++..##
###.##+###.#
#....#++.#.#
#..##.#X#..#
############

to'q sariq rangda Labirint eshiklari
qizil rangda Lolekning taxminiy marshruti
yashil rangda Bolekning taxminiy marshruti
L va B Lolek va Bolekning dastlabki nuqtalari belgilangan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	8 12 ############ #...#......# #.......##.# #..#......## ###.##.###.# #....#...#.# #..##.#X#..# ############	11 10 Bolek

D. Rabin- Karp

Xotira: 512 MB, Vaqt: 2000 ms

Masala

Rabin - Karp algoritmini urganish jarayonida qiziq bir narsa meni o'ylantirib qoldi. Sizga inglizcha harflardan iborat s satr beriladi. s satrni Pastki qator(substring)\(s[l...r](1 \leq l \leq r \leq \vert s \vert)\) larida yomon deb berilgan harflar soni ko'pi bilan k ta bo'lganlari sonini toping.
Agar 2 ta \(s[x...y] ≠ s[p...q]\) bo'lmasa ular har xil hisoblanadi, yani mano jihatidan bir xil bo'lmasligi kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda s satr uzunligi 1500 dan oshmaydi.
Ikkinchi qatorda 26 ta harf uchun yaxshi yoki yomon ekanini belgilovchi '0' va '1' lardan iborat satr kiritiladi('0' bo'lsa yomon , '1' bo'lsa yaxshi).
Ohirgi qatorda k(\(0 \leq k \leq |s|\)) butun son kiritiladi.

Chiquvchi ma'lumotlar:

Berilgan shartni qanoatlantiruvchi satrlar sonini toping.

Izoh:

1-Test uchun: Berilgan shartlarni qanoatlantiruvchi satrlar "a", "aa", "ac", "b", "ba", "c", "ca", "cb".

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	acbacbacaa 00000000000000000000000000 2	8

E. Vaqt

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga biror vaqtni beraman shu vaqtda t minut o'tgandan keyingi vaqtni ayting. 24 soatlik vaqt haqida malumotga ega bo'lmasangiz: link.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(hh:mm\) formatidagi biror vaqt(\(0 \leq hh < 24, 0 \leq mm < 60\)).
Ikkinchi qatorda t(\(0 \leq t \leq 10^4\)) butun son kiritiladi.

Chiquvchi ma'lumotlar:

Hosil bo'lgan vaqtni \(hh:mm\) ko'rinishida chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10:10 0	10:10
2	23:59 10	00:09

F. Riemann sum

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Quvonchbek Matematikani yaxshi bilganligi sababli bu ifodalarni qiyinchiliksiz sodalashtira oldi.

\(\Sigma_{i=1}^{n}i = 1 + 2 + 3 + ... + n = \frac{n*(n+1)}{2}\)
\(\Sigma_{i=1}^{n}i^2 = 1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n*(2n+1)*(n+1)}{6}\)
\(\Sigma_{i=1}^{n}i^3 = 1^3 + 2^3 + 3^3 + ... + n^3 = (\frac{n*(n+1)}{2})^2\)

Lekin bir qiyinroq misol berilganda u yechishda biroz qiynalmoqda, siz

\(\Sigma_{i=1}^{n}i^k = 1^k + 2^k + 3^k + ... + n^k\)

ushbu ifodani qiymatini topishda yordam bering.

Kiruvchi ma'lumotlar:

n va k (\(1 \leq n \leq 10^9, 0 \leq k \leq 10^6\)) butun sonlari 1 qatorda kiritiladi.

Chiquvchi ma'lumotlar:

Berilgan ifodani qiymati hisoblang, bu qiymat katta bo'lib ketganligi sababli \(10^9+7\) ga bo'lgandagi qoldiqni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3	100

G. Funksiya #1

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga \(f(x) = -1 + 2 - 3 + 4 +... +-1^x*x\) funksiya beriladi. Ushbu funksiyani \(x=n\) dagi qiymatini toping.

Kiruvchi ma'lumotlar:

n(\(1 \leq n \leq 10^{15}\)) butun soni kiritiladi.

Chiquvchi ma'lumotlar:

\(f(n)\) ni qiymatini toping.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4	2