Masala #LPXWWSNCDW
Toshlar o'yini Pro Max
Anvar va Bobur yangi stol o'yinini o'ynashmoqda. Stolda \(N\)ta tosh bor. O'yin qoidalariga ko'ra \(K\) xil mumkin bo'lgan \(L[i], R[i]\) oraliqlar bor.
Navbati kelgan ishtirokchi stoldan bir-nechta toshlarni olishi kerak, bunda olingan toshlar soni mumkin bo'lgan ixtiyoriy oraliqqa tegishli bo'lishi kerak. Xususan, o'yinchi \(X\)ta tosh olishi uchun, qaysidir \(1 \le i \le K\) uchun \(L[i] \le X \le R[i]\) shart bajarilishi lozim. Yurish amalga oshira olmaydigan ishtirokchi o'yinda yutqazadi.
Agar o'yinni Anvar boshlasa va ikkala ishtirokchi ham optimal o'ynashsa, o'yinda kim g'alaba qozonadi?
Birinchi qatorda \(N\) va \(K\) sonlari beriladi. \((1 \le N \le 10^6)\) va \((1 \le K \le 100)\).
Keyingi \(K\)ta qatorda ikkitadan butun son, \(L[i]\) va \(R[i]\) beriladi. \((1 \le L[i] \le R[i] \le N)\).
Agar optimal o'yinda Anvar g'olib bo'lsa “Anvar”, aks holda “Bobur” deb chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
11 2 1 3 6 7 |
Anvar |
| 2 |
20 1 3 6 |
Bobur |
Birinchi misolda \(N=11\), berilgan oraliqlar \([1;3]\) va \([6; 7]\). Ya'ni bitta yurishda 1, 2, 3, 6, yoki 7ta tosh olish mumkin.
Anvarning strategiyasi birinchi yurishda 7ta tosh olish. Shunda stolda 4ta tosh qoladi. Shundan so'ng:
- Agar Bobur 1ta tosh olsa, Anvar 3ta tosh oladi va g'alaba qozonadi.
- Agar Bobur 2ta tosh olsa, Anvar 2ta tosh oladi va g'alaba qozonadi.
- Agar Bobur 3ta tosh olsa, Anvar 1ta tosh oladi va g'alaba qozonadi.
Demak, Boburning qanday o'ynashidan qat'iy nazar Anvarda yutish strategiyasi bor.
Telegram kanalimizga obuna bo'ling