A. Ideal qator
Xotira: 32 MB, Vaqt: 1000 msSizga \(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\).
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 .
Chiqish faylida \(a_1,a_2,...,a_n\) ideal qatorni chop eting, agar bunday yechimlar bir nechta bo'lsa istalganini chop etishingiz mumkun.
# | 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\(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)\).
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.
Chiqish faylida har bir test uchun javobni alohida satrlarda chop eting.
# | 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 msHoshimjon 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.
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.
Chiqish faylida har bir testlar uchun javobni alohida satrlarda chop eting.
# | 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 msHoshimjon 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.
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.
Chiqish faylida har bir testlar uchun javobni alohida satrlarda chop eting.
# | 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 msSizga \(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.
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.
Chiqish faylida har bir test uchun masalani yechimini alohida satrlarda chop eting.
# | 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 msSizda \(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.
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.
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.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
4 5 11010 11010 2 01 11 3 000 101 9 100010111 101101100 |
0 1 -1 3 |