A. Ideal qator

Xotira: 32 MB, Vaqt: 1000 ms

Sizga $n$ natural son berilgan. Siz shunday $a_1,a_2,...,a_n$ qatorni hosil qilingki ushbu qator ideal bo'ladi quyidagi shartlarga javob bersa:

• $1\leq a_i \leq 1000$ bu yerda $1\leq i \leq n$;
• $a_i$ ga qoldiqsiz bo'linadi $i$ bu yerda $1\leq i \leq n$;
• $a_1+a_2+...+a_n$ ga qoldiqsiz bo'linadi $n$. 

 

3
4
2
5

2 8 6 4
2 4
3 4 9 4 5

B. Satrni ikkiga bo'lish

Xotira: 32 MB, Vaqt: 1000 ms

$f(x)$ - bu funksiya $x$ satrning turli belgilar soniga teng qiymatni hisoblaydi. Masalan: $f(abc)=3,f(aaaa)=1$ va $f(abcabcd)=4$.

Sizga $s$ satr beriladi, sizning vazifangiz bo'sh bo'lmagan shunday ikkita $a$ va $b$ satrlarga ajratingki $f(a)+f(b)$ ning qiymati maksimal bo'lsin(bu yerda $a+b=s)$.

4
5
aaaaa
7
abcabcd
11
robocontest
4
aaab

2
7
9
3

C. Hoshimjon va do'stlari #1

Xotira: 32 MB, Vaqt: 2000 ms

Hoshimjon uyiga $n$ ta do'stini taklif qildi. Stol atrofidagi o'rindiqlar $1,2,...,n$ tartibda raqamlangan bo'lib Hoshimjonning do'stlari o'rindiqlarga joylashib olishdi. 

Unda jami $m$ ta bir birini tanimaydigan jufliklar ro'yxati mavjud. Ushbu ro'yxatga kiritilmagan har qanday juftlik do'stlar bir birini taniydi. Siz shunday $[a,a+1,a+2,...,b](1\leq a\leq b\leq n)$ segmintlarni topingki ushbu segmintdagi barcha do'stlar bir birini tanisin, bunday segmintdagi do'stlar yaxshi do'stlar segminti hisoblanadi.

Sizning vazifangiz Hoshimjonning do'stlari joylashgan stolda jami bo'lib nechta yaxshi do'stlar segminti mavjudligini aniqlashdan iborat.

2
3 2
1 3
2 3
4 2
1 2
2 3

4
5

D. Hoshimjon va do'stlari #2

Xotira: 32 MB, Vaqt: 1000 ms

Hoshimjon uyiga $n$ ta do'stini taklif qildi. Stol atrofidagi o'rindiqlar $1,2,...,n$ tartibda raqamlangan bo'lib Hoshimjonning do'stlari o'rindiqlarga joylashib olishdi. 

Unda jami $m$ ta bir birini taniydigan jufliklar ro'yxati mavjud. Ushbu ro'yxatga kiritilmagan har qanday juftliklar bir birini tanimaydi. Siz shunday $[a,a+1,a+2,...,b](1\leq a\leq b\leq n)$ segmintlarni topingki ushbu segmintdagi barcha do'stlar bir birini tanisin, bunday segmintdagi do'stlar yaxshi do'stlar segminti hisoblanadi.

Sizning vazifangiz Hoshimjonning do'stlari joylashgan stolda jami bo'lib nechta yaxshi do'stlar segminti mavjudligini aniqlashdan iborat.

2
3 2
1 3
2 3
4 2
1 2
2 3

4
7

E. Max o'suvchi ro'yxat

Xotira: 32 MB, Vaqt: 1000 ms

Sizga $n$ ta elementdan tashkil topgan $a$ massiv beriladi.

$L(a)$ - bu funksiya $a$ massivning eng uzun ortib boruvchi ketma-ketligi uzunligini hisoblaydi. Masalan:

• $L([2,1,1,3]) = 2$ ketma-ketlik $[1,3]$;
• $L([7,2,9,1,11])=3$ ketma-ketlik $[7,9,11]$;
• $L([3,1,2,4])=3$ ketma-ketlik $[1,2,4]$.

Massivni $a'$ hisoblash uchun biz uni teskari tartibda joylashtirib chiqamiz, ya'ni $a'=[a_n,a_{n-1},...,a_1]$.

Sizning vazifangiz massivni istalgan tartibda elementlarini qayta tartibga solganingizdan so'ng $min(L(a),L(a'))$ ning qiymatini hisoblashdan iborat, faqat ushbu qiymat maksimal bo'lsin.

3
4
2 1 1 3
4
1 1 1 1
4
3 1 2 4

2
1
2

F. Shamlar

Xotira: 32 MB, Vaqt: 1000 ms

Sizda $n$ ta shamlar to'plami mavjud. Shamlar bitta satrda joylashgan bo'lib, yoniq turgan shamlar $1$ bilan, o'chik turgan shamlar esa $0$ bilan ifodalangan $a$ satr mavjud.

Sizda yana boshqa $n$ ta shamlar to'plami ham mavjud, ushbu shamlar to'plami $b$ satr. 

Siz $a$ satrdagi yonib turgan istalgan bir shamni tanlab olib shu satrdagi qolgan barcha yonib turgan shamlarni o'chirishingiz va o'chik turgan shamlarni yoqib chiqishingiz mumkun. Bu harakatni eng kam bajargan holda $a$ satrdagi shamlarni $b$ satrdagi shamlar ko'rinishiga keltirishingiz kerak.

4
5
11010
11010
2
01
11
3
000
101
9
100010111
101101100

0
1
-1
3