A. Golf

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Ko'pgina o'yinlarda o'yinchi qancha ko'p ball yig'sa shuncha yaxshi. Ammo golfda unday emas!.

Golf o'yini juda sodda, ammo o'ziga xos intizomga ega sport turidir. O'yinning asosiy maqsadi — to'pni maxsus tayoqlar (klublar) yordamida iloji boricha kamroq zarbalar bilan start nuqtasidan teshikka (lupaga) tushirishdir.

Golf "janoblar o'yini" hisoblanadi, shuning uchun o'yinchilar ko'pincha hakamlarsiz o'ynab, o'z zarbalarini o'zlari halol hisoblashlari shart.

Janob Adizbek shunday halol insonlardan biri. U hozirga qadar \(N\) marotaba golf o'yinida ishtirok etgan, va har o'yinda nechta zarba bilan to'pni teshikka(lupaga) tushirganini yozib olgan.

Janob Adizbekning hozirga qadar golf o'yinida o'zi tomonidan o'rnatilgan shaxsiy rekordi necha zarbadan iborat ekanligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(N(1 \le N \le 100)\) soni kiritiladi.

Ikkinchi satrda bo'sh joy bilan ajratilgan holda qiymati [1, 500] oralig'idagi \(N\) ta butun son, janob Adizbekning har bir o'yindagi to'pni teshikka tushirishdagi zarbalar soni keltirilgan.

Chiquvchi ma'lumotlar:

Janob Adizbekning golfdagi shaxsiy rekordini chop eting!.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 2 9 5	2

B. Efootball reytingi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Efootball (sobiq PES) o‘yinida PvP rejimida o‘yinchilar onlayn o‘yin o‘tkazadi. Har bir o‘yin natijasidan so‘ng o‘yinchining reytingi o‘zgaradi.

Reyting hisoblash qoidalari

O‘yin boshida reyting \(1200\).
Agar o‘yin natijasi g‘alaba bo‘lsa, reyting oshadi.
Ketma-ket g‘alabalar seriyasi uchun qo‘shiladigan ochkolar:
- birinchi g‘alaba \(30\),
- ikkinchi ketma-ket g‘alaba \(29\),
- uchinchi ketma-ket g‘alaba \(28\),
- va hokazo.
- Qiymat \(10\) ga yetganda kamayish to‘xtaydi, undan keyingi ketma-ket g‘alabalar uchun \(10\) ochkodan qo‘shiladi.
Agar o‘yin natijasi mag‘lubiyat bo‘lsa, reyting kamayadi.
Ketma-ket mag‘lubiyatlar seriyasi uchun ayriladigan ochkolar:
- birinchi mag‘lubiyat \(30\),
- ikkinchi ketma-ket mag‘lubiyat \(29\),
- uchinchi ketma-ket mag‘lubiyat \(28\),
- va hokazo.
- Qiymat \(10\) ga yetganda kamayish to‘xtaydi, undan keyingi ketma-ket mag‘lubiyatlar uchun \(10\) ochko ayriladi.
Durang uchun reyting o‘zgarmaydi, \(0\) ochko.
Seriyalar yangilanishi:
- g‘alaba mag‘lubiyat seriyasini \(0\) ga tushiradi, g‘alaba seriyasini \(1\) ga oshiradi.
- mag‘lubiyat g‘alaba seriyasini \(0\) ga tushiradi, mag‘lubiyat seriyasini \(1\) ga oshiradi.
- durang ikkala seriyani ham \(0\) ga tushiradi.
Har bir o‘yindan keyin agar reyting manfiy bo‘lib qolsa, u \(0\) ga tenglashtiriladi.

Sizga o‘yin natijalari ketma-ketligi beriladi. Shu ketma-ketlik bo‘yicha o‘yinchining yakuniy reytingini hisoblang.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(k \ (1 \le k \le 10^5)\) - o‘yinlar soni beriladi.
Ikkinchi qatorda uzunligi \(k\) bo‘lgan satr kiritiladi. Har bir belgi o‘yin natijasini bildiradi:
W - g‘alaba
L - mag‘lubiyat
D - durang

Chiquvchi ma'lumotlar:

Yagona qatorda o'yinchining yakuniy reytingini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 WDW	1260
2	9 LDLLWDWWW	1228

C. Qutilarni joylashtirish

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Omborda konveyer lentasida \(n\) ta quti ketma-ket turibdi. Har bir qutining og‘irligi \(a_i\).

Omborchi quyidagi amalni istagancha marta bajarishi mumkin:

Yonma-yon turgan ikkita qutini (\(a_i\) va \(a_{i+1}\)) tanlaydi.
Ularni faqat \(a_i + a_{i+1}\) toq bo‘lsa, joyini almashtiradi.

Sizga konveyerning kerakli yakuniy ko‘rinishi \(b\) berilgan. \(a\) massivni shu qoidalar bilan \(b\) massivga aylantirish mumkinmi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t\) — testlar soni kiritiladi.

Har bir test uchun:

Birinchi qatorda \(n (2 ≤ n ≤ 2\times10^5)\);
Ikkinchi qatorda \(a_i (1 ≤ a_i ≤ 10^9)\);
Uchinchi qatorda \(b_i (1 ≤ b_i ≤ 10^9)\) beriladi.

Cheklov: barcha testlar bo‘yicha \(n\) lar yig‘indisi \(2\times10^5\) dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda:

\(YES\) — mumkin bo‘lsa;
\(NO\) — aks holda;

ni chop eting;

Izoh:

1-test — \(YES\)

\([3, 2, 4, 1] → [2, 3, 1, 4]\)

Mumkin bo‘lgan swaplar ketma-ketligi:

\(3\) va \(2\) ni swap qilamiz (3+2=5 toq): \([2, 3, 4, 1]\)
\(4\) va \(1\) ni swap qilamiz (4+1=5 toq): \([2, 3, 1, 4]\)

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 4 3 2 4 1 2 3 1 4 4 3 2 4 1 4 3 2 1 5 2 7 4 9 6 7 2 4 6 9 4 1 3 2 4 3 1 2 4	YES NO YES NO

D. Tugunlar Murosasi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga N ta tugun va M ta qirrali (yo'naltirilmagan) graf berilgan. Tugunlar \(1\) dan \(N\) gacha raqamlangan.

Siz grafga ba’zi yangi qirralarni qo‘shishingiz mumkin (ixtiyoriy tugunlar orasiga).

\(K\) — grafni bog‘lash (bitta bog‘langan komponentga keltirish) uchun qo‘shiladigan minimal qirralar soni.
\(extra_i\) — qo‘shilgan yangi qirralardan tugun i ga tutashganlari soni.
\(max\_extra\) — \(\max \{extra_1, extra_2, \dots, extra_N\}\).

Grafni bog‘lash uchun avvalo \(K\) ning qiymati minimal bo‘lsin.
Shu minimal \(K\) bilan bog‘lash mumkin bo‘lgan yechimlar ichida esa \(max\_extra\) eng kichik bo‘lsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(M\) beriladi. \(1 \le N \le 100\,000, \ 0 \le M \le 100\,000\)
Keyingi \(M\) qatorda \(a\ b\) juftliklari beriladi — bu \(a\) va \(b\) tugunlar orasida qirra borligini bildiradi.
Kirishdagi qirralar takrorlanmaydi va har bir qirra uchun \(a \ne b\).

Chiquvchi ma'lumotlar:

Bitta qatorda ikki son - \(K\) va \(max_{extra}\) ni chiqaring.

Misollar:

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

E. Kuryer yo'li

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Shaharda yangi turdagi “aqlli” kuryer-robot sinovdan o‘tkazilmoqda. Shahar xaritasi to‘g‘ri to‘rtburchak shaklida bo‘lib, u \(N\) ta qator va \(M\) ta ustundan iborat. Har bir katak — bir blok (maydon) va u yerda signal darajasi yozilgan.

Qiziq tomoni: xaritadagi signal darajalari 1 dan \(N*M\) gacha bo‘lgan barcha sonlardan iborat.

Robotning harakati cheklangan:

u har safar qo‘shni blokka 1 qadam bilan o‘tadi;
faqat o‘ngga (Sharq) yoki pastga (Janub) yurishi mumkin.

Robot yo‘l (marshrut)ni istalgan blokdan boshlashi va istalgan blokda tugatishi mumkin (harakat qoidalariga rioya qilgan holda).

Robot ishlab chiqaruvchilari marshrutni “muvaffaqiyatli” deb baholashadi, agar:

marshrut tugagan blokdagi signal darajasi boshlangan blokdagidan katta bo‘lsa.

Ya’ni marshrut “muvaffaqiyatli” bo‘lishi uchun, oxirgi signal birinchidan kuchliroq bo‘lishi shart.

Istalgan “muvaffaqiyatli” marshrut ichida robot bosib o‘tishi mumkin bo‘lgan bloklar sonining eng katta qiymati \(Z\) ni toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(M\) beriladi. \((1\le N, M\le 2000)\)
Keyingi \(N\) qatorda \(M\) tadan son — har bir blokdagi signal darajasi beriladi. \(1\le signal\le N * M\)

Matritsada 1 dan \(N*M\) gacha bo‘lgan barcha sonlar aynan bir martadan uchraydi.

Chiquvchi ma'lumotlar:

Yagona qatorda masala javobi \(Z\) ni chiqaring.

Agar birorta ham muvaffaqiyatli marshrut mavjud bo‘lmasa, 0 ni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4 12 11 10 6 7 5 4 3 9 2 8 1	4
2	3 3 5 8 7 9 6 4 3 1 2	3