RoboContest

Xotira 256 MB Vaqt 2000 ms

14

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?

Kiruvchi ma'lumotlar:

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)$ .

Chiquvchi ma'lumotlar:

Agar optimal o'yinda Anvar g'olib bo'lsa “Anvar”, aks holda “Bobur” deb chiqaring.

Misollar

#	input.txt	output.txt
1	11 2 1 3 6 7	Anvar
2	20 1 3 6	Bobur

Izoh:

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.

RoboContest

Masala E

Toshlar o'yini Pro Max