A. Sardor va Behruz uchrashuvi

Xotira: 32 MB, Vaqt: 1000 ms

Tasavvur qiling, baland ofis binosi bor va qavatlar 1 dan N gacha raqamlangan. Sardor A-qavatdan boshlaydi, Behruz esa B-qavatdan. Har daqiqada ular hozir turgan qavatni tekshiradi; agar bir vaqtda bir xil qavatda bo‘lsa, uchrashib, jarayon muvaffaqiyatli tugaydi. Tekshiruvdan so‘ng, Sardor bir pog‘ona yuqoriga, Behruz esa bir pog‘ona pastga tushadi. Bu takrorlanadi, toki ular uchrashguncha yoki Sardor N-qavatga yetib, undan yuqoriga chiqa olmaguncha, yoki Behruz 1-qavatga yetib, undan pastga tusholmaguncha. Agar shu holatga kelib ham uchrashmasa, ular binoni tark etib, keyinroq uchrashishga kelishib oladi.

Berilgan N, A va B butun sonlari asosida aniqlang: ular shu jarayon davomida uchrashadimi?

1 <= N <= \(10^{12}\)

1 <= a,b <= N

5 3 4

NO

10 4 4

YES

12345 1 12345

YES

B. Asilbek International Master

Xotira: 32 MB, Vaqt: 1000 ms

Asilbek ancha vaqtdan beri codeforces da International Master darajasiga chiqishga harakat qilardi. Ammo har safar biroz yetmay qolardi. Shu safar ham juda oz qolgan. Hozirgi contestdan keyin International Masterga chiqa olishi uchun quyidagilarni bajarishi kerak:

1. Kamida X ball yig'ishi
2. Kamida Y ta masalani to'liq yecha olishi
3. Kamida Z ta masalada 0 dan yuqori ball olishi

Contestda masalalar soni 7 ta. Siz Asilbek shu contestda International Masterga chiqa oladimi yo'qmi aniqlashingiz kerak. Agar shartlarni bajara olsa "IM", bo'lmasa "IM emas" deb chiqaring. 

P.S: Asilbek International Masterga chiqdi. 

0 <= X <= 700

0 <= Y, Z <= 7

400 2 5
100 100 75 50 0 100 0

IM

500 3 4
100 100 100 0 0 0 0

IM emas

C. Eldor voleybol turnirida

Xotira: 32 MB, Vaqt: 1000 ms

Eldor kelajakdagi turnirga tayyorgarlik sifatida voleybolda to'p oshirib berishni mashq qilmoqda. Har bir mashg‘ulotda u N marta to'p oshirib beradi va har bir to'p oshirishi quyidagi uch holatdan birida to'g'ri keladi:

1. S: Muvaffaqiyatli, 1 ball.
2. P: Mukammal, 2 ball.
3. F: Xato, 0 ball.

Eldor ham biz kabi oddiy inson, shu sababli u bosim ostida hayajonlanadi:

• Agar bir holat “P” (mukammal) bo‘lsa, keyingi holat “P” bo‘la olmaydi.
• Agar ketma-ket K ta to'p oshirish muvaffaqiyatli yoki mukammal (ya’ni S yoki P) bo‘lsa, unda shundan keyingi to'p oshirish albatta “F” (xato) bo‘lishi kerak.

Eldorning mashg‘ulot yozuvi aralashib, boshqa odamlarning yozuvlari bilan aralashib qolgan. Sizga shug'ullanish jadvali (uzunligi N bo‘lgan S, P, F belgilardan tashkil topgan satr) beriladi. Bu jadval Eldorning qoidalariga to‘g‘ri kelishi mumkinmi? Agar mumkin bo‘lsa, YES va uning umumiy ballini (S=1, P=2, F=0 bo‘yicha yig‘indi) chiqaring. Aks holda NO ni chiqaring.

 \(1 <= K <= N <= 10^6\)

8 2
SSFSPFSF

YES
6

6 2
SPSPSP

NO

D. Jahonali va Timur o'yini

Xotira: 32 MB, Vaqt: 1000 ms

Jahonali va Timur Codeforces’ga juda qiziqish bilan qaraydigan do‘stlar. Ularning bir nechta Codeforces akkaunti bor, lekin ular qiziqarli “reyting o‘yini” o‘ylab topishdi: akkauntlarni bir-birlariga almashtirib olib, navbat bilan yurish qilishadi.

Boshlang‘ich holatda har bir akkauntda ma’lum bir butun reyting bor. Reytinglar ma'lum bir ketma-ketlikda joylashtirilgan va sizga massiv ko'rinishida beriladi.

Jahonali 1-harakat qiladi, keyin Timur, keyin Jahonali va hokazo navbat bilan.

Har bir o'yinchi o'z navbatida quyidagi amalni bajarishi kerak: 1 ta index tanlab undagi elementni 1 ga oshira yoki tushira oladi.

Jahonali o‘yin davomida quyidagi maqsadni ko‘zlaydi: barcha N akkauntning ratinglari ketma-ket joylashganda “o'zgaruvchan” shaklga kelsin, ya’ni:

Har bir indexdagi son oldidagi ikkala sondan ham qat'iy ravishda katta yoki ikkalasidan ham qat'iy ravishda kichik bo'lishi kerak.

Agar o'yinning qaysidir qismida ushbu barcha shartlar bajarilib, ratinglar ketma-ketligi o'zgaruvchan bo‘lib qolsa, o‘yin darhol to‘xtaydi va Jahonali g‘olib hisoblanadi.

Timurning maqsadi esa buning oldini olish. Agar u 10^9 ta umumiy harakat (Jahonali va Timur harakatlari qo‘shilganda) davomida ketma-ketlikni o'zgaruvchan holga keltirishni oldini olsa Timur o'yinda yutadi.

Faraz qilamizki, ikkisi ham mukammal o‘ynaydi ya'ni yutishi uchun eng yaxshi yurishlarni bajaradi.

Sizga boshlang‘ich N va har bir akkauntning dastlabki ratinglari beriladi. Siz agar Jahonali yutsa, nechta yurishdan keyin yutishini, Timur yutsa -1 ni chiqaring

1 <= A[i] <= \(10^6\)

1 <= N <= \(2*10^5\)

Note: Massivning ketma-ketligi bir xil turadi, ya'ni sonlar joyini almashtirish mumkin emas.

5
2 1 3 1 1

1

E. Sarvarning topshirig'i

Xotira: 32 MB, Vaqt: 2000 ms

Sarvar o‘quvchilari uchun interaktiv vazifa tayyorlamoqchi. U ulardan ikkita manfiy bo‘lmagan butun son, ya’ni a va b ni tanlashni so‘raydi. Bu sonlar quyidagi chegaralar orasida bo‘lishi kerak: 0 ≤ a ≤ A, 0 ≤b ≤ B, bu yerda A va B oldindan berilgan butun sonlardir. Vazifaning sharti shuki, tanlangan a va b yig‘indisi mukammal kvadrat bo‘lishi kerak. Ya’ni,  manfiy bo‘lmagan butun son c, a + b = \(c^2\) mavjud bo‘lsin.

Sarvar mashg‘ulotdan avval qancha to‘g‘ri juftlik (a,b) borligini aniqlamoqchi. A va B juda katta bo‘lishi mumkin va juftliklar soni ham juda katta chiqishi ehtimoli bor,shuning uchun javobni 998244353 ga bo‘lingan qoldiq sifatida berish kerak.

Bundan tashqari, Sarvar oldindan bir nechta mashg‘ulotlarni rejalashtirgan: jami T ta savol bo‘ladi (har bir mashg‘ulot uchun bittadan). Har bir savolda alohida A va B beriladi va har biri uchun to‘g‘ri juftliklar sonini 998244353 ning qoldig'i sifatida hisoblab chiqarish talab qilinadi.

1 <= T <= 1000

1 <= A, B <= \(10^{18}\)

3
3 5
9982 44353
123456789 123456789

7
1551747
923038039

F. NQ?

Xotira: 50 MB, Vaqt: 1300 ms

Sizga uzunligi \(n\) ga teng \(arr\) massiv berilgan. Sizning vazifangiz shu massiv ustidagi \(q\) ta so'rovni bajarish. So'rovlar 2 xil turda bo'ladi:

1.  Sizga \(k\) soni beriladi. \(arr\) massivdan ko'pi bilan 2 ta element tanlashingiz kerak va ularning yig'indisi \([k, 2k]\)da yotishi kerak. Agar shartni qanoatlantiruvchi elementlarni tanlash iloji bo'lsa  1 bo'lmasa 0 chiqaring.
2. Bu so'rov turida sizga \(i\) va \(x\) sonlari beriladi. Sizning vazifangiz \(sorted(arr)\) massivning \(i\) - elementini \(x\) ga almashtirish. \(0 \le i \le n-1\)

*Masalada indekslash 0 dan boshlanadi.

3 2
1 1 99
1 49
1 2

01