A. Egizaklar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling sizning egizak jiyanlaringiz bor. Siz ularning ikkisini ham judayam yaxshi ko’rasiz, va ularni bir biridan ayirmaslik uchun ikkisiga ham har doim bir xil o’yinchoqlar, kiyimlar olib berasiz. Kunlardan bir kun siz bolalar do’koniga kirdingiz, do’konda har bir turdagi bolalar o’yinchoqlari raqamlab chiqilgan. Siz do’konni aylanib chiqib bildingizki do’konda jami N ta o’yinchoq bor va ularning har birining raqamlarini bilib oldingiz. Siz jiyanlaringizga sovg’a olsangiz bu do’kondan ko’pi bilan nechta mahsulot xarid qilishingizni aniqlang.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining birinchi satrida T(1 ≤ T ≤ 1000) testlar soni kiritiladi. Keyin har bir qator uchun alohida ikki qatorning birinchisida N(1 ≤ N ≤ 1000) va ikkinchi qatorida N ta [1, 1000000] oralig’idagi butun sonlar kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 9 12981 10309 12981 19639 10309 22624 22624 19639 2273 3 8783 14989 14989	8 2
2	4 10 21772 21772 21379 13185 27573 13185 21379 10195 27573 10195 5 8916 30334 8916 26653 7529 10 561 19093 17440 24222 15569 13917 31122 19478 19093 8427 2 15148 15148	10 2 2 2

#

INPUT.TXT

OUTPUT.TXT

1

2
9
12981 10309 12981 19639 10309 22624 22624 19639 2273
3
8783 14989 14989

8
2

2

4
10
21772 21772 21379 13185 27573 13185 21379 10195 27573 10195
5
8916 30334 8916 26653 7529
10
561 19093 17440 24222 15569 13917 31122 19478 19093 8427
2
15148 15148

B. Takrorlanmas qism satr

Xotira: 16 MB, Vaqt: 1000 ms

Masala

S satri berilgan. S satrdan barcha qism satrlari takrorlanmas bo’lishi uchun eng kamida nechta belgi o’chirish kerakligini aniqlang.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 100) testlar soni. Keyingi T ta qatorning har birida lotin kichik harflaridan iborat S (1 ≤ |S| ≤ 26) satri kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda bittadan butun son, eng kam o’chirilishi kerak bo’lgan belgilar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 aab aebaecedabbee ab	1 8 0

C. Chiroyli matritsa

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Matritsaning barcha qatorlari va barcha ustunlari elementlari yig’indisi bir – biriga teng bo’lsa bu matritsa chiroyli hisoblanadi. Sizga o’lchami NxN bo’lgan matritsa berilgan, siz bir o’zgartirishda matritsaning ixtiyoriy bir elementini qiymatini 1 ga oshirishingiz mumkin. Matritsani chiroyli matritsa holatiga keltirish uchun size ng kamida matritsa ustiga necha marotaba o’zgarish qilishingiz kerakligini aniqlang.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 1000). Keyingi N ta satrning har birida N tadan butun son, [1, 10⁹] oralig’idagi matritsa elementlari kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida yagona son, masala yechimini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 1 2 3 4	4
2	3 1 2 3 4 2 3 3 2 1	6

D. Ajoyib juftlik

Xotira: 16 MB, Vaqt: 500 ms

Masala

Sizga [0,9] oralig’idagi raqamlardan tashkil topgan N ta satr berilgan. Agar i – satr va j – satrni birlashtirganda 0 dan 9 gacha bo’lgan barcha raqamlar qatnashadigan satr hosil bo’lsa i va j (i<j) juftlik ajoyib deyiladi. Berilgan satrlar orasida nechta ajoyib juftliklar mavjudligini toping.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 10⁶) jami satrlar soni kiritiladi. Keyingi N ta satrda umumiy uzunligi 10⁶ dan oshmaydigan satrlar beriladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, umumiy ajoyib juftliklar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 129300455 5559948277 012334556 56789 123456879	5

E. Permutatsiya

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Adizda [1,…,N] sonlar ketma-ketligi mavjud. U bu sonlarning barcha permutatsiyasini leksikografik o’sish tartibida qog’ozga yozib oldi va ularni ketma-ketligi bo’yicha raqamlab chiqdi. Masalan N=3 uchun jami 6 ta permutatsiya bor va ular quyidagilar:

Adiz bu permutatsiyalar orasidan ixtiyoriy birini tanlab oldi va uni yodida saqladi. Bir necha kundan so’ng u o’zi tanlagan permutatsiyani qog’ozga yozmoqchi bo’lganida bildiki tanlagan permutatsiyasidagi ba’zi qiymatlar yodidan ko’tarilgan, qog’ozga yozish jarayonida u yodidan ko’tarilgan qiymatlar o’rniga 0 qiymatini yozdi. Shundan so’ng uni quyidagicha savol qiziqtirib qoldi, u tanlagan permutatsiya qog’ozdagi qaysi qatorlar bo’lishi mumkin.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 3*10⁵) permutatsiyadagi elementlar soni. Keyingi qatorda N ta butun son, Adizning yodida saqlagan permutatsiyasi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, Adiz yodida saqlagan permutatsiya mos kelishi mumkin bo’lgan qog’ozdagi qatorlarning qiymatlari yig’indisini 10⁹+7 ga bo’lgandagi qiymatini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 0 2 3 0	23
2	4 4 3 2 1	24