5-daraja testi: Olimpiada

5-darajaOlimpiada — musobaqa mahorati33–40 darslar

Yigirma savol, 33–40 darslar bo’yicha. Bu darajada savollarning bir qismi algoritm haqida emas — qaror qabul qilish haqida. Olimpiadada ular ham xuddi shunday ball keltiradi.

Usullar

1n ≤ 20 chegarasi nimani ishora qiladi? A) n² B) 2ⁿ, bitmask C) n log n D) DP

Javobni ko'rish

B. 2²⁰ taxminan bir million. Shunchalik kichik chegara deyarli har doim ichki to’plamlarga ochiq taklif. (33-dars)

2To'plamga i elementini qanday qo'shasiz? A) m + i B) m | (1 << i) C) m & i D) m << i

Javobni ko'rish

B. Bor-yo’qligini (m >> i) & 1 bilan tekshirasiz. (33-dars)

3n gacha barcha tub sonlar kerak, n = 10⁶. Qaysi usul? A) Har sonni tekshirish B) Eratosfen elagi C) EKUB D) Modul arifmetikasi

Javobni ko'rish

B. Elak n log log n — deyarli chiziqli. Har sonni tekshirish esa n·sqrt(n). (34-dars)

4Modul ostida bo'lish qanday bajariladi? A) // bilan B) Teskari elementga ko'paytirish orqali C) Bo'lish mumkin emas D) % bilan

Javobni ko'rish

B. Modul tub bo’lsa teskari element pow(b, p - 2, p). (34-dars)

5C(n, k) ni n = 10⁶ uchun qanday hisoblaysiz? A) Paskal jadvali B) math.comb C) Faktoriallar + teskari element D) Rekursiya

Javobni ko'rish

C. Paskal jadvali n² katak talab qiladi va xotiraga sig’maydi. (35-dars)

6Uch nuqta bir chiziqda ekanini qanday tekshirasiz? A) Og'ishlarni solishtirish B) Vektor ko'paytmasi nolga tengmi C) Burchaklarni hisoblash D) Masofalarni solishtirish

Javobni ko'rish

B. Butun sonlarda, bo’lishsiz. Og’ish kasr son va u aniqlik yo’qotadi. (36-dars)

7Kirishni tez o'qish uchun nima yoziladi? A) input() B) sys.stdin.buffer.read().split() C) open(0).read() D) int(input()) siklda

Javobni ko'rish

B. Bir marta o’qish va C tilidagi split. Bu ikki qator olimpiadadagi har Python yechimining boshida turadi. (37-dars)

Murakkablik va chegaralar

8Bitmask DP da holatlar soni qancha? A) 2ⁿ B) 2ᵏ, k — belgilar soni C) n! D) n²

Javobni ko'rish

B. Tanlovlar emas, erishilgan to’plamlar sanaladi — 27-darsdagi knapsack bilan bir xil fikr. (33-dars)

9Elakda tashqi sikl qayergacha yuradi? A) n gacha B) n/2 gacha C) sqrt(n) gacha D) log n gacha

Javobni ko'rish

C. Undan katta p uchun p·p allaqachon n dan oshgan. (34-dars)

10Bir xil murakkablikdagi ikki Python yechimi qancha farq qilishi mumkin? A) Farq qilmaydi B) 2 barobar C) O'nlab barobar D) Faqat xotirada

Javobni ko'rish

C. Konstanta murakkablik bahosida ko’rinmaydi, lekin ball keltiradi. (37-dars)

11Python C++ dan taxminan qancha sekin ishlaydi? A) Bir xil B) 2 barobar C) 10–50 barobar D) 1000 barobar

Javobni ko'rish

C. Shu sababli n ≤ 10⁵ masalalar Python’da o’tadi, n = 10⁷ da esa optimal algoritm ham yetmasligi mumkin. (37-dars va C++ sahifasi)

12Uchliklarni sanashda javob nega uchga bo'linadi? A) Formula shunday B) Har uchlik uch marta — har uchidan bir marta — sanaladi C) Xatoni tuzatish uchun D) Modul sababli

Javobni ko'rish

B. (36-dars)

Xato topish

13maska & i bilan i-bit tekshirildi. Nima xato? A) Hech narsa B) Bu i sonining bitlarini tekshiradi C) Sekin ishlaydi D) Xato xabari chiqadi

Javobni ko'rish

B. To’g’ri shakl: maska & (1 << i) yoki (maska >> i) & 1. (33-dars)

14Modul ostida (a * b) // c % p yozildi. Natija? A) To'g'ri B) Umuman boshqa son C) Xato xabari D) Manfiy son

Javobni ko'rish

B. Qoldiq olingandan keyin bo’linish xossasi buzilgan bo’ladi. Teskari element kerak. (34-dars)

15C(a, b) da b > a holati tekshirilmadi. Nima bo'ladi? A) Nol qaytadi B) Manfiy indeks tufayli tasodifiy son qaytadi C) Xato xabari D) Cheksiz sikl

Javobni ko'rish

B. Python manfiy indeksni ro’yxat oxiridan oladi — yechim xato bermay noto’g’ri javob beradi. (35-dars)

16Geometriyada og'ish (dy/dx) ishlatildi. Ikki muammo qanday? A) Sekin va uzun B) Nolga bo'lish va kasr taqqoslash C) Xotira va vaqt D) Muammo yo'q

Javobni ko'rish

B. Vertikal chiziqda nolga bo’lish, kasr sonlarni == bilan solishtirish esa ishonchsiz. (36-dars)

17C++ da million ta milliardgacha son int ga yig'ildi. Natija? A) Xato xabari B) Jimgina buziladi C) Sekinlashadi D) To'g'ri ishlaydi

Javobni ko'rish

B. int taxminan 2·10⁹ gacha. long long kerak. (37-dars va C++ sahifasi)

18Yechim O(n log n), chegaraga sig'adi, lekin vaqtdan oshdi. Birinchi navbatda nima tekshiriladi? A) Til B) Kirish-chiqish C) Algoritm D) Xotira

Javobni ko'rish

B. input() va har qatordagi print ko’p holatda butun muammoning sababi. Til almashtirish — oxirgi chora. (37-dars)

Strategiya

19G'oya topilmagan masalaga qancha vaqt beriladi? A) Cheksiz B) 15 daqiqa, keyin belgilab qo'yib boshqasiga C) Butun musobaqa D) 5 daqiqa

Javobni ko'rish

B. Keyinroq qaytiladi — miya orada ustida ishlashda davom etadi. (39-dars)

20Musobaqadan keyin nima qilinadi? A) Yechilgan kodni tozalash B) Tahlilni o'qish C) Yechilmaganlarni o'zingiz yozib, qabul qilinishiga erishish D) Keyingi musobaqaga o'tish

Javobni ko'rish

C. Tahlilni o’qish yetarli emas: o’qiganda tushunarli ko’ringan narsa yozganda o’nlab nozik joy chiqaradi. (40-dars)

Modul tugadi

Bu oxirgi test. Agar to’rttadan kam xato qilgan bo’lsangiz — besh daraja o’zlashtirilgan va sizda olimpiadaga borish uchun yetarli asos bor.

Endi bitta narsa qoladi: haftada kamida bitta virtual musobaqa va har birida upsolving. Usullar ro’yxati tugadi, mashq esa tugamaydi — va aynan mashq natija beradi.

Yo’lni davom ettirish uchun: 40-dars dagi musobaqa formati, CSES to’plami va o’qituvchingizdagi olimpiada yo’li kalendari.