A. Yo'l ustida

Xotira: 32 MB, Vaqt: 1000 ms

Siz hozirgina yo'lning har ikki tomonida \(n\) ta bir xil uylar joylashgan mukammal tekis ko'chaga ko'chib o'tdingiz. Tabiiyki, ko'chaning narigi tomonidagi odamlarning uy raqamini bilishni xohlaysiz. Ko'cha shunday ko'rinadi:

 1 |       | 6

 3 |       | 4

 5 |       | 2

      you     

 

O'ng tomonda tenglik kuchayadi; chap tomonda koeffitsientlar kamayadi. Uy raqamlari 1 dan boshlanadi va bo'shliqlarsiz ko'payadi. n = 3 bo'lsa, 1 6 ga qarama-qarshi, 3 ta 4 ga qarama-qarshi va 5 ta 2 ga qarama-qarshi bo'ladi.

1 3

6

3 3

4

B. Shifrlash

Xotira: 32 MB, Vaqt: 1000 ms

1-qadam: Berilgan qatordagi barcha kichik unlilarni quyidagi naqshga muvofiq raqamlar bilan almashtirish uchun encode() funksiyasini yarating:

a -> 1
e -> 2
i -> 3
o -> 4
u -> 5

Masalan, encode("salom") "h2ll4" ni qaytaradi. Bu kata katta unlilar haqida tashvishlanishga hojat yo'q.

2-qadam: Endi yuqorida ko'rsatilgan naqsh bo'yicha raqamlarni unlilarga aylantirish uchun decode() nomli funktsiyani yarating.

Masalan, decode("h3 th2r2") "salom u erda" ni qaytaradi.

Oddiylik uchun siz funktsiyaga kiritilgan har qanday raqamlar unlilarga mos keladi deb taxmin qilishingiz mumkin.

encode
hello

h2ll4

decode
h2ll4

hello

C. Vektor yaqinligi

Xotira: 32 MB, Vaqt: 1000 ms

Har bir vektorda bir xil indeksda, bir xil qiymatga ega bo'lgan vektordagi elementlar sonini hisoblang.

([1 2 3 4 5], [1 2 2 4 3]) => 0.6
([1 2 3], [1 2 3]) => 1.0
Yaqinlik qiymati 0,0 dan 1,0 gacha bo'lgan shkalada amalga oshirilishi kerak, 1,0 mutlaqo bir xil. Ikkita bir xil to'plam har doim 1,0 yaqinlik darajasiga ega deb baholanishi kerak.

Maslahat: Oxirgi misol sinov ishi yaqinlikni to'g'ri hisoblash uchun muhim ma'lumotga ega.

1 2 3
1 2 3 4 5

3/5

1 2 3
1 2 3

1

D. Ikki marta chiziqli

Xotira: 32 MB, Vaqt: 1000 ms

U quyidagi tarzda aniqlangan u ketma-ketligini ko'rib chiqing:

u(0) = 1 soni u dagi birinchi raqamdir.

U dagi har bir x uchun y= 2 * x + 1 va z = 3 * x + 1 u ichida ham bo'lishi kerak.

u ichida boshqa raqamlar yo'q.

Masalan: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1 3 va 4 ni beradi, keyin 3 7 va 10 ni, 4 9 va 13 ni beradi, keyin 7 15 va 22 ni beradi va hokazo...

 

Berilgan n parametrga ega dbl_linear (yoki dblLinear...) funksiyasi tartiblangan (< bilan) u ketma-ketligining u(n) elementini qaytaradi (demak, dublikatlar yo‘q).

10

22

20

57

E. Freak Contaz Sequence

Xotira: 32 MB, Vaqt: 1000 ms

Freak Contaz Sequence - bu Collatz butun sonlar ketma-ketligining yana bir versiyasi bo'lib, a(1) dan quyidagi tarzda olinadi:

a(n + 1) = a(n) / 3, agar a(n) 3 ga boʻlinsa.
Biz buni katta pastga qadam sifatida belgilaymiz, "D".

a(n + 1) = (4 * a(n) + 2) / 3, agar a(n) 3 ga bo'linganda 1 qoldiq bo'lsa.
Biz buni yuqoriga qadam sifatida belgilaymiz, "U".

a(n + 1) = (2 * a(n) - 1) / 3, agar a(n) 3 ga bo'linganda 2 ning qoldig'i chiqadi.
Biz buni kichik pastga qadam sifatida belgilaymiz, "d".
Ba'zi k uchun a(k) = 1 bo'lganda ketma-ketlik to'xtaydi.

Har qanday butun sonni hisobga olgan holda, biz qadamlar ketma-ketligini sanab o'tishimiz mumkin:

Misol uchun, agar a(1) = 231 bo'lsa, {an} = {231,77,51,17,11,7,10,14,9,3,1} ketma-ketligi "DdDddUUdDD" bosqichlariga mos keladi.

Albatta, xuddi shu "DdDddUUdDD...." ketma-ketligi bilan boshlanadigan boshqa ketma-ketliklar ham bor.

Misol uchun, agar a = 1004064 bo'lsa, u holda ketma-ketlik "DdDddUUdDDDdUDUUUdDdUUDDDUdDD" bo'ladi.

Sizning vazifangiz N > 1 bo'lgan eng kichik musbat sonni topishdir, shunda ketma-ketlik s qatoridan boshlanadi. Ya'ni, agar s = "DdDddUUdDD" bo'lsa, natija 1004064 o'rniga 231 bo'lishi kerak.

Eslatma: a(1) = 1 uchun ketma-ketlik darhol tugaydi va 0 uzunlikdagi satr qaytariladi!

ddDddUDUDUDUddDUUUdd

1883021696

DdDddUUdDD

231

D

3

U

4

F. Quvurlarni tuzating

Xotira: 32 MB, Vaqt: 1000 ms

Ushbu kataning maqsadi suv quvurlari tarmog'ining biron bir joyda oqayotganligini tekshirishdir.

Vazifa
Xarita kiritishni qabul qiladigan va suvning biror joydan sizib chiqayotganligini tekshiradigan funksiya yarating. Agar suv oqayotgan bo'lsa, noto'g'ri qaytaring. Agar quvur tarmog'i to'g'ri bo'lsa, ya'ni hech qanday joyda oqish yo'q bo'lsa, rostni qaytaring.

Bir nechta suv manbalari bo'lishi mumkin. Xaritadan tashqariga yo'naltirilgan barcha quvurlar suv manbaiga ulangan va siz ularni oqish uchun tekshirishingiz kerak.

....
.┛┛.
....

YES

...┏
┃..┃
┛..┣

NO

G. To'rtburchaklar bilan qoplangan umumiy maydon

Xotira: 32 MB, Vaqt: 1000 ms

Ushbu Masalani bajarish uchun sizning vazifangiz to'rtburchaklar birlashmasi bilan qoplangan maydonni hisoblaydigan funktsiyani yozishdir.
To'rtburchaklar bo'sh bo'lmagan kesishmalarga ega bo'lishi mumkin, shu tarzda oddiy yechim: Sall = S1 + S2 + ... + Sn-1 + Sn (bu erda n - to'rtburchaklar miqdori) ishlamaydi.

Old shartlar
har bir to'rtburchak quyidagicha ifodalanadi: [x0, y0, x1, y1]
(x0, y0) - pastki chap burchakning koordinatalari
(x1, y1) - yuqori o'ng burchakning koordinatalari
xi, yi - musbat butun sonlar yoki nollar (0, 1, 2, 3, 4..)
to'rtburchaklar tomonlari koordinata o'qlariga parallel
sizning kiritilgan ma'lumotlaringiz to'rtburchaklar qatoridir
Talablar
Bitta testdagi to'rtburchaklar soni (oddiy testlarni hisobga olmaganda) 3000 dan 15000 gacha. Bunday diapazonga ega 10 ta test mavjud. Shunday qilib, sizning algoritmingiz optimal bo'lishi kerak.
To'rtburchaklar o'lchamlari 1e6 kabi qiymatlarga yetishi mumkin.

0 4 11 6

22

0 0 1 1
1 1 2 2

2

3 3 8 5
6 3 8 9
11 6 14 12

36