A. Interstellar

Xotira: 256 MB, Vaqt: 1000 ms

Barchangiz Interstellar kinosini ko'rgan bo'lsangiz kerak. Jozef Kuper qizi Merfning yoniga qaytishi kerak. U hozir haftaning \(N-\)kunida, Merf esa haftaning \(M-\)kunida. U maqsadiga erishish uchun yo Merf turgan kun kelishini kutishi, yoki vaqt mashinasidan foydalanib o'tmishga (orqaga) qaytishi mumkin, bunda 1 kunga orqaga qaytish 1 kun vaqt oladi.

Hafta kunlariga quyidagicha raqamlar berilgan: Dushanba = 1, Seshanba = 2, ..., Yakshanba = 7. Merfning yoniga yetib borish uchun talab qilinadigan minimal kunlar sonini toping.

3
1 2
2 4
3 7

1
2
3

B. Ma'lumot xavfsizligi

Xotira: 256 MB, Vaqt: 1000 ms

Shohruh yangi kompaniyada ish boshladi. Uning ishi berilgan maxfiy ma'lumotni messenjer orqali kerakli insonga xavfsiz yetkazish. Hech qaysi messenjer to'liq maxfiylikni ta'minlay olmaydi, shu sababli maxfiy ma'lumotni yashirishi kerak. Buning uchun u ma'lumotga o'zgartirishlar kiritishi, unga qo'shimcha belgilar joylashtirishi lozim. Shohruh bu ishda hali yangi bo'lganligi sabab, matndan ba'zi harflarni o'chirib qo'ygan bo'lishi mumkin. Maxfiy ma'lumotni bilgan holda, Shohruh uni to'g'ri shiflragan yo xatolikka yo'l qo'yganini aniqlang.

salom
sabllom

YES

salom
slaom

NO

C. Qadimiy sivilizatsiya

Xotira: 256 MB, Vaqt: 1000 ms

Asilbek tarixiy manbalardan qadimiy bir sivilizatsiya haqida bilib oldi. Ushbu sivilizatsiya o‘z davrida juda yuqori darajada rivojlangan bo‘lib, transport tizimi ham shular jumlasidandir. Arxeologik tadqiqotlar natijasida aniqlanishicha, sivilizatsiya eng gullab-yashnagan davrida \(n\) ta shahar mavjud bo‘lgan va ular \(1\) dan \(n\) gacha raqamlangan.

Shaharlar orasida jami \(m\) ta yo‘l mavjud bo‘lib, har bir yo‘l ikki shaharni bog‘laydi. Bir juft shahar orasida bir nechta yo‘l bo‘lishiga ham ruxsat etiladi.

Ma’lumki, ushbu transport tarmog‘i quyidagi ikki shartni qanoatlantirgan:

1. Har qanday yo‘l \(u\) va \(v\) shaharlarini bog‘lasa, u holda
\(1 \le |u - v| \le K\) sharti bajarilishi kerak.

2. Har bir shahar bilan tutashgan yo‘llar soni juft bo‘lishi shart (0 ham juft son hisoblanadi).

Afsuski, aniq transport tarmog‘i bizgacha yetib kelmagan. Sizdan yuqoridagi shartlarni qanoatlantiradigan barcha mumkin bo‘lgan transport tarmoqlari sonini aniqlash talab etiladi.

Ikki xil transport tarmog‘i faqat va faqat shunday holatda turlicha hisoblanadi: agar kamida bitta shahar jufti mavjud bo‘lib, ular orasidagi yo‘llar soni ikki tarmoqda har xil bo‘lsa.

Natija juda katta bo‘lishi mumkinligi sababli, javobni \(10^9 + 7\) ga bo‘lgandagi qoldiqda chiqaring.
 

3 4 1

3

5 2 3

9

6 30 5

595145665

D. Kazino: taxminiy natija

Xotira: 256 MB, Vaqt: 1000 ms

Qishning sovuq va zerikarli kunlarida Shohruh o'ziga yangi quvonch izlab kazinoga yo'l oldi. U yerda "Aqllilar o'yini" deb nomlangan ajabtovur o'yinga ko'zi tushdi.

O'yin qoidalari quyidagicha:

• Kazinoning sirli generatori ketma-ket \(K\) marta, har gal \(N\) xil sovg'alardan tasodifiy birini taklif qiladi.
• Har bir raundda, Shohruhga bir sovg'a chiqariladi va u bevosita qaror qabul qilishi kerak: oladimi yoki rad etadimi?
• Agar Shohruh sovg'ani rad etsa, u sovg'a g‘oyib bo’ladi va keyingi bosqichga o‘tiladi (ortga qayta olib bo‘lmaydi!).

Har bir sovg'a turi bir xil ehtimollikda chiqadi va raundlar bir-biriga bog‘liq emas.
Hatto ketma-ket bir necha bor bir xil sovg'a chiqishi ham mumkin.
Yuqoridagi o'yinda, Shohruh \(P_i\) ball olib keladigan \(i\)-tur sovg‘ani olishni xohlashi mumkin. Biroq, har bir \(i\)-tur sovg'aning "majburiy to'plami" – ya’ni olishdan oldin to'plashi shart bo'lgan sovg'alar ro‘yxati \(S_i\) bor.

Shohruh faqat \(S_i\) to‘plamidagi barcha sovg’alarni oldin olganidan keyin \(i\)-tur sovg‘ani olishi mumkin.

(Agar hali ololmaydigan sovg'a chiqsa va u o'sha paytda rad qilinadigan holatda bo‘lsa, bu imkoniyat havoga uchdi deganidir!)

Optimal strategiyaga rioya qilgan holda, Shohruh ushbu o'yindan olish mumkin bo'lgan o'rtacha balining qiymati qancha bo‘ladi?

5 2
-10 0

100 1 
1

143.75000

20 10
152 0

91 0

292 3
2 5 7
-102 0

-849 3
3 4 10
777 3
2 5 9
299 2
2 5
520 1
4
-541 0

590 0

2161.74902

5 1
-5 0

0.00000

E. Kazino: Aniq yutuqlar

Xotira: 256 MB, Vaqt: 3000 ms

Monakodagi eng mashhur kazino — Casino de Monte-Carlo. U XIX asrda ochilgan va Monakoning iqtisodiy rivojida katta rol o‘ynagan. Bu yerda ruletka, blekjek, bakara va poker kabi klassik o‘yinlar mavjud. Qiziq jihati: Monako fuqarolariga kazinoda o‘ynash taqiqlangan, kazinolar asosan sayyohlar uchun.

Kazino ma'muriyati yangi turdagi strategik o'yinni e'lon qildi. Unda \(N\) ta professional ishtirokchi (o'yinchi) qatnashadi. Joylashuv bo'yicha \(1-\)raqamli o'yinchi eng yuqorida turadi. Qolgan har bir \(i\) (\(2 \le i \le N\)) ishtirokchining o'z ustozi \(f_i\) bor (\(f_i < i\)).

O'yin qoidalari:

1. Har bir ishtirokchi \(i\) o'zining kapitali  \(h_i\) ga ega. 
2. Agar mijozning joriy kapitali u to'qnash kelgan ishtirokchining \(h_i\) qiymatidan kichik bo'lmasa (kapital \(\ge h_i\)), mijoz g'alaba qozonadi va ierarxiya bo'yicha yuqoriga — \(f_i\) ishtirokchi tomon yo'l oladi.
3. Har bir g'alabadan so'ng mijozning kapitali o'sha stol qoidasiga ko'ra o'zgaradi:
  - Agar \(a_i = 0\) bo'lsa: kapitalga \(v_i\) qo'shiladi.
  - Agar \(a_i = 1\) bo'lsa: kapital \(v_i\) martaga ko'payadi.
4. Agar kapital \(h_i\) dan kichik bo'lsa, mijoz yutqazadi va o'sha stolda to'xtaydi.
5. O'yin mijoz \(1-\)raqamli ishtirokchini yengib o'tguncha yoki mag'lub bo'lguncha davom etadi.

\(Q\) ta so'rov berilgan, har bir so'rovda mijoz o'yinni ma'lum bir \(c_j\) ishtirokchidan boshlaydi va o'zi bilan \(s_j\) miqdordagi boshlang'ich kapitalni olib keladi. Har bir mijoz uchun, u necha marta g'alaba qozonishi mumkinligini aniqlashda yordam bering. 

3 2
10 5 20
1 0 10
2 1 5
10 2
1 3

2 0