A. Kubik o'yini

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Shohruhda \(n\) yuzali kubik bor. Kubik yuzalari \(1\) dan \(n\) gacha raqamlangan. Ushbu kubik bilan o'ynash uchun u yerga tashlanadi. Kubikning tepa qismida ko'ringan son Shohruhning ochkolariga qo'shilib boradi.

Shohruh jami kamida \(m\) ochko to‘plashni xohlaydi. Agar Shohruh eng yaxshi holatda o'ynasa, kamida nechta marta kubik tashlashi kerakligini toping.

Kiruvchi ma'lumotlar:

Bitta qatorda ikkita butun son \(n\) va \(m\) beriladi.

\(2 \le n \le 100\)

\(1 \le m \le 100\)

Chiquvchi ma'lumotlar:

Bitta butun son chiqaring, kamida \(m\) ochkoga yetish uchun kerak bo‘ladigan eng kam kubik o'yinlari soni.

Izoh:

Birinchi test uchun, agar kubik ketma-ket 6, 5 va 4 sonlari bilan tushsa, umumiy 15 ochko boladi, demak 3 ta kubik yetarli. Aytish mumkinki, 3 tadan kamroq kubik bilan 15 ochko olish imkonsiz ekanini isbotlash mumkin.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
6 15
 
3
2 
10 4
 
1

B. Kompyuter xonalari

Xotira: 256 MB, Vaqt: 1000 ms
Masala

STEM musobaqasi maktabdagi kompyuter xonalarida o‘tkaziladi. Musobaqada jami \(K\) nafar o‘quvchi qatnashadi.

Maktabda \(N\) ta kompyuter xonasi bor. \(i-\) xonada \(a_i\)​ ta kompyuter mavjud. Bitta kompyuterda faqat bitta o‘quvchi ishlaydi.

Musobaqa vaqtida xavfsizlik va tartib uchun ishlatilgan har bir xonaga aynan bitta nazoratchi tayinlanadi. Agar xona ishlatilmasa, u qulflanadi va unga nazoratchi tayinlanmaydi.

Siz o‘quvchilarni xonalarga joylashtirishingiz kerak. Har bir o‘quvchi aynan bitta xonaga joylashtiriladi va \(i-\) xonaga joylashtirilgan o‘quvchilar soni \(a_i\) dan oshmasligi kerak.
Barcha \(K\) nafar o‘quvchini nazorat qilish uchun kerak bo‘ladigan eng kam nazoratchilar sonini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(K\) va \(N\) - mos ravishda o'quvchilar va xonalar soni beriladi.
Ikkinchi qatorda \(N\) ta butun son \(a_1,a_2,…,a_N\) - har bir xonadagi kompyuterlar soni kiritiladi.

\(1 \le K \le 10^9\)

\(1 \le N \le 10^5\)

\(1 \le a_i \le 10^9\)

\(\sum_{i = 1}^{N}{a_i} \ge K\) ekanligi, ya'ni umumiy kompyuterlar soni barcha o'quvchilar sonidan kam emasligi kafolatlanadi.

Chiquvchi ma'lumotlar:

O'quvchilarni qamrab olish uchun kerak bo'ladigan eng kam nazoratchilar sonini chop eting.

Izoh:

1-test holati uchun 3 ta nazoratchini 1, 2, va 4 xonalarga qo'yish mumkin, bunda barcha ishtirokchilar ushbu xonalarga joylashtiriladi. 

2-test holati uchun esa barcha xonalar ishlatilishi shart, shuning uchun hamma xonaga bittadan nazoratchi talab qilinadi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
20 4
6 8 5 10
 
3
2 
20 5
4 4 4 4 4
 
5

C. Energiya kapsulalari

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Qadimiy laboratoriyada yonma-yon terilgan energiya kapsulalari bor. Har kapsulada \(0…9\) oralig‘idagi bitta raqam yozilgan.

Laboratoriya qoidasi shunday:

  • Agar yonma-yon turgan ikkita kapsulaning raqamlari yig‘indisi 10 bo‘lsa, ular birdaniga portlab, ikkalasi ham yo‘qoladi.
  • Kapsulalar yo‘qolgach, qolganlari yaqinlashib, yana yonma-yon bo‘lib qoladi.
  • Bu jarayon portlash bo‘lishi mumkin bo‘lganicha davom etadi.

Sizning vazifangiz: har test uchun portlashlar tugagandan keyin nechta kapsula qolishini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t\) — testlar soni.

Har bir testda bitta satr beriladi: raqamlardan iborat \(s\) satri \((0…9)\).

Chegaralar:

  • \(1 ≤ t ≤ 2 \times 10^4\)
  • \(1 ≤ |s| ≤ 2 \times 10^5\)
  • \(s\) faqat \(0…9\) raqamlardan iborat
  • Barcha testlar bo‘yicha \(|s|\) uzunliklar yig‘indisi  \(2 \times 10^5\) dan oshmaydi.

 

Chiquvchi ma'lumotlar:

Har bir test uchun bitta butun son chiqaring — barcha portlashlardan keyin qolgan kapsulalar soni.

Izoh:
  • \(1901\): \(1+9=10 → 19\) portlaydi, satr \(01\) bo‘ladi. \(0+1≠10\), to‘xtaydi. Qoldi: \(2\).
  • \(2819\): avval \(2+8=10 → 28\) portlaydi, satr \(19\) bo‘ladi. \(1+9=10 → 19\) ham portlaydi. Qoldi: \(0\).
Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
1901
2819
5555
9182736455
 
2
0
0
0

D. Sehrli matritsa

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Sizga \(N \times M\) o‘lchamli A matritsa beriladi. Har bir elementning qiymati \(1\) dan \(N \cdot M\) gacha bo‘ladi, qiymatlar takrorlanishi mumkin.

Bitta operatsiyada quyidagilardan bittasini bajarish mumkin:

  • ketma-ket joylashgan (yonma-yon) ikki qatorni tanlab, ularning o‘rnini almashtirish;
  • ketma-ket joylashgan ikki ustunni tanlab, ularning o‘rnini almashtirish.

Matritsa Sehrli deyiladi, agar:

  • har bir qatorda chapdan o‘ngga qarab qiymatlar kamaymasa:

    \(A[i][j] \geq A[i][j-1] \quad (1 \leq i \leq N,\ 2 \leq j \leq M)\)

  • har bir ustunda yuqoridan pastga qarab qiymatlar kamaymasa:

    \(A[i][j] \geq A[i-1][j] \quad (2 \leq i \leq N,\ 1 \leq j \leq M)\)

Berilgan matritsani sehrli matritsaga aylantirish uchun kerak bo‘ladigan minimal operatsiyalar sonini toping.
Agar bunday o‘zgartirishni amalga oshirib bo‘lmasa, -1 chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(M\) beriladi. \(1 \leq N,\ M \leq 300\)
Keyingi \(N\) qatorning har birida \(M\) tadan son — matritsa elementlari beriladi.

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Izoh:

2-namunaviy test uchun:
1-operatsiya: 1-qator va 2-qator joyini almashtiramiz

\(\begin{matrix} 4 & 6 & 2 \\ 6 & 6 & 5 \end{matrix}\)

2-operatsiya: 2-ustun bilan 3-ustunni almashtiramiz

\(\begin{matrix} 4 & 2 & 6 \\ 6 & 5 & 6 \end{matrix}\)

3-operatsiya: 1-ustun bilan 2-ustunni almashtiramiz

\(\begin{matrix} 2 & 4 & 6 \\ 5 & 6 & 6 \end{matrix}\)

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 3
1 2 4
3 5 6
 
0
2 
2 3
6 6 5
4 6 2
 
3

E. Yo‘llarni yo‘naltirish

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Algoritm City da \(n\) ta chorraha va ular orasida \(m\) ta ikki tomonlama yo‘l bor.

Har bir chorraha \(v\) uchun shahar qoidasi berilgan:
 

  • \(r[v]=0\) bo‘lsa — \(v\) dan chiqadigan yo‘naltirilgan yo‘llar soni juft bo‘lishi kerak.
  • \(r[v]=1\) bo‘lsa — \(v\) dan chiqadigan yo‘naltirilgan yo‘llar soni toq bo‘lishi kerak.


Sizning vazifangiz: har bir ikki tomonlama yo‘lga yo‘nalish bering (ya’ni \(u \to v\) yoki \(v \to u\)).

Agar barcha chorrahalar uchun talablarga mos yo‘nalish berish imkonsiz bo‘lsa, \(-1\) chiqaring.
Aks holda, yo‘llarning kiritilgan tartibida ularning yo‘nalishini chiqaring.

Agar bir nechta yechim mavjud bo‘lsa, istalgan bittasini chiqarsangiz bo‘ladi.
 

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) va \(m\) beriladi.

Ikkinchi qatorda \(n\) ta son \(r_1, r_2, \dots, r_n\) \(\big(r_i \in \{0,1\}\big)\) beriladi.

Keyingi \(m\) qatorda \(u_i\) va \(v_i\) — \(i\)-yo‘lning ikki uchi (ya’ni qaysi ikkita chorrahani bog‘laydi) beriladi.

Chegaralar:

\(1 \le n \le 2 \cdot 10^5\)

\(1 \le m \le 2 \cdot 10^5\)

\(1 \le u_i, v_i \le n,\; u_i \ne v_i\)

Bir xil ikki chorraha orasida bir nechta yo‘l bo‘lishi mumkin (parallel yo‘llar bo‘lishi mumkin).

O‘z-o‘ziga yo‘l yo‘q.

 

Chiquvchi ma'lumotlar:

Agar yechim bo'lmasa: \(-1\)

Aks holda \(m\) qatorda (yo'llar kiritilgan tartibda) \(a_i\) \(b_i\) chiqaring — bu \(i\)-yo'l \(a_i \to b_i\) yo'nalishda qo'yilganini bildiradi.
 

Izoh:

\(1\)-testda chiqadigan yo'llar soni:

  • \(1\) dan chiqadi: \(1\) ta (toq) \(\rightarrow r_1=1\)
  • \(2\) dan chiqadi: \(1\) ta (toq) \(\rightarrow r_2=1\)
  • \(3\) dan chiqadi: \(1\) ta (toq) \(\rightarrow r_3=1\)

 

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 3
1 1 1
1 2
2 3
1 3
 
1 2
2 3
3 1
2 
3 3
0 0 0
1 2
2 3
1 3
 
-1
Kitob yaratilingan sana: 11-Mar-26 16:26