A. Qurbaqa

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Qurbaqa 1 dan boshlab raqamlangan cheksiz toshlarning \(a\) raqamli toshida o'tiribdi. Qurbaqa bir sakrashda agar \(x\) raqamli toshda turgan bo'lgan bo'lsa \(2 \times x\) yoki \(2 \times x +1\) toshga sakrashi mumkin. Qurbaqa b raqamli toshga bora oladimi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t\) - testlar soni kiritiladi.

Keyingi \(t\) qatorning har birida 2 tadan butun son - \(a\) va \(b\) kiritiladi.

\(1 \le t \le 1000\)

\(1 \le a \le b \le 10^{18}\)

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda, agar b raqamli toshga sakrashning iloji bo'lsa “Yes”, aks holda “No” yozuvini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 2 12 3 12	No Yes
2	3 5 5 5 85 7 64	Yes Yes No

B. String

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga 2 ta satr berilgan. Siz bu ikki satrlar ustida quyidagi amallarni bajarish orqali bir-biriga tenglashingiz kerak:

istalgan satrni tanlang va bu satrning bitta belgisini o'chirib yuboring
istalgan satrni tanlang va bu satrning 2 ta belgisi joylashuvini o'zgartiring

Yuqorida berilgan topshiriqni bajargandan so'ng, mumkin bo'lgan eng uzun satr uzunligini chop eting.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(s\) stringi (\(|s|≤10^5\))
Ikkinchi qatorda \(t\) stringi (\(|t|≤10^5\))
Ikkala string ham lotin alifbosining kichik harflaridan tashkil topgan.

Chiquvchi ma'lumotlar:

Bitta yagona qatorda \(s\) ning maximum uzunligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	dbcd bdaacd	4
2	cd bb	0
3	ddcacdb ddccca	5

C. Hosil to'plash

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Robolandiyada hosil yig'ib olish mavsumi boshlandi. U yerlik dasturchilar va injenerlar birgalikda hosil yig'ish qurilmasini ishlab chiqdi. Bu yil barcha hosil ushbu texnika yordamida yig'iladigan bo'ldi. Qurilma quyidagicha ishlaydi:

Ish boshida qurilma 1 tonna meva yig'a oladi.
Har bir terimda qurilma o'z terish hajmiga teng miqdorda olma yig'adi va konteynerga yuklaydi. Bu uchun 1 miqdor yoqilg'i sarflanadi.
Keyingi terishda qurilma xohishiga ko'ra o'z hajmini 2 baravarga oshiradi yoki shu holda davom ettiradi.

Yirik eksport kompaniyasi X tonna olma sotib olmoqchi. Mevalar isrof bo'lmasligi uchun aynan X tonna meva yig'ib berish zarur. Yoqilg'ini tejash maqsadida esa terimlar sonini imkon qadar kamroq qilish kerak. Kompaniyaga aynan X tonna mahsulotni yig'ib berish uchun qancha yoqilg'i zarur?

Kiruvchi ma'lumotlar:

Yagona qatorda butun X soni kiritiladi.

\(1 \le X \le 10^{18}\)

Chiquvchi ma'lumotlar:

X tonna hosilni yig'ishtirib olish uchun mumkin bo'lgan minimum yoqilg'i qiymatini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	50	8
2	100	9
3	30	8

D. K MEX

Xotira: 256 MB, Vaqt: 300 ms

Masala

N ta natural sondan tashkil topgan A massivi berilgan. Massivda uchramaydigan va K ga karrali bo'lgan eng kichik natural sonni aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va K kiritiladi.

Keyingi qatorda N ta butun son - A massivi elementlari kiritiladi.

\(1 \le N \le 10^6\)

\(1 \le K \le 10^{12}\)

\(1 \le A_i \le 10^{18}\)

Chiquvchi ma'lumotlar:

Javobni chop eting.

Vaqt va xotira chegarasiga e'tiborli bo'ling!!!

Python uchun yechimlarni pypy kompilyatorida yuboring!!!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 2 3 8 1 2 4 10	6

E. Robotlar

Xotira: 256 MB, Vaqt: 5000 ms

Masala

Robolandiya 1 dan N gacha ketma-ket raqamlangan shaharlardan iborat robotlar “uyi”, ya'ni har bir shahar robot ishlab chiqarish bilan shug'ullananadi. Har bir shahar xaridor talabiga ko'ra robotlar uchun narxni o'zi belgilaydi. Yaqin kunlarda uzoq o'lkalardan mehmonlar tashrif buyuradi. Har bir xaridor \([l, r]\) oralig'idagi shaharlarni aylanadi va ushbu shaharlar ichidagi eng arzon narxdagi robotni, agar puli yetsa xarid qiladi. Aks holda hech narsa xarid qilmaydi. Xaridorlar ko'pligi uchun shaharlar robot narxini belgilashda sizdan yordam so'ramoqda. Robolandiya oladigan foyda maksimal bo'ladigan narxlarni aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(M\) - shaharlar va turistlar soni kiritiladi.

Keyingi \(M\) ta qatorning har birida uchtadan son \(a_i, b_i, c_i\) - har bir turist sayohatni qayerdan boshlashi, qaysi shaharda tugatishi va byudjet miqdori kiritiladi.

\(1 \le N \le 50\)

\(1 \le M \le 4000\)

\(1 \le a_i \le b_i \le N\)

\(1 \le c_i \le 5 \times 10^5\)

Chiquvchi ma'lumotlar:

Birinchi qatorda maksimal foyda qiymatini chop eting.

Keyingi qatorda har bir shahar uchun optimal narxni chop eting. Maksimal summani bir necha xil usulda olish mumkin bo'lsa istalganini chop etishingiz mumkin. Har bir shahar uchun narx \([1, 500000]\) oralig'ida bo'lishi zarur.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7 5 1 4 7 3 7 13 5 6 20 6 7 1 1 2 5	43 5 5 13 13 20 20 13
2	5 4 1 4 10 1 4 9 1 4 1 1 4 3	18 9 9 9 9 1