39-dars: Musobaqa strategiyasi

5-darajaOlimpiada — musobaqa mahorati33–40 darslar

HayotdaMusobaqa

Uch soat tugadi. Ikki o’quvchining bilimi teng edi, lekin biri uch masala yechdi, ikkinchisi bittasini. Farq bitta narsada: birinchisi eng qiyin masalaga bir yarim soat sarflamadi. Bilim teng bo’lganda vaqtni boshqarish hal qiladi.

Bu darsdan keyin siz

• uch soatlik musobaqa uchun vaqt rejasi tuzasiz
• masalani qachon tashlab ketish kerakligini bilasiz
• qisman ball uchun ataylab to’liq izlash yozasiz

Avval qo’lda

Avval qo‘lda

~7 daqiqa·juftlikda·Qog'oz va qalam

Uch soatlik musobaqa uchun rejangizni qog’ozga yozing: har yarim soatda nima qilasiz? Beshta masala bor, ulardan ikkitasi oson, ikkitasi o’rta, biri juda qiyin.

Keyin sinfdoshingiz bilan rejalarni almashib, bir-biringizga bitta savol bering: «bu rejada eng katta xavf nimada?»

Nimani sezishingiz kerak

Deyarli har rejadagi xavf bir xil: bitta masalaga tiqilib qolish. Reja aynan shundan saqlaydi — u nima qilishni emas, qachon to’xtashni aytadi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Uch soatlik reja

Reja qat’iy qonun emas, lekin u bitta narsani ta’minlaydi: hech bir masala qolganlarini yeb ketmaydi.

Vaqt	Nima qilinadi
0–30	Barchasini o’qib chiqish, chegaralarni yozish, qiyinlikni baholash
30–60	Eng oson ikkitasini yechish
60–90	O’rta masalaga o’tish. G’oya 15 daqiqada topilmasa — belgilab qo’yib keyingisiga
90–120	Tashlab ketilganlarga qaytish
120–150	To’liq yechim chiqmasa, qisman ball uchun to’liq izlash
150–180	Yangi masala boshlamaslik. Chegara holatlarini sinash

▲Bu yerda xato qilishadi

Birinchi yarim soatda hech narsa yozilmaydi va bu yo’qotilgan vaqt emas. Masalalarni o’qimasdan boshlagan o’quvchi eng qiyinini birinchi bo’lib tanlab olishi mumkin — bu musobaqaning eng qimmat xatosi.

Qachon tashlab ketish

Qoida oddiy va uni oldindan kelishib qo’yish kerak, aks holda o’sha paytda qaror qabul qila olmaysiz.

G’oya yo’q bo’lsa — 15 daqiqa. Shu vaqt ichida hech qanday yondashuv ko’rinmasa, masalani belgilab qo’yib boshqasiga o’tiladi. Miya orada ustida ishlashda davom etadi.

G’oya bor, lekin kod ishlamayotgan bo’lsa — 25 daqiqa. Bu holatda tashlab ketish qiyinroq, chunki «yana ozgina» degan tuyg’u bor. Aynan shu tuyg’u ikki masalani yo’qotadi.

Uchinchi marta qaytganda — tashlab ketiladi. Bir masalaga uch marta qaytib, hali ham yechilmagan bo’lsa, qolgan vaqt boshqa joyda ko’proq ball beradi.

Qisman ball

qisman ballpartial score

To’liq bo’lmagan yechim uchun beriladigan ball. IOI turidagi musobaqalarda testlar guruhlarga bo’linadi va kichik chegaralar uchun alohida ball ajratiladi.

Bu eng ko’p e’tiborsiz qoldiriladigan imkoniyat. Shart odatda shunday yozilgan bo’ladi: «1-guruh: n ≤ 20, 20 ball. 2-guruh: n ≤ 1000, 30 ball. 3-guruh: n ≤ 10⁵, 50 ball».

Ya’ni to’liq izlash 20 ball keltiradi. n² yechim yana 30 ball. Optimal yechim topilmasa ham, 50 ball nol baldan besh barobar yaxshi.

qisman ball uchun shablonNusxalash

1# Har masalada birinchi yozadigan narsa — to'liq izlash.2# U tez yoziladi, qisman ball keltiradi va tez yechim uchun3# etalon bo'lib qoladi (15-dars).4import sys5def toliq_izlash(a):6  eng = 07  n = len(a)8  for maska in range(1 << n):9      # ... har variantni tekshirish10      pass11  return eng

Tekshirish tartibi

Oxirgi yarim soat yangi masala uchun emas. U mavjud yechimlarni sindirish uchun. Har yechimda quyidagi ro’yxat o’tiladi va u 15-darsdagi jadvalning qisqartmasi.

n = 1 bo’lsa ishlaydimi. Barcha sonlar bir xil bo’lsa. Barcha sonlar manfiy bo’lsa. Javob nol bo’lsa. Eng katta chegarada vaqt yetadimi. Va oxirgisi — kirish-chiqish tez o’qilganmi (37-dars).

◆Asosiy g'oya

Stress-test bu yerda ham ishlaydi. Sizda allaqachon to’liq izlash yechimi bor (qisman ball uchun yozgansiz), demak python mashqlar/stress.py uchun hamma narsa tayyor: sekin yechim, tez yechim va generator.

Sinab ko’r

Vizualda uch soatlik reja bo’lak-bo’lak ko’rib chiqiladi.

Uch soatlik reja

Har bo'lakda bitta vazifa. Rejaning maqsadi — bitta masalaga tiqilib qolmaslik.

Musobaqa vaqti bo'laklarga bo'linadi: o'qish, oson masalalar, o'rtalari, qaytish, qisman ball va tekshirish.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Uch soat, besh masala. Reja bo'lmasa vaqt eng qiyin masalaga ketadi va oson ikkitasi yechilmay qoladi — bu eng ko'p uchraydigan yo'qotish.
2. 0-30 daqiqa — o'qish. Barcha masalani o'qib chiqing va chegaralarni yozing. Hech narsa yozilmaydi — bu yo'qotilgan vaqt emas, sarmoya.
3. 30-60 daqiqa — oson. Eng oson ko'ringan ikkitasini yeching. Erta ball ishonch beradi va reyting jadvalida joy oladi.
4. 60-90 daqiqa — o'rta. Keyingi masalaga o'ting. Yechim g'oyasi 15 daqiqada topilmasa — belgilab qo'yib, boshqasiga.
5. 90-120 daqiqa — qaytish. Tashlab ketilganlarga qayting. Miya orada ustida ishlagan bo'ladi — bu haqiqatan ishlaydi.
6. 120-150 daqiqa — qisman. To'liq yechim chiqmasa, qisman ball uchun to'liq izlash yozing. Nol baldan har doim yaxshi.
7. 150-180 daqiqa — tekshirish. Yangi masala boshlamang. Chegara holatlarini sinang: n = 1, bo'sh kirish, maksimal chegara.
8. Reja qat'iy qonun emas, lekin u bitta narsadan saqlaydi: bitta masalaga tiqilib qolib, qolganlarini umuman ko'rmaslikdan.

daqiqa

0-30030-60160-90290-1203120-1504150-1805

reja

Uch soat, besh masala. Reja bo'lmasa vaqt eng qiyin masalaga ketadi va oson ikkitasi yechilmay qoladi — bu eng ko'p uchraydigan yo'qotish.

O'tgan daqiqa0

OrqagaO‘ynatishOldinga1/8Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

39 / 40

VaziyatUch soatdan 40 daqiqa qoldi. Ikki masala yechilgan, uchinchisining g'oyasi topildi, lekin kod hali ishlamaydi.

Taklif qilingan qaror

1. 1G‘oya to‘g‘ri, demak kodda kichik xato bor.
2. 2Xatoni topsam uchinchi masala ham hisobga o‘tadi.
3. 3Qolgan 40 daqiqani shu masalaga sarflayman.
4. 4Vaqt yetmasa, hech bo‘lmasa urinib ko‘rgan bo‘laman.

Bu javobning 3-qismi noto'g'ri. 40 daqiqani bitta masalaga to'liq sarflash — qimor. To'g'ri qaror: 15–20 daqiqa shu masalaga, qolgan vaqt esa yechilgan ikkitasini tekshirishga va to'rtinchi masalaning qisman balliga. Yechilgan masalada topilmagan chegara xatosi butun ballni yo'qotadi — bu esa uchinchi masaladan qimmatroq.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Birinchi yarim soatda nima qilinadi?

Javobni ko'rish

Barcha masalalarni o’qib chiqish va chegaralarni yozish. Kod yozilmaydi — bu sarmoya, yo’qotish emas.

2G'oya topilmasa masalaga qancha vaqt beriladi?

Javobni ko'rish

15 daqiqa. Keyin belgilab qo’yib boshqasiga o’tiladi va keyinroq qaytiladi.

3Qisman ball nima va u nega muhim?

Javobni ko'rish

To’liq bo’lmagan yechim uchun beriladigan ball. To’liq izlash odatda kichik chegara guruhini oladi — bu nol baldan ancha yaxshi.

4Oxirgi yarim soat nimaga sarflanadi?

Javobni ko'rish

Mavjud yechimlarni tekshirishga: chegara holatlari va kirish-chiqish tezligi. Yangi masala boshlanmaydi.

5Nima uchun mavjud ballni himoya qilish afzal?

Javobni ko'rish

Yechilgan masaladagi topilmagan xato butun ballni yo’qotadi. Yangi masala esa faqat qo’shimcha — u ham hali topilmagan.

Masalalar

Mashq uchun: vaqt bilan yechish

3 ta

• CSES Introductory ProblemsCSESoson

  Beshtasini tanlab, 90 daqiqa qo‘yib yeching. Vaqt tugagach to‘xtang, keyin tahlil qiling.

• Codeforces Div. 3 arxiviCodeforceso'rta

  Virtual musobaqa rejimida qatnashing — vaqt haqiqiy musobaqadagidek hisoblanadi.

• USACO Bronza arxiviUSACOo'rta

  Bu yerda uchta masala va to‘rt soat beriladi — qisman ball tizimini sinash uchun qulay.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

O’zingizning uch soatlik rejangizni yozing va uni devorga yopishtiring. Keyingi mashq musobaqasidan keyin unga qaytib, nimasi ishlamaganini yozib qo’ying.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

CSES dan beshta masala tanlab, 90 daqiqalik musobaqa o’tkazing. Har masalaga qancha vaqt sarflaganingizni yozib boring. Vaqt tugagach to’xtang — hatto «yana ozgina» qolgan bo’lsa ham.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Sinfda uch kishilik jamoa musobaqasi tashkil qiling: bitta kompyuter, uch soat, beshta masala. Kim qachon kompyuterda o’tiradi? Bu qarorni oldindan kelishib olish kerak — va aynan shu ko’nikma ICPC turidagi musobaqalarda hal qiluvchi.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim