A. Abdulla va Xo'jamurod

Xotira: 64 MB, Vaqt: 1000 ms

Abdulla va Xo'jamurodning har birida bittadan massiv bor va ular shu massivlar yordamida o'yin o'ynashmoqchi. Abdullada \(A\) massiv Xo'jamurodda esa \(B\) massiv. Ikkala massivning uzunligi \(n\) ga teng va ikkala massiv ham \([-10^9, 10^9]\) oraliqdagi butun sonlardan tashkil topgan. O'yin qoidalari quyidagicha.

1. Abdulla yurishni birinchi boshlaydi
2. Har bir ishtirokchi o'z navbatida massividan bitta son olib tashlaydi va navbatni boshqa ishtirokchiga beradi
3. Ikkala massivda ham bittadan element qolganda, o'yin tugaydi.

Shu qolgan elementlarni mos ravishda \(x\) va \(y\) desak, Abdullaning maqsadi \(|x-y|\) qiymatini maksimallashtirish, Xo'jamurodning vazifasi esa bu qiymatni minimallashtirish.

Ikkisi ham optimal o'ynaganda, \(|x-y|\) ning qiymatini toping.

3
1 3 8 
3 6 2

2

2
1 6 
7 3

2

B. Ketma ketlik va oraliq

Xotira: 32 MB, Vaqt: 1000 ms

Vaqt kam, masala shartini tezroq yozish kerak. Shuning uchun ham Valijon yoki Asilbek yoki yana kimdir bilan bog'liq hikoyani o'zingiz o'ylab toping.

Sizda \([A,B]\) oraliq hamda maxsus ketma-ketlik bor.

Maxsus ketma-ketlikning \(i-\)hadi formulasi quyidagicha

\[\frac{(-1)^i(i-1)}{(i-1)!}\]

Xususan ketma ketlik quyidagicha ko'rinishda: \([0, 1, -1, 1/2, -1/6, \ ...]\)

Siz shu ketma ketlikning birinchi \(n\) ta hadidan nechtasi berilgan oraliqda joylashganligini topishingiz lozim.

0 1 2

2

-5 0 10

5

C. Tog'lar

Xotira: 32 MB, Vaqt: 1000 ms

Abdullajon bugun tog'ga chiqishga qaror qildi.

Tog' sistemasi bir qator to'g'lardan iborat to'glardan iborat. Bunda \(i\)-to'g balandligi \(a_i\) ga teng.

Agar Abdulla hozir \(i\)-tog' ustida tugan bo'lsa

• Chapga qaraganda u faqat oldingi tog'larning barchasidan balandroq bo'lgan tog'larni ko'radi (yaqinidan uzog'idagi tartibda).
• O'ngga qaraganda u faqat keyingi tog'larning barchasidan balandroq bo'lgan tog'larni ko'radi (yaqinidan uzog'idagi tartibda).

Abdullajon har bir tog'ga chiqqanida, jami nechta boshqa tog'larni ko'ra oladi?  

3
1 2 3

2 2 1

5
3 1 4 2 5

3 3 4 2 2

D. Grid

Xotira: 32 MB, Vaqt: 1000 ms

Matritsa chiroyli deyiladi, agar u faqatgina ‘0’ va ‘1’ elementlaridan tashkil topgan bo'lsa hamda matritsada qo'shni ‘1’ elementlar mavjud bo'lmasa.

Sizga ikkita \(n (1 \leq n \leq 8)\) va \(m (1 \leq m \leq 60)\) sonlari beriladi.

Sizning vazifangiz,  o'lchovi \(n \times m\) bo'lgan chiroyli matritsalar sonini sanashdir. 

1 1

2

2 2

7

2 3

17

3 1

5

E. Qism massivlarga ajratish

Xotira: 256 MB, Vaqt: 2000 ms

Sardorda  \(n\) ta butun sondan iborat \(a\) massiv bor \((0 \leq a[i] \leq 20, 1 \leq n \leq 10^5)\) . Sardor massivni bir nechta uzluksiz va o'zaro kesishmaydigan qism massivlarga ajratmoqchi, boshqacha so'zlar bilan aytganda har bir element aynan bitta qism massivda bo'lishi va har bir qism massiv kamida 1 ta elementdan iborat bo'lishi lozim.

Uning do'sti Farrux ajratilgan har bir qism massivning faqat birinchi elementiga qiziqadi, va uning norozilik darajasi ushbu qism massivlarning turli xil birinchi elementlarining soniga teng (turlilar soni).

Bundan tashqari, Farrux Sardoga \(m\) ta \((1 \leq m \leq 10^5)\) shart bergan:

• Har bir shart \(l\) va \(r\) \((1 \leq l \leq r \leq n )\) qiymatlaridan iborat  – shu \(l\) va \(r\) oraliqdagi birorta elementdan boshlangan kamida 1 ta qism massiv bo'lishi kerak.

Sardor Farruxning noroziligini minimallashtiradigan va barcha \(m\) ta shartlarni qanoatlantiradigan qism-massivlarga bo'lish usulini topishi kerak.  Unga yordam bering!

 

3 2
1 2 3
1 2
3 3

2 2
1 3

5 2
1 2 0 0 1
2 3
4 5

2 3
1 2 5

5 5
1 2 0 0 1
1 1
2 2
3 3
4 4
5 5

3 5
1 2 3 4 5

F. Robocontest

Xotira: 64 MB, Vaqt: 1250 ms

Valijon Robocontest platformasida masala ishlashni juda yoqtiradi, ayniqsa rated roundlarni sevadi. Ammo anchadan beri rated roundlar bo'lmay qo'ygani sababli Valijon Robocontest platformasi adminlaridan rated kontest qo'yishni so'radi.

Adminlar Valijonga vazifa berdilar, agar Valijon vazifani bajarsa, keyingi rated round tezroq kelishiga ishontirishdi. Vazifa esa quyidagicha

\(S\) satri mavjud. Undagi shunday eng kichik qism satr uzunligini topingki, shu qism satrda mavjud harflardan ‘robocontest’ so'zini yasashning iloji bor bo'lsin! Agar to'liq satrda ham ‘robocontest’ so'zini yasash uchun yetarlicha harflar bo'lmasa, -1 chiqaring.

robo

-1

testroconbo

11

arobocontestb

11

fftroboclownnteskept

14