Stolda \(n\) ta askar doira shaklida joylashgan va soat yo'nalishi bo'yicha \(1\) dan \(n\) gacha raqamlangan. O'yin quyidagicha o'tkaziladi: \(1\)-raqamli askardan boshlab soat yo'nalishi bo'yicha sanaladi va har safar navbatdagi \(k\)-inchi askar doiradan chetlashtiriladi. Chetlashtirilgan askar hisobga olinmaydi, sanash chetlashtirilmagan askarlar orasida davom etadi. Bu jarayon doirada faqat bitta askar qolguncha davom etadi.
Oxirigacha qolgan (g'olib bo'lgan) askarning boshlang'ich raqamini toping.
Bitta qatorda ikkita butun son \(n\) va \(k\) beriladi (\(1 \le n \le 10^6, 1 \le k \le 10^9\)) — askarlar soni va har safar chetlashtiriladigan askarning tartib raqami.
G'olib bo'lgan askarning boshlang'ich raqamini chop eting.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
7 3 |
4 |
| 2 |
5 2 |
3 |
Siz raundning oxirgi tirik o'yinchisisiz — klassik \(1vN\) clutch holatidasiz. Qarshingizda n ta dushman qoldi, va siz ular bilan birma-bir, o'zingiz tanlagan tartibda jang qilasiz (masalan, xonalarni birin-ketin tekshirasiz).
i-dushman bilan jangga kirganingizda:
- \(p_i \)% ehtimol bilan siz g'alaba qozonasiz — bu holda \(r_i\) frag-ball olasiz va navbatdagi dushman bilan jangga o'tasiz.
- qolgan ehtimol bilan (100 - \(p_i\))% siz mag'lub bo'lasiz (o'lasiz) — round shu yerda tugaydi, qolgan dushmanlar bilan jang bo'lmaydi va ulardan ball ololmaysiz.
Sizga dushmanlar bilan jang qilish tartibini shunday tanlash kerakki, o'yin oxirida to'playdigan kutilgan (expected) umumiy ball eng katta bo'lsin.
- 1-qator: \(n (1 ≤ n ≤ 2×10^5)\)
- Keyingi n qatorning har birida: \(p_i, r_i — i\)-dushmanni yengish ehtimoli foizda \((1 ≤ p_i ≤ 100)\) va uni yengish uchun beriladigan frag-ball \((1 ≤ r_i ≤ 10^9)\)
Optimal tartibda o'ynalganda olinadigan maksimal kutilgan ballni chiqaring \(10^{-6}\) aniqlikda.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
2 50 100 90 10 |
54.500000 |
| 2 |
2 100 5 50 100 |
55.000000 |
| 3 |
3 50 100 90 10 20 50 |
59.000000 |
| 4 |
3 41 467 75 300 41 151 |
387.639825 |
Cho'lda uzun bir yo'l bor, va bu yo'l bo'ylab \(n\) ta joyda quduq qazilgan — ularning yo'l boshidan masofalari \(x_1, x_2, \dots, x_n\) (o'sish tartibida berilgan, barchasi turli). Yo'lovchilar karvoni shu quduqlardan \(m\) tasini tanlab, ularni dam olish bekati sifatida belgilamoqchi.
Issiqda charchamaslik uchun, tanlangan bekatlar orasidagi eng qisqa masofa iloji boricha katta bo'lishi kerak (ya'ni ikkita bekat bir-biriga juda yaqin bo'lib qolmasin). Karvon boshlig'i \(m\) ta bekatni shunday tanlamoqchi — eng yaqin turgan ikkita bekat orasidagi masofa maksimal bo'lsin.
Shu maksimal qiymatni toping.
Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi (\(2 \le m \le n \le 2 \times 10^5\)).
Ikkinchi qatorda \(n\) ta butun son \(x_1 < x_2 < \dots < x_n\) beriladi (\(0 \le x_i \le 10^9\)) — quduqlarning yo'l boshidan masofalari.
Tanlangan \(m\) ta bekat orasidagi eng qisqa masofaning maksimal mumkin bo'lgan qiymatini chop eting.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
5 3 1 2 4 8 9 |
3 |
| 2 |
5 3 1 2 100 101 200 |
99 |
Sizga \(n\) ta butun sondan iborat \(a_1, a_2, \dots, a_n\) massiv beriladi (o'sish tartibida joylashgan). Shuningdek, sizga \(t\) ta so'rov beriladi. Har bir so'rovda bitta \(q\) soni berilib — massivda shu son bor yoki yo'qligini aniqlashingiz talab etiladi.
Birinchi qatorda ikkita butun son \(n\) va \(t\) beriladi (\(1 \le n, t \le 2 \times 10^5\)).
Ikkinchi qatorda \(n\) ta butun son \(a_1 < a_2 < \dots < a_n\) beriladi (\(-10^9 \le a_i \le 10^9\)).
Keyingi \(t\) ta qatorning har birida bitta butun son \(q\) beriladi (\(-10^9 \le q \le 10^9\)) — qidirilayotgan son.
Har bir so'rov uchun alohida qatorda, agar \(q\) soni massivda mavjud bo'lsa "YES", aks holda "NO" deb chop eting.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
6 9 1 3 5 7 9 11 1 2 3 4 5 6 7 8 9 |
YES NO YES NO YES NO YES NO YES |
Qadim zamonlarda mashhur bo'lgan Feruz degan zargar ustaning bisotida n dona nodir munchoq saqlanar edi, ularning har biri o'ziga xos vaznga ega bo'lib, bu vaznlar \(a_1, a_2, \dots, a_n\) qiymatlar bilan ifodalanardi.
Ustaning bir g'alati odati bor edi: u ustaxonasini yopishdan burun, qo'lidagi munchoqlarni birma-bir savdogarlarga hadya qilib yuborardi. Biroq bu hadya jarayoni ixtiyoriy tartibda emas, balki qat'iy bir intizom asosida kechardi. Dastlabki hadya etiladigan munchoqni usta o'zi xohlagancha, erkin tanlab olardi. Ammo undan keyingi har bir qadamda hadya qilinadigan munchoqning vazni juftlik xususiyati jihatidan oldingi hadya etilgan munchoqnikidan albatta farqli bo'lishi shart edi: agar avvalgi munchoqning vazni toq son bo'lsa, endigisi so'zsiz juft son bo'lishi lozim edi, va aksincha. Qaysidir bosqichda ushbu talabga javob beradigan munchoq qolmasa, hadya jarayoni beixtiyor to'xtab qolardi, va shu topilgan zahoti qo'lida qolgan munchoqlar abadiy uning xazinasida saqlanib qolaverardi.
Feruz usta o'ta hisobli va tejamkor kishi bo'lgani bois, u o'z bisotida qolib ketadigan munchoqlarning umumiy vazni imkon qadar oz bo'lishini orzu qilardi. Shu maqsadda u dastlabki qadamda qaysi munchoqni tanlashni va har keyingi bosqichda qaysi mos munchoqqa qo'l urishni — aynan shu maqsad, ya'ni qo'lida qolib ketadigan munchoqlar vaznining yig'indisini eng kamiga tushirish — yo'lida hal etardi.
Sizdan talab qilinadigan: berilgan \(n\) ta munchoqning vaznlari asosida, Feruz usta eng unumli tarzda harakat qilganda, jarayon yakunida uning huzurida qolib ketadigan munchoqlar vaznining eng kichik mumkin bo'lgan yig'indisini toping.
Birinchi qatorda bitta butun son \(n (1 \le n \le 2000)\) — munchoqlar soni keltiriladi.
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 10^6)\) — har bir munchoqning vazni keltiriladi.
Yagona butun son — jarayon yakunlangach ustaning huzurida qolib ketgan munchoqlar vaznining minimal yig'indisi.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
5 1 5 7 8 2 |
0 |
| 2 |
6 5 1 2 4 6 3 |
0 |
| 3 |
2 1000000 1000000 |
1000000 |
Qadim zamonda, ipak yo'li ustida joylashgan gavjum bir shaharda, mohir hunarmand Sulton Mirzo yashar edi. U yiliga bir marta, muqaddas bayram arafasida, o'z shogirdlariga uchta buyuk hunar sirlarini — kulolchilik, to'qimachilik va zargarlik san'atini — o'rgatish uchun alohida kunlar tayinlar edi.
Ushbu tayyorgarlik \(n\) kunlik muddatga cho'zilgan bo'lib, har bir kunning o'ziga xos xususiyati bor edi: ma'lum bir kunda shaharning turli mahallalaridan kelib, ustaga yordam berishga va hunar sirlarini o'rganishga tayyor bo'lgan shogirdlar soni har xil edi. Aniqrog'i, \(i\)-kun uchun quyidagilar ma'lum edi:
Sulton Mirzoning qat'iy odati shunday ediki, u har bir hunar uchun alohida, boshqalaridan farqli bir kunni tanlashi shart edi — ya'ni kulolchilik uchun tanlangan kun, to'qimachilik yoki zargarlik uchun tanlangan kunlar bilan mos kelmasligi lozim edi. Boshqacha aytganda, \(n\) kun ichidan uchta har xil kun tanlanib, ularning har biri faqat bitta hunarga bag'ishlanardi.
Usta o'zining ustaxonasiga imkon qadar ko'proq shogird jalb qilishni, ya'ni tanlangan uchta kunda yig'iladigan shogirdlar sonining umumiy yig'indisini maksimal qilishni orzu qilardi.
Sizdan talab qilinadigan: har bir sinov uchun berilgan ma'lumotlar asosida, Sulton Mirzo qanday tanlov qilmasin, uchta turli kunni tanlab olib, ularda yig'iladigan shogirdlarning eng katta mumkin bo'lgan umumiy sonini toping.
Birinchi qatorda bitta butun son \(t (1 \le t \le 10^4) \)— sinovlar soni keltiriladi.
Har bir sinov uchun:
- Birinchi qatorda bitta butun son \(n (3 \le n \le 10^5)\) — tayyorgarlik kunlari soni;
- Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^8\)) — har bir kunda kulolchilikka tayyor shogirdlar soni;
- Uchinchi qatorda \(n\) ta butun son \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le 10^8\)) — har bir kunda to'qimachilikka tayyor shogirdlar soni;
- To'rtinchi qatorda \(n\) ta butun son \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 10^8\)) — har bir kunda zargarlikka tayyor shogirdlar soni.
Barcha sinovlardagi \(n\) qiymatlari yig'indisi \(10^5\) dan oshmaydi.
Har bir test uchun bitta butun son — tanlangan uchta turli kunda yig'ilishi mumkin bo'lgan shogirdlarning eng katta umumiy sonini chop eting.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
1 3 1 10 1 10 1 1 1 1 10 |
30 |
| 2 |
3 3 5 5 5 5 5 5 5 5 5 3 1 2 3 3 2 1 2 3 1 4 100 1 1 1 1 100 1 1 1 1 100 1 |
15 9 300 |
Qishloq bolalari orasida mashhur bo'lgan Beshtosh o'yinining bir varianti bor: yerga \(n\) ta g'uj-g'uj tosh uyumlari qo'yiladi, \(i\)-uyumda \(a_i\) dona tosh bo'ladi. Ikki o'yinchi — Anvar va Botir — navbat bilan yurish qiladi. Anvar birinchi bo'lib boshlaydi.
Har bir yurishda o'yinchi istalgan bitta uyumni tanlaydi va o'sha uyumdan kamida bitta, istagancha ko'p toshni olib tashlaydi (butun uyumni ham olib tashlash mumkin). Navbatida yura olmagan o'yinchi (ya'ni barcha uyumlar bo'sh bo'lib qolganda yurish kerak bo'lgan o'yinchi) yutqazadi.
Ikkala o'yinchi ham eng aqlli (optimal) tarzda o'ynaydi. Shu holatda kim g'olib chiqadi?
Nega bu qiziq?
Qarasangiz, uyumlar soni va toshlar joylashuvi juda xilma-xil bo'lishi mumkin — lekin g'alaba faqat bitta oddiy amalga bog'liq ekan: barcha \(a_i\) larning XOR (⊕) yig'indisi! Agar bu yig'indi 0 bo'lsa, boshlovchi (Anvar) qancha urinmasin albatta yutqazadi. Aks holda, u albatta g'olib strategiyasini topa oladi. Bu o'yinlar nazariyasining eng mashhur va "sehrli" natijalaridan biri.
1-qator: \(t\) (\(1 \le t \le 10^4\)) — sinovlar soni.
Har bir sinov uchun:
Barcha sinovlardagi n larning yig'indisi \(2 \times 10^5\) dan oshmaydi.
Har bir sinov uchun — kim g'olib bo'lishini chop eting: Anvar yoki Botir.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
2 3 1 2 3 2 3 4 |
Botir Anvar |
| 2 |
1 1 0 |
Botir |
| 3 |
1 1 5 |
Anvar |
1-test:
- [1,2,3]: \(1\oplus2\oplus3=0\) → boshlovchi (Anvar) yutqazadi → Botir
- [3,4]: \(3\oplus4=7\ne0\) → Anvar \(4\to3\) qiladi, \([3,3]\) hosil bo'ladi, so'ng oyna strategiyasi bilan g'olib chiqadi → Anvar
2-test:
[0] — tosh yo'q, Anvar yura olmaydi, zudlik bilan yutqazadi → Botir
3-test:
[5] — \(5\ne0\), Anvar hammasini bir yurishda oladi, Botirga yurish qolmaydi → Anvar
Qoida: \(\text{XOR} =0\) → boshlovchi yutqazadi; \(\text{XOR} \ne0\) → boshlovchi yutadi.
Ushbu masalada sizga \(8 \times 8\) maydonda bo'lib o'tadigan standart shaxmat o'yinining qaysidur jarayoni beriladi. Bu jarayonda yurish navbati sizga kelib qolgan va usha jarayonda faqatgina bitta yurish bilan raqibni mot qilishingiz kerak bo'ladi.
Misol: Agar siz oq toshlarda o'ynayotgan bo'lsangiz C5 da joylashgan ot ni D7 ga olib o'tish orqali raqibni bir marotaba yurishda mot qilish mumkin (1-test).
Shaxmat tosh donalari quyidagicha belgilanadi: King(shox) - K, Queen(farzin) - Q, Bishop(fil) - B, Knight(ot) - N, Rook(rux) - R va Pawn(piyoda) - P. Oq va qora toshlar mos ravishda katta kichik harflar bilan va bo'sh maydon nuqta bilan ifodalanadi.
Kirish faylining dastlabki satrida \(k\) (\(0 \le k \le 1\)) butun son ya'ni \(0\) yoki \(1\) bu mos ravishda siz o'yinni qora yoki oq toshlarda davom ettirishingizni anglatadi. Keyin \(8 \times 8\) maydonda o'yin jarayoni tasvirlanadi.
Siz shunday bir toshni boshqa maydonga kuchirish orqali shoxga hujum qilishingiz kerak netijada shox hujum ostida qolsin. Ko'chirilishi kerak bo'lgan toshning dastlabki va keyingi koordinatasini mos ravishda probil bilan ajratilgan holda (agar bunday yechimlar bir nechta bo'lsa istalganini) chop eting. Yechim mavjudligi kafolatlanadi.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
1 ...r.... .pk..... ...pP... ..N..... ........ ........ ........ ..R....K |
C5 D7 |
| 2 |
0 ....K.R. .Pp..P.P ....Bb.. ..pP.... R.....p. .......p ....r... .......k |
C7 C8 |
Piyoda harakati siz oq yoki qora toshlarda o'ynashingizdan qati nazar faqat bir tomonlama bo'ladi 2-testga qarang.