A. Two strings (Ikki Satr)

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Sizga uzunliklari N ga teng bo’lgan $S$ va $T$ satrlar berilgan. Siz $S$ satr elementlarini xohlagan tartibingizda joylashtirishingiz mumkin. Vazifangiz $S[i]$ = $T[i]$ bo’ladigan 1 ≤ $i$ ≤ $N$ indekslar sonini maksimallashtirish.

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga $N$ butun son beriladi - satrlarning uzunliklari.
Ikkinchi qatorda $S$ satr beriladi.
Uchinchi qatorda $T$ satr beriladi.

Chegaralar
• 1 ≤ $N$ ≤ 1000
• $S$ va $T$ ingliz alifbosining kichkina harflaridan tashkil topgan
Subtasks
1. (10 ball) $T$ satr faqat “a” harflaridan iborat.
2. (20 ball) $N$ ≤ 10
3. (30 ball) $T$ satr faqat “a” va “b” harflaridan iborat.
4. (40 ball) Qo’shimcha chegaralarsiz.

Chiquvchi ma'lumotlar:

Yagona qatorda optimal tartiblashdan so’ng $S[i]$ = $T[i]$ shart bajariladigan indekslar sonining maksimal qiymatini chiqaring.

Izoh:

Masalan, N = 7, S = “dfaebac” va T = “abacaba” bo’lsin. U holda biz S ni “abdcefa” ko’rinishida tartiblashimiz mumkin. Shunda i ∈ {1, 2, 4, 7} indekslarda S[i] = T [i] shart bajariladi. Javob 4.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7 fdbeaac abacaba	4

B. Transport

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Dadorlandtiria mamlakatida $(N + 1)$ ta shahar bor va ular 1 dan $(N + 1)$ gacha raqamlangan.Shuningdek, mamlakatda 4 xil transport turi bor: avtobus, taksi, poyezd, samolyot.Sizga o’lchamlari 4 × N bo’lgan ikki o’lchamli a massiv berilgan. $a[t][i]$ bu $t$ -transport yordamida $i$ -shahardan $(i + 1)$ -shaharga borish uchun chipta narxi. Agar $a[t][i]$ = −1 bo’lsa u holda bu transport bilan $i$ va $(i + 1)$ -shaharlar orasida yurib bo’lmaydi. Bundan tashqari, har bir transport uchun oylik abonement mavjud. Agar siz qaysidir transportga abonement sotib olsangiz undan tekinga xohlaganingizcha foydalanishingiz mumkin. $t$ -transport abonementi $c[t]$ dollar turadi. Vazifangiz 1-shahardan $(N + 1)$ -shaharga borish uchun eng kamida qancha pul sarflash kerakligini topish. E’tibor bering, Dadorlandtiria mamlakatida barcha yo’llar bir tomonlik. Ya’ni i-shahardan $(i + 1)$ -shaharga o’tish mumkin, biroq $(i + 1)$ -shahardan $i$ -shaharga o’tib bo’lmaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga $N , c[1], c[2], c[3], c[4]$ sonlari beriladi - yo’llar soni va abonement narxlari.
Keyingi 4ta qatorda $N$ tadan butun son, ikki o’lchamli $a$ massiv elementlari.

Chegaralar
• $1 ≤ N ≤ 10^5$
• $1 ≤ c[t] ≤ 10^9$ , barcha $1 ≤ t ≤ 4$ uchun
• $−1 ≤ a[t][i] ≤ 10^9$ , barcha $1 ≤ t ≤ 4$ va $1 ≤ i ≤ N$ uchun
Subtasks
1. (11 ball) $a[i][j] ≠ −1$
2. (10 ball) Abonement sotib olmasdan ham optimal javob topish mumkin.
3. (20 ball) Faqat 1 ta transportga abonement sotib olish orqali optimal javob topish mumkin.
4. (21 ball) Ko’pi bilan 2ta transportga abonement sotib olish orqali optimal javob topish mumkin.
5. (29 ball) Faqatgina 1 - va/yoki 2 - turdagi transportlar orqali optimal javobni topish mumkin.
6. (9 ball) Qo’shimcha chegaralarsiz.

Chiquvchi ma'lumotlar:

Yagona qatorda 1-shahardan $(N + 1)$ -shaharga borish uchun minimal pul miqdori.

Izoh:

Masalan, $N$ = 5, $c$ = [11, 5, 10, 99] bo’lsin. 2- va 3- transportlarga $c[2] + c[3]$ = 5 + 10 = 15 dollarga
abonement sotib olamiz. Shunda:
* 1-shahardan 2-shaharga bepul boramiz. (2-transport orqali).
* 2 shahardan 3-shaharga bepul boramiz. (3-transport orqali).
* 3-shahardan 4-shaharga 4 dollar evaziga boramiz. (1-transport orqali).
* 4-shahardan 5-shaharga bepul boramiz. (3-transport orqali).
* 5-shahardan 6 shaharga bepul boramiz. (2-transport orqali). Jami 15 + 0 + 0 + 4 + 0 + 0 = 19 dollar ishlatdik. Ko’rsatish mumkinki 19 minimal javob.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 11 5 10 99 -1 5 4 -1 -1 4 -1 -1 -1 9 -1 8 -1 6 -1 10 10 10 10 10	19

C. Cards (Kartalar)

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Bu interaktiv masala!

Gulnoza o’ylab topgan yangi Onu o’yinida $N$ xil turdagi karta bor, bunda ularga 1 dan $N$ gacha sonlar yozilgan. O’yinda jami $2N$ dona karta bor va bunda har bir turdagi kartadan aynan 2ta nusxada bor. Bir xil son yozilgan kartalar juftliklar deb ataladi. Yahyo barcha kartalarni bir qatorga orqa tomoni bilan qo’yib chiqdi. Yahyoga kartalarda qanday son yozilgani ko’rinadi, Gulnozaga esa yo’q. Gulnozaning vazifasi Yahyoga so’rovlar berish orqali barcha juftliklarni topib chiqish. Buning uchun Gulnoza bitta so’rovda kartalar to’plamini tanlab oladi, Yahyo esa shu to’plamda necha xil turdagi kartalar borligini aytadi.

Gulnozaga yordam bering!

Kodlash tartibi

Dastur boshida sizga $N$ soni beriladi, ya’ni turli xil kartalar soni. So’rov berish uchun:

? $k\ a[1]\ a[2]\ ...\ a[k]$

formatida ekranga chiqaring. Bunda $k$ – tanlangan
kartalar to’plamidagi elementlar soni, $a[i]$ esa kartalar indeksi. Indekslar o’sish tartibida chiqarlishi lozim, ya’ni

$1 ≤ a[1] < a[2] < ... < a[k] ≤ 2N$

So’ngra kiruvchi ma’lumotlardan d sonini qabul qiling, d – to’plamdagi har xil kartalar soni.
Javobni topganingizdan so’ng uni chiqarish uchun:

! $x[1]\ y[1]\ x[2]\ y[2] ... x[N]\ y[N]$

formatida chiqaring, bunda $x[i]$ va $y[i]$ kartalar bir xil turda bo’lishi kerak.

Kiruvchi ma'lumotlar:

Chegaralar
• 1 ≤ $N$ ≤ 256
• Jami so’rovlar soni 20 000dan oshmasligi zarur.
Subtasks
1. (9 ball) $N$ ≤ 2
2. (19 ball) $N$ ≤ 100
3. (7 ball) Ko’pi bilan bitta juftlik yonma-yon joylashmagan
4. (65 ball) Qo’shimcha chegaralarsiz.
Shuningdek, 4-subtaskda qism ball olishingiz mumkin. Aytaylik, 4-subtask testlari orasida eng ko’p ishlatgan so’rovlaringiz soni $q$ bo’lsin. U holda, quyidagicha ball olasiz:

Chiquvchi ma'lumotlar:

Masalan, $N$ = 4 va Yahyo kartalarni [2, 3, 2, 1, 4, 4, 3, 1] ko’rinishida joylashtirgan bo’lsin. Ya’ni bir xil son yozilgan juftliklar bu (4, 8), (1, 3), (2, 7) va (5, 6).

Birinchi so’rovda Gulnoza [1, 2, 3] indeksdagi kartalar haqida so’rov beradi. Bu kartalarda [2, 3, 2] sonlari yozilgan. Jami 2 xil turdagi kartalar borligi uchun Yahyo 2 deb javob beradi.

Agar Gulnoza [2, 4, 6, 7] deb so’rov bersa, Yahyo 3 deb javob beradi, chunki [3, 1, 4, 3] sonlari orasida 3 xil qiymat bor.

Shundan so’ng Gulnoza [2, 7, 5, 6, 1, 3, 8, 4] ko’rinishida javob beradi. Ya’ni 2 va 7-kartalarda bir xil son yozilgan, 5 va 6-kartalarda bir xil son yozilgan va h.k.

E’tibor bering, Gulnoza [7, 2, 5, 6, 1, 3, 8, 4] yoki [8, 4, 3, 1, 2, 7, 6, 5] ko’rinishida javob berganida
ham uning javobi to’g’ri hisoblanar edi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 2 3	‎ ‎ ? 3 1 2 3 ? 4 2 4 6 7 ! 2 7 5 6 1 3 8 4

D. Thanos sort

Xotira: 128 MB, Vaqt: 1500 ms

Masala

Tanosning saralash algoritmi deb quyidagi saralashga aytiladi: - Agar massiv kamaymaslik tartibida* saralangan bo’lsa, u holda Tanos hech narsa qilmaydi. - Aks holda Tanos cheksizlik toshlari yordamida massivni teng ikkiga bo’ladi va istalgan yarmini o’chirib tashlaydi. - Massiv saralanmagunicha shu ishni davom ettiradi.
Sizda uzunligi $N$ ga teng bo’lgan $a[1], a[2], ..., a[N ]$ massivi bor. Shuningdek, Qta so’rovda sizga $l$ va $r$ sonlari beriladi. Vazifangiz $a[l], a[l + 1], ..., a[r]$ qismmassivni saralash uchun cheksizlik toshlarini eng kamida nechi marta ishlatish kerakligini topish. Bunda berilgan qismmassiv uzunligi 2 ning darajasi ekanligi kafolatlanadi.
*Kamaymaslik tartibida har bir element o’zidan avvalgi elementdan kichkina bo’lmasligi lozim.
Ya’ni $a[1] ≤ a[2] ≤ ... ≤ a[N ].$

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga N va Q sonlari beriladi - elementlar va so’rovlar soni.
Ikkinchi qatorda $a[1], a[2], ..., a[N ]$ - massiv elementlari. Keyingi $Q$ ta qatorda $l$ va $r$ - so’rovlar.

Chegaralar
• 1 ≤ $N$ ≤ 131 072
• 1 ≤ $Q$ ≤ 200 000
• $1 ≤ a[i] ≤ 10^9$ , barcha $1 ≤ i ≤ N$ uchun
• 1 ≤ $l$ ≤ $r$ ≤ $N$ , hamda $r − l + 1 = 2x$ , $x$ - nomanfiy butun son
Subtasks
1. (6 ball) So’rovlarda $r$ = $l$ + 1
2. (13 ball) $N$ ≤ 8; $Q$ = 1; $l$ = 1; $r$ = N
3. (21 ball) $Q$ = 1; $l$ = 1; $r$ = N
4. (24 ball) Barcha so’rovlar uchun javob 2dan oshmaydi.
5. (15 ball) $N$ ≤ 16384
6. (21 ball) Qo’shimcha chegaralarsiz.

Chiquvchi ma'lumotlar:

$Q$ ta qatorda har bir so’rov uchun javobni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	9 3 3 1 4 1 5 9 2 6 5 1 8 5 5 3 4	2 0 1

E. Two Trees (Ikki daraxt)

Xotira: 512 MB, Vaqt: 1000 ms

Masala

Daraxt deb bog’langan yo’nalmagan asiklik grafga aytiladi.
Sizga ikkita ildizli daraxt berilgan, ikkala daraxtda ham N tadan tugun bor. Birinchi daraxtning ildizi $r_1$ , ikkinchi daraxtning ildizi $r_2$ -tugun.
$S_1(v)$ deb shunday $u$ tugunlar to’plamiga aytiladiki, birinchi daraxtda $r_1$ dan u tugunga boruvchi yo’l $v$ tugundan o’tadi. Xuddi shunday, $S_2(v)$ deb shunday $u$ tugunlar to’plamiga aytiladiki, ikkinchi daraxtda $r_2$ dan $u$ tugunga boruvchi yo’l $v$ tugundan o’tadi.
Sizdan so’ralgan narsa barcha $1 ≤ v ≤ N$ tugunlar uchun $S_1(v)$ ∩ $S_2(v)$ to’plam kesishmalarining o’lchamlarini topish.

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga $N$ , $r_1$ va $r_2$ butun sonlari beriladi - tugunlar soni va daraxtlarning ildizlari.
Ikkinchi qatorda $p_1[1], p_1[2],...,p_1[N]$ butun sonlari beriladi. Bunda barcha $1 ≤ i ≤ N$ va $i ≠ r1$
uchun birinchi daraxtda i va p1 [i] tugunlar o’rtasida qirra bor.
Uchinchi qatorda $p_2[1], p_2[2],...p_2[N]$ butun sonlari beriladi. Bunda barcha $1 ≤ i ≤ N$ va $i ≠ r2$ uchun ikkinchi daraxtda $i$ va $p_2[i]$ tugunlar o’rtasida qirra bor.
E’tibor bering, $p_1[r_1]$ va $p_2[r_2]$ elementlarning qiymatlari −1ga teng.

Chegaralar
• 2 ≤ $N$ ≤ 3 · 105
• 1 ≤ $r_1$ , $r_2$ ≤ $N$
• 1 ≤ $p_1[i]$ ≤ $N$ , barcha $1 ≤ i ≤ N$ va $i≠r_1$ uchun
• $1 ≤ p_2 [i] ≤ N$ , barcha $1 ≤ i ≤ N$ va $i≠r_2$ uchun
• $p_1 [r_1 ] = −1$ va $p_2 [r_2 ] = −1$ $p_1$ va $p_2$ massivlar daraxt hosil qilishi kafolatlanadi.

Subtasks
$c(v)$ bu $p[i] = v$ bo’ladigan $i$ indekslar soni bo’lsin.
Binar daraxt deganda barcha $1 ≤ v ≤ N$ tugunlar uchun $c(v) = 0$ yoki $c(v) = 2$ shart bajariladigan
daraxtga aytiladi.
Chiziqli daraxt deganda barcha 1 ≤ v ≤ N tugunlar uchun c(v) ≤ 1 shart bajariladigan daraxtga
aytiladi.

1. (11 ball) Daraxtlar bir xil, ya’ni $r_1 = r_2$ va $p_1 = p_2$
2. (12 ball) $N$ ≤ 3000
3. (13 ball) Ikkala daraxtlar ham binar.
4. (17 ball) Ikkala daraxtlar ham chiziqli.
5. (21 ball) Birinchi daraxt chiziqli.
6. (26 ball) Qo’shimcha chegaralarsiz.

Chiquvchi ma'lumotlar:

Yagona qatorda $N$ ta son chiqaring, har bir $v$ uchun javob.

Izoh:

Masalan, $N$ = 5, $r_1$ = 3, $r_2$ = 1 bo’lsin, hamda $p_2$ = [3, 3, −1, 1, 2] va $p_2$ = [−1, 1, 2, 3, 3] deylik. Uholda daraxtlar quyidagi ko’rinishda bo’ladi:
• $S_1 (1)$ = {1, 4} va $S_2 (1)$ = {1, 2, 3, 4, 5}. Ularning kesishmasi {1, 4}ga teng.
• $S_1 (2)$ = {2, 5} va $S_2 (2)$ = {2, 3, 4, 5}. Ularning kesishmasi {2, 5}ga teng.
• $S_1 (3)$ = {1, 2, 3, 4, 5} va $S_2 (3)$ = {3, 4, 5}. Ularning kesishmasi {3, 4, 5}ga teng.
• $S_1 (4)$ = {4} va $S_2 (4)$ = {4}. Ularning kesishmasi {4}ga teng.
• $S_1 (5)$ = {5} va $S_2 (5)$ = {5}. Ularning kesishmasi {5}ga teng.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 1 3 3 -1 1 2 -1 1 2 3 3	2 2 3 1 1