A. Abdulla va Xo'jamurod

Xotira: 64 MB, Vaqt: 1000 ms

Masala

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.

Abdulla yurishni birinchi boshlaydi
Har bir ishtirokchi o'z navbatida massividan bitta son olib tashlaydi va navbatni boshqa ishtirokchiga beradi
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.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son, $N(1 \leq N \leq 5000)$ kiritiladi.

Ikkinchi qatorda $N$ ta butun son, $A$ massivi elementlari kiritiladi

Uchunchi qatorda $N$ ta butun son, $B$ massivi elementlari kiritiladi

Chiquvchi ma'lumotlar:

Ikkala o'yinchi ham optimal o'ynaganda, $|x-y|$ ning qiymatini toping.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 3 8 3 6 2	2
2	2 1 6 7 3	2

B. Ketma ketlik va oraliq

Xotira: 32 MB, Vaqt: 1000 ms

Masala

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.

Kiruvchi ma'lumotlar:

Yagona qatorda 3 ta bugun son kiritiladi.

$A, B \leq |10^{18}|, A \leq B, 0 \leq n \leq 10^{18}$

Chiquvchi ma'lumotlar:

Yagona qatorda bitta son, masala javobini chiqaring.

Izoh:

Namunaviy testlar o'rni sistemadagi testlar bilan bir xil emas.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	0 1 2	2
2	-5 0 10	5

C. Tog'lar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

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?

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - $N (1 \leq N \leq 2*10^5)$ , tog'lar sistemasidagi tog'lar soni kiritiladi.

Ikkinchi qatorda $N$ ta butun son - $a_i (0 \leq a_i \leq 10^9)$ sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir tog' uchun, undan ko'rsa bo'ladigan barcha tog'lar sonini probel bilan ajratib chop eting.

Izoh:

2 -testda Abdulaljon chapga qaraganda ko'ra oladigan to'glari:

1-tog'dan chapga qaraganda to'g ko'rinmaydi

2-tog'dan chapga qaraganda bitta to'g, 1-tog' ko'rinadi

3-tog'dan chapga qaraganda ikkita to'g, 2- hamda keyin 1- tog' ko'rinadi.

4-tog'dan chapga qaraganda bittagina to'g, 1-tog' ko'rinadi.

5-tog'dan chapga qaraganda ikkita to'g, 4-tog' hamda keyin 3-tog' ko'rinadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 2 3	2 2 1
2	5 3 1 4 2 5	3 3 4 2 2

D. Grid

Xotira: 32 MB, Vaqt: 1000 ms

Masala

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.

Kiruvchi ma'lumotlar:

Yagona qatorda $n$ va $m$ sonlari kiritiladi.

$n*m \leq 60$ ekanligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiroyli matritsalar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 1	2
2	2 2	7
3	2 3	17
4	3 1	5

E. Qism massivlarga ajratish

Xotira: 256 MB, Vaqt: 2000 ms

Masala

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!

Kiruvchi ma'lumotlar:

Birinchi qatorda $n$ va $m$ – mos ravishda massivnig uzunligi va Farrux bergan shartlar soni.

Keyingi qatorda $n$ ta elementdan iborat $a$ massiv elementlari.

Keyingi $m$ ta qatorning har birida ikkita butun son $(l, r)$ - shartlarning parametrlari kiritiladi.

Chiquvchi ma'lumotlar:

Birinchi qatorda minimal norozilik darajasini va massivning necha bo'lakka bo'linganligini $(k)$ ni chop eting.

Keyingi qatorda uzunligi $k$ ta elementdan iborat, optimal bo'linishni tasvirlovchi massivni chiqaring.

Shu massivni way deb olaylik.

$way[i]$ – $i$ -qismmassivning birinchi elementi indexiga teng bo'lsin.
$way[1] = 1$ va $way[i] > way[i - 1] (2 \leq i \leq k)$ bo'lsin

Agar optimal bo'lish bir nechta bo'lsa istalganini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 2 1 2 3 1 2 3 3	2 2 1 3
2	5 2 1 2 0 0 1 2 3 4 5	2 3 1 2 5
3	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

Masala

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.

Kiruvchi ma'lumotlar:

Yagona qatorda uzunligi $10^5$ dan oshmaydigan yagona $S$ satri kiritiladi.

Chiquvchi ma'lumotlar:

Masala javobini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	robo	-1
2	testroconbo	11
3	arobocontestb	11
4	fftroboclownnteskept	14