A. Muhammad yaxshi bola

Xotira: 256 MB, Vaqt: 50 ms
Masala

Muhammad do'stining tug'ilgan kuni uchun sovg'a tayyorlamoqda. Uning a degan massivda n ta raqam bor va sovg'asi bu raqamlarning ko'paytmasi bo'ladi. Muhammad yaxshi bola bo'lgani uchun eng katta ko'paytmani hosil qilmoqchi va bu maqsadda u o'zining bitta raqamiga aynan 1 qo'shmoqchi.

Savol: Muhammad eng katta ko'paytmani qanday hosil qilishi mumkin?

Kiruvchi ma'lumotlar:

Kirish

Birinchi qatorda bitta butun son t (1 ≤ t ≤ 10⁴) — test sinovlari soni beriladi.

Har bir test sinovi uchun:

  1. Birinchi qatorda bitta butun son n (1 ≤ n ≤ 9) — raqamlar soni beriladi.
  2. Ikkinchi qatorda n ta butun son aᵢ (0 ≤ aᵢ ≤ 9) — massivdagi raqamlar beriladi (bo'sh joy bilan ajratilgan).
Chiquvchi ma'lumotlar:

Chiqish

Har bir test sinovi uchun aynan bitta raqamga 1 qo'shib Muhammad hosil qilishi mumkin bo'lgan eng katta ko'paytmani chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
4
2 2 1 2
3
0 1 2
5
4 3 2 3 4
9
9 9 9 9 9 9 9 9 9
 
16
2
432
430467210

B. Ibodatning sevimli topshirig'i

Xotira: 256 MB, Vaqt: 50 ms
Masala

Ibodat bir satrni yozish uchun avval ushbu satrda mavjud bo‘lgan barcha harflarni o‘rganishi kerak.

Ibodat s qatori ko‘rinishida ifodalangan xabarni yozmoqchi. U sizdan ushbu xabarni yozish uchun minimal alfavit hajmi qancha bo‘lishi kerakligini so‘raydi.

Hajmi x bo‘lgan alfavit (1≤x≤26) faqat birinchi x ta lotin harflarini o‘z ichiga oladi. Masalan, hajmi 4 bo‘lgan alfavit faqat a, b, c va d belgilaridan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son t (1≤t≤1000) — testlar soni keltiriladi.

Har bir testning birinchi qatorda bitta butun son n (1≤n≤100) — satr uzunligi keltiriladi.

Har bir testning ikkinchi qatorda uzunligi nnn ga teng bo‘lgan kichik lotin harflaridan iborat s satri keltiriladi.

Chiquvchi ma'lumotlar:

Har bir test uchun bitta butun sonni chop eting — Ibodat xabarini yozishi uchun kerak bo‘lgan minimal alfavit hajmi.

Izoh:

Birinchi test holati uchun Atilla faqat a belgisini bilishi kerak, shuning uchun faqat a ni o‘z ichiga olgan hajmi 1 bo‘lgan alfavit yetarli.

Ikkinchi test holati uchun Atilla d, o, w, n belgilarini bilishi kerak. Ushbu belgilarni o‘z ichiga oladigan eng kichik alfavit hajmi 23 bo‘ladi (bunday alfavitni abcdefghijklmnopqrstuvw ko‘rinishida ifodalash mumkin).

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz
 
1
23
19
6
26

C. Matrix #1

Xotira: 256 MB, Vaqt: 50 ms
Masala

n × n o‘lchamdagi a jadvali quyidagicha aniqlangan:

  1. Birinchi qator va birinchi ustun faqat birlardan iborat, ya'ni:
    aᵢ,₁ = a₁,ᵢ = 1 barcha i = 1, 2, ..., n uchun.
  2. Jadvaldagi qolgan barcha elementlar o‘zidan yuqoridagi va chapdagi sonlarning yig‘indisiga teng, ya'ni:
    aᵢ,ⱼ = aᵢ₋₁,ⱼ + aᵢ,ⱼ₋₁.

Shu shartlar jadvaldagi barcha qiymatlarni aniqlaydi.

Sizga n soni berilgan. Ushbu jadvaldagi maksimal qiymatni aniqlashingiz kerak.

Kiruvchi ma'lumotlar:

Yagona qator — musbat n sonini o‘z ichiga oladi (1 ≤ n ≤ 10) — jadvaldagi qatorlar va ustunlar soni.

Chiquvchi ma'lumotlar:

Yagona qatorda — jadvaldagi maksimal qiymat bo‘lgan musbat m sonini chop eting.

Izoh:

2-testda ko'rinishi: 

{1, 1, 1, 1, 1}, 

{1, 2, 3, 4, 5},

{1, 3, 6, 10, 15},  

{1, 4, 10, 20, 35}, 

{1, 5, 15, 35, 70}.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1
 
1
2 
5
 
70

D. Uchlik

Xotira: 256 MB, Vaqt: 50 ms
Masala

Sizga n elementdan iborat massiv a berilgan. Har bir test holati uchun massivda kamida uch marta uchraydigan biror qiymatni chiqaring yoki agar bunday qiymat bo'lmasa, -1 ni chop eting.

Kiruvchi ma'lumotlar:
  1. Birinchi qatorda t (1 ≤ t ≤ 10⁴) — test holatlar soni beriladi.
  2. Har bir test holati uchun ikki qator:
    • Birinchi qatorda n (1 ≤ n ≤ 2⋅10⁵) — massiv uzunligi.
    • Ikkinchi qatorda massiv elementlari a1, a2, …, an (1 ≤ ai ≤ n) beriladi.

Umumiy holda, barcha test holatlari uchun n ning yig'indisi 2⋅10⁵ dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir test holati uchun:

  • Agar massivda kamida uch marta uchraydigan element bo'lsa, shu elementdan birinchisini chop eting.
  • Aks holda, -1 chop eting.
Misollar:
# INPUT.TXT OUTPUT.TXT
1 
7
1
1
3
2 2 2
7
2 2 3 3 4 2 2
8
1 4 3 4 3 2 4 1
9
1 1 1 2 2 2 3 3 3
5
1 5 2 4 3
4
4 4 4 4
 
-1
2
2
4
1
-1
4

E. Yangi yil sovg'asini tuzatish

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Sizda n ta sovg'a bor va siz ushbu sovg'alarni bolalarga berishni xohlaysiz. Albatta, hech kimni ranjitishni xohlamaysiz, shuning uchun barcha sovg'alar bir xil bo'lishi kerak. i-sovg'a ai dona konfet va bi dona apelsindan iborat.

Bitta yurishda siz quyidagilardan birini tanlashingiz mumkin (1 ≤ i ≤ n):

  1. ai ni 1 ga kamaytirish (ya'ni, i-sovg'adan 1 dona konfet yeyish).
  2. bi ni 1 ga kamaytirish (ya'ni, i-sovg'adan 1 dona apelsin yeyish).
  3. ai va bi ni bir vaqtning o'zida 1 ga kamaytirish (ya'ni, i-sovg'adan 1 dona konfet va 1 dona apelsin yeyish).

Shuni ta'kidlash kerakki, siz konfet yoki apelsinni ularning miqdori 0 bo'lgan holatda yeyolmaysiz (ai va bi 0 dan kichik bo'lmasligi kerak).

Yuqorida aytib o'tilganidek, barcha sovg'alar bir xil bo'lishi kerak. Bu degani, quyidagi ikkita shart bajarilishi kerak:

  • a1 = a2 = ⋯ = an
  • b1 = b2 = ⋯ = bn

(ai va bi ning teng bo'lishi majburiy emas).

Sizning vazifangiz — barcha sovg'alarni tenglashtirish uchun zarur bo'lgan minimal yurishlar sonini topishdir.

Kiruvchi ma'lumotlar:

Dastlabki qatorda bitta butun son t (1 ≤ t ≤ 1000) — testlar to'plami soni beriladi. Keyin esa t ta testlar to'plami keltiriladi:

  • Har bir test uchun birinchi qatorda bitta butun son n (1 ≤ n ≤ 50) — sovg'alar soni.
  • Ikkinchi qatorda n ta butun son a1, a2, ..., an (1 ≤ ai ≤ 10⁹) — har bir sovg'adagi konfetlar soni.
  • Uchinchi qatorda n ta butun son b1, b2, ..., bn (1 ≤ bi ≤ 10⁹) — har bir sovg'adagi apelsinlar soni.
Chiquvchi ma'lumotlar:

Har bir test uchun bitta butun son chiqaring: sovg'alarni tenglashtirish uchun zarur bo'lgan minimal yurishlar soni.

Izoh:

Birinchi test to'plamida biz quyidagi yurishlar ketma-ketligini bajarishimiz mumkin:

  1. Birinchi sovg'ani tanlab, undan bitta apelsin yeyish, shunda a = [3, 5, 6] va b = [2, 2, 3] bo'ladi.
  2. Ikkinchi sovg'ani tanlab, undan bitta konfet yeyish, shunda a = [3, 4, 6] va b = [2, 2, 3] bo'ladi.
  3. Ikkinchi sovg'ani yana bir marta tanlab, undan bitta konfet yeyish, shunda a = [3, 3, 6] va b = [2, 2, 3] bo'ladi.
  4. Uchinchi sovg'ani tanlab, undan bitta konfet va bitta apelsin yeyish, shunda a = [3, 3, 5] va b = [2, 2, 2] bo'ladi.
  5. Uchinchi sovg'ani yana bir marta tanlab, undan bitta konfet yeyish, shunda a = [3, 3, 4] va b = [2, 2, 2] bo'ladi.
  6. Uchinchi sovg'ani yana bir marta tanlab, undan bitta konfet yeyish, shunda a = [3, 3, 3] va b = [2, 2, 2] bo'ladi.
Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
3
3 5 6
3 2 3
5
1 2 3 4 5
5 4 3 2 1
3
1 1 1
2 2 2
6
1 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1
3
10 12 8
7 5 4
 
6
16
0
4999999995
7

F. Konfetlar

Xotira: 256 MB, Vaqt: 2000 ms
Masala

Alisa va Bob ota-onalaridan n ta konfet sovg'a olishdi. Har bir konfetning og'irligi faqat 1 gramm yoki 2 gramm bo'lishi mumkin. Endi ular barcha konfetlarni o'zaro halol taqsimlashni xohlashadi, shunda Alisaning konfetlarining umumiy og'irligi Bobning konfetlarining umumiy og'irligiga teng bo'ladi.

Sizdan so'raladi: ular buni amalga oshira olishadimi?

Muhim: konfetlarni bo'laklarga bo'lish taqiqlangan.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son t (1 ≤ t ≤ 10⁴) — testlar to'plami soni berilgan.
Keyingi qatorlarda har bir test uchun quyidagilar beriladi:

  • Birinchi qatorda bitta butun son n (1 ≤ n ≤ 100) — Alisa va Bob olgan konfetlar soni.
  • Keyingi qatorda n ta butun son a1, a2, ..., an — konfetlar og'irligi. Har bir og'irlik faqat 1 yoki 2 ga teng.

Garantiya: barcha testlar bo'yicha n lar yig'indisi 10⁵ dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda quyidagilarni chiqaring:

  • Agar barcha konfetlarni teng og'irlikka ega ikkita to'plamga bo'lish mumkin bo'lsa, "YES" deb yozing.
  • Aks holda, "NO" deb yozing.
Izoh:

Birinchi kirish to'plamida Alisa va Bob har biri o'ziga bitta konfet olishlari mumkin, shunda ikkala tomonning og'irligi 1 bo'ladi.

Ikkinchi kirish to'plamida har qanday bo'linish adolatsiz bo'ladi.

Uchinchi kirish to'plamida Alisa va Bob har biri o'ziga bitta 1 gramm va bitta 2 gramm konfet olishlari mumkin, shunda ikkala tomonning og'irligi teng bo'ladi.

To'rtinchi kirish to'plamida uchta bir xil konfetni ikki kishi o'rtasida teng bo'lishning imkoni yo'q.

Beshinchi kirish to'plamida har qanday bo'linish ham adolatsiz bo'ladi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
2
1 1
2
1 2
4
1 2 1 2
3
2 2 2
3
2 1 2
 
YES
NO
YES
NO
NO

G. Musobaqa

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Yarim ochiq g'ildirakli Formula-A avtomobil poygalari bo'yicha jahon chempionati navbatdagi bosqichidan so'ng, poygachilar natijalarni muhokama qilish uchun bir kafega yig'ilishdi. Ular yoshligida katta avtomobillarda emas, balki kichikroq o‘lchamdagi kartlarda musobaqalashganlarini eslashdi.

Do‘stlar kart poygasining birida g‘olibni aniqlashga qaror qilishdi. Poyganing g‘olibi deb trassadagi barcha aylanishlarni eng kam vaqt ichida bosib o‘tgan poygachi hisoblanadi.

Natijalar yozuvlari saqlanmaganligi sababli, har bir n nafar poygachi o‘sha poygada trassaning m ta aylanishidagi natijalarini yoddan chiqib, qayd qilib berdi. Ammo ushbu ma’lumotlar asosida poygachilar g‘olibni topish qiyin deb topishdi. Shu sababli ular bu vazifani sizdan so‘rashdi.

Sizdan ushbu kart poygasining g‘olibini aniqlaydigan dastur yozish talab etiladi.

Kiruvchi ma'lumotlar:

INPUT.TXT faylining birinchi qatorida ikkita butun son berilgan: n va m (1 ≤ n, m ≤ 100). Keyingi 2∙n qatorda har bir poygachining trassani bosib o‘tish natijalari tasvirlangan. Poygachining trassani bosib o‘tishi quyidagicha tasvirlanadi:

  1. Birinchi qator – poygachining ismi (faqat kichik va katta lotin harflari ishlatiladi). Barcha ismlar turlicha, katta va kichik harflar ajralib turadi.
  2. Ikkinchi qator – m ta ijobiy butun son (har bir son – ushbu poygachi tomonidan har bir aylanish uchun ketgan vaqt). Bu sonlarning har biri 1000 dan oshmaydi.
    Har bir ismlar qatorining uzunligi 255 belgidan oshmaydi.
Chiquvchi ma'lumotlar:

OUTPUT.TXT fayliga kart poygasining g‘olibi bo‘lgan poygachining ismini yozish kerak. Agar g‘oliblar bir nechta bo‘lsa, ulardan birinchisining ismini chiqarish kifoya.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 3
Jumanazar
2 1 1
Barikelo
2 1 2
Fatima
1 2 1
Mirshod
1 1 1
Fedya
1 1 1
 
Mirshod

H. String #3

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Kuzimirda s qatori bor, u faqat lotin harflaridan 'A', 'B' va 'C' iborat. Har bir yurishda u quyidagi ikki amaldan birini bajarishi mumkin:

  1. Bir dona 'A' harfini va bir dona 'B' harfini olib tashlash (bu harflar qatorning istalgan joyida, yonma-yon bo'lmasa ham bo'ladi);
  2. Bir dona 'B' harfini va bir dona 'C' harfini olib tashlash (bu harflar qatorning istalgan joyida, yonma-yon bo'lmasa ham bo'ladi).

Shunday qilib, har bir yurishda qator uzunligi aynan 2 ta harfga kamayadi. Amallar bir-biriga bog'liq emas, va har bir yurishda Kazimir yuqoridagi ikki variantdan birini tanlashi mumkin.

Masalan, agar s = "ABCABC" bo'lsa, u bir yurishda sni "ACBC" ko'rinishiga keltirishi mumkin (birinchi 'B'ni va ikkinchi 'A'ni olib tashlash orqali). Bu faqat mumkin bo'lgan bir natija, boshqa ko'plab imkoniyatlar mavjud.

Masala:
Sizga berilgan qator s ni bo'sh qatorga aylantirish uchun amallar ketma-ketligini bajarish mumkinmi? Ya'ni, barcha harflarni olib tashlash mumkinmi?

Kiruvchi ma'lumotlar:
  • Birinchi qatorda butun son t (1 ≤ t ≤ 1000) — testlar soni.
  • Keyingi t qatorning har biri qatori s ni ifodalaydi. Har bir qator faqat 'A', 'B' va 'C' harflaridan iborat va uzunligi 1 ≤ |s| ≤ 50.
Chiquvchi ma'lumotlar:

Har bir test uchun javobni alohida qator sifatida chiqaring:

  • Agar qatorni bo'sh qatorga aylantirish mumkin bo'lsa, YES chiqaring.
  • Aks holda, NO chiqaring.
Misollar:
# INPUT.TXT OUTPUT.TXT
1 
6
ABACAB
ABBA
AC
ABC
CABCBB
BCBCBCBCBCBCBCBC
 
NO
YES
NO
NO
YES
YES
Kitob yaratilingan sana: 19-Jan-25 03:51