A. Ideal qator

Xotira: 32 MB, Vaqt: 1000 ms
Masala

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\)

 

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida \(t(1\leq t\leq 200)\) testlar soni beriladi. Kiyingi \(t\) ta satrda \(n(1\leq n\leq 200)\) qator uzunligi beriladi .

Chiquvchi ma'lumotlar:

Chiqish faylida \(a_1,a_2,...,a_n\) ideal qatorni chop eting, agar bunday yechimlar bir nechta bo'lsa istalganini chop etishingiz mumkun.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
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
Masala

\(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)\).

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrda testlar soni \(t(1\leq t\leq 1000)\) beriladi. Kiyingi satrlarda \(t\) ta test beriladi, har bir testning dastlabki satrda satr uzunligi \(n(2\leq n\leq 2000)\)va kiyingi satrda \(n\) ta belgi lotin alifbosining kichik harflaridan tashkil tashkil topgan \(s\) satr beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun javobni alohida satrlarda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
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
Masala

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.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrda testlar soni \(t(1\leq t\leq 20000)\) beriladi. Kiyingi satrlarda \(t\) ta test beriladi, har bir test uchun \(n,m(2\leq n\leq 100000,0\leq m\leq min(2n,n(n-1)/2))\)mos ravishda Hoshimjonning do'stlari soni va o'zaro bir birini tanimaydigan juftliklar(barcha testlar uchun \(t+m_i\leq 10^6, 1\leq i\leq t\)). Kiyingi \(m\) ta satrda \(u_i,v_i(1\leq u_i, v_i\leq n, u_i \neq v_i)\) o'zaro bir birini tanimaydigan juftliklar.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir testlar uchun javobni alohida satrlarda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
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
Masala

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.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrda testlar soni \(t(1\leq t\leq 20000)\) beriladi. Kiyingi satrlarda \(t\) ta test beriladi, har bir test uchun \(n,m(2\leq n\leq 100000,0\leq m\leq min(2n,n(n-1)/2))\)mos ravishda Hoshimjonning do'stlari soni va o'zaro bir birini taniydigan juftliklar(barcha testlar uchun \(t+m_i\leq 10^6, 1\leq i\leq t\)). Kiyingi \(m\) ta satrda \(u_i,v_i(1\leq u_i, v_i\leq n, u_i \neq v_i)\) o'zaro bir birini taniydigan juftliklar.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir testlar uchun javobni alohida satrlarda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
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
Masala

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.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrda \(t(1\leq t\leq 10^4)\) testlar soni beriladi. Kiyingi satrlarda sizga \(t\) ta test beriladi, har bir testning dastlabki satrda \(n(1\leq n\leq 10^5)\)massiv elementlari soni va kiyingi satrda \(n\) ta son \(a_1,a_2,...,a_n(1\leq a_i\leq 10^9)\) beriladi.

Barcha kiruvchi ma'lumotlar soni \(10^6\) dan oshmaydi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun masalani yechimini alohida satrlarda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
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
Masala

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.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida \(t(1\leq t\leq 10^4)\) testlar soni beriladi. Kiyingi satrlarda \(t\) ta test beriladi, har bir test uchun dastlabki satrda \(n(1\leq n\leq 10^5)\) har bir satrdagi shamlar soni va kiyingi ikki satrda uzunligi \(n\) ga teng bo'lgan \(a\) va \(b\) (\(0\) va \(1\) lardan tashkil topgan) satrlar beriladi.

Kiruvchi ma'lumotlar soni \(10^6\) oshib ketmasligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun masalani javobini alohida satrlarda chop eting agar \(a\) satrdan \(b\) satrni hosil qilish mumkun bo'lmasa \(-1\) ni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
4
5
11010
11010
2
01
11
3
000
101
9
100010111
101101100
0
1
-1
3
Kitob yaratilingan sana: 15-Nov-24 03:37