A. Kechki Sayr

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Siz do'stlaringiz bilan yilning \(X\) - kuni soat \(Y\) dan keyin Kechki sayrga chiqishni rejalashtirdingiz, lekin do'stlaringizni orasida qorong'udan qo'rqadigan bolalar ham mavjud shuning uchun sizlar faqatgina Tungi chiroqlar \(yoqilgan\) vaqtdagina sayrga chiqishlaring mumkin. Baxtga qarshi chiroqlar faqatgina yilning \(toq\) kunlari soat \(18:00\) dan keyin yoqiladi va \(24:00\) da o'chiriladi. Siz rejalashtirgan vaqtda do'stlaringiz bilan sayrga chiqa olasizmi ?

\(Agar \ sayrga \ chiqa \ olsangiz \ "YES" \ aks \ holda \ "NO" \ so'zini \ ekranga \ chiqaring.\)

Kiruvchi ma'lumotlar:

Yagona qatorda \(X(1 \le X \le 365)\) va \(Y(17 \le Y \le 23)\) sonlari mos ravishda yilning qaysi kuni ekanligi, hamda soat nechchida sayrga chiqishlaring.

Chiquvchi ma'lumotlar:

Masala javobini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	161 17	NO
2	310 20	NO
3	161 19	YES

B. Sirkdagi akrobatlar

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Sirkda jami \(N\) ta akrobat bor. har bir akrobatning futbolkasida uning tartib raqami yozilgan.

Sirkga tashrif buyurgan muxlislar akrobatlarning tartibini qura tashlash orqali o'zgartirishdi, hamda ularni bir safga terib qo'yishdi.
Endi akrobatlar muxlislarni hayratga solish maqsadida quyidagi tarzda harakat qilib o'rin almashtirish orqali safni qayta tartiblangan holga keltirishga qaror qilishdi:

Akrobatlarda umumiy bitta to'p bor, va u o'yin boshida safda 1-tartibda turgan o'yinchida bo'ladi (bu hech nimani anglatmaydi). Barcha akrobat toki o'z o'rniga(futbolkasida yozilgan o'ringa) yetib bormaguncha ular jamoaviy harakat qilib quyidagi amalni takror-takror bajarishadi:
- Qo'lida to'p bor o'yinchi safdagi tartibi \([2, N-1]\) oraliqda bo'lgan ixtiyoriy bir akrobatni tanlaydi va unga to'pni uloqtiradi (agarda o'zi ham shu oraliqda bo'lsa o'ziga o'zi to'p uloqtirishi ham mumkin).
- To'pni qabul qilgan akrobat to'pni mahkam ushlab yerga o'tiradi, shu vaqtda uning chap va o'ng tomonidagi akrobatlar uning ustidan sakrab o'tib o'zaro o'rin almashishadi. Boshqacha qilib aytganda to'pni qabul qilib olgan akrobatning joylashgan o'rni \(position\) bo'lsa \(position - 1\) va \(position + 1\) o'rinlaridagi akrobatlar o'zaro o'rin almashishadi.

Sizning vazifangiz berilgan ketma-ketlik uchun akrobatlar qachondir dam olishi mumkin yoki yo'qligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10^4)\) testlar soni kiritiladi.
Har bir testning dastlabki satrida bitta butun son, \(N( 1 \le N \le 2 \times 10^5)\) soni kiritiladi.

Keyingi satrda \(N\) ta butun son, \([1,..N]\) permutatsiya kiritiladi, ya'ni akrobatlarning futbolkasida yozilgan sonlar bo'yicha tartibi kiritiladi.

Barcha testlardagi \(N\) larning umumiy yig'indisi \(2 \times 10^5\) dan oshmasligi kafolatlanadi!

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda agar yuqorida keltirilgan amallarni bajargan holda akrobatlar futbolkasidagi sonlar bo'yicha tartiblangan holga kela olda YES aks holda NO so'zini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 1 2 2 1 3 3 2 1	YES NO YES

C. Chalg'ituvchi omillar

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Azizbek sport dasturlashga juda qiziqadi, bundan tashqari u matematikani ham juda yaxshi ko'radi. Shu sababli uning eng asosiy hobbilari bu sport dasturlash hamda matematika.

Uning har ikkala hobbisi ham uning sport dasturlash bo'yicha ICPC musobaqasiga ishtiroki natijasini yaxshilash uchun foydali.

Shu sababli Azizbekning ICPC musobaqasidagi jamoa rahbari Sirojiddin Azizbekning har qanday bo'sh vaqtini muntazam nazorat qiladi va har bir bo'sh vaqtida qaysi hobbi bilan shug'ullanishi kerakligini ham aniqlab beradi.

Ayni vaqtda Azizbekning kun davomidagi bo'sh vaqtlari \(N\) ta teng qismlarga bo'lingan. Sirojiddin Azizbekga shu \(N\) ta qismning har birida nima bilan mashg'ul bo'lishi kerakligini satr ko'rinishida tuzib bermoqda. Bu satr jami \(N\) uzunlikdagi faqatgina S va M belgilaridan tashkil topadi. Bu yerda S - sport dasturlash, M esa matematika ma'nosida keladi.

Azizbek Sirojiddinning topshirig'ini so'zsiz bajaradi. Ammo ba'zi omillar talabani chalg'itishi mumkinligini bilgan Sirojiddin o'zi tuzgan satrda chalg'ituvchi omil bo'lishini istamaydi.

Sirojiddinning fikricha satrda SMS hamda MSM satri bo'lmasligi kerak, chunki:

SMS - Short Message Service - Qisqa matnli xabar
MSM - Mainstream Media - Ommaviy axborot vositalari

Tabiiyki bu qisqartmalarni ko'rgan talaba albatta chalg'ish ehtimoli mavjud.

Shu sababli Sirojiddin o'zi tuzgan satrdan (mashg'ulotlar ketma-ketligidan) ba'zi belgilarni(mashg'ulotlarni) olib tashlamoqchi. Chunki Azizbek mashg'ulotlar vaqtida chalg'igandan ko'ra mashg'ulotlarni bajarib bo'lgach dam olgani yaxshiroq.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 2 \times 10^4)\)

dastlabki satrida bitta butun son, \(N (1 \le N \le 3 \times 10^5)\) Azizbekning bo'sh vaqtlari soni kiritiladi.

Keyingi satrda S va M harflaridan iborat \(N\) uzunlikdagi satr kiritiladi. Sirojiddinning Azizbek uchun dastlabki tuzgan rejasi.

Eslatma: Barcha testlardagi \(N\) larning umumiy yig'indisi \(3 \times 10^5\) dan oshmasligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Mashg'ulotlarni bajarish jarayonida Azizbek chalg'imasligi uchun Sirojiddin o'zi tuzgan satrdan eng kamida nechta belgini o'chirishi kerakligini aniqlang.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 12 SMSMSSMMSSMS	2

D. Kalkulyator o'yini

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Mardon va Husanboy kalkulyator o'yinini o'ynayapti.

O'yin sharti quyidagicha:

Dastlab kalkulyatorda \(N\) soni yozilgan.
O'yin navbatma-navbat amal bajarish orqali o'ynaladi.
Navbati kelgan o'yinchi quyidagi ikki amaldan birini bajaradi:
- Kalkulyatordagi sondan 1 ni ayiradi
- Ixtiyoriy \(x(1 < x)\) sonini tanlaydi (bunda kalkulyatordagi son \(x\) ga qoldiqsiz bo'linishi talab qilinadi) hamda kalkulyatordagi sonni \(x\) ga bo'lib yuboradi
O'yin kalkulyatordagi son \(0\) bo'lib qolguniga qadar davom etadi.
Kalkulyatordagi sonni \(0\) qiymatiga olib kelgan o'yinchi o'yinda g'alaba qozonadi.

O'yinda birinchi amal bajarishni Mardon boshlab bersa hamda har ikkala o'yinchi optimal harakat qilsa o'yinda kim g'alaba qozonishini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 10^3)\) testlar soni kiritiladi.

Keyingi \(T\) ta satrda bittadan butun son, navbatdagi o'yinda tanlangan \(N(1 \le N \le 10^9)\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Har bir o'yin uchun alohida qatorda o'yin g'olibining ismini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 2 3 234 1009	Husanboy Mardon Mardon Husanboy

E. Distinct values

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Sizga \(N\) ta nomanfiy butun sonlardan tashkil topgan \(A\) massiv bor.

Siz bir harakatda ixtiyoriy \(i(1 \le i \le N)\) sonini tanlab \(A_i = A_i \oplus1\) qilishingiz mumkin, boshqacha qilib aytganda uning juft/toq lik holatini o'zgartirishingiz mumkin. Siz bu amalni xoxlagancha marotaba bajarishingiz mumkin.

Sizning vazifangiz \(\sum_{i=1}^{N}{\sum_{j=i}^{N}{distinct([A_i, A_{i+1}, ...,A_j])}}\) ning qiymatini maksimallashtirish.

Bu yerda \(distinct([x_1, x_2, ..., x_k])\) funksiyasi \(k\) ta elementdan iborat \(x\) massividagi har xil qiymatlar soniga teng.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(N(1 \le N \le 3 \times 10^5)\) soni kiritiladi. Ikkinsi satrida \(N\) ta butun son, \(A (0 \le A_{i(1 \le i \le N)} < 2^{31})\) massiv elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Sizning amallaringizdan so'ng \(\sum_{i=1}^{N}{\sum_{j=i}^{N}{distinct([A_i, A_{i+1}, ...,A_j])}}\) ning mumkin bo'lgan maksimal qiymatini aniqlang.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	12 9 3 2 1 8 7 1000000000 999999999 7 1 2 0	356
2	1 0	1