O‘quv – uslubiy majmua

Yuqori qiyinlik darajasidagi masalalar va ularni yechish usullari

Informatikadan olimpiadaning respublika bosqichida asosan qiyinlik darajasi yuqori bo‘lgam masalalar taqdim etiladi. Quyida shunday masalalardan namunalar keltiramiz:
1. N ta kulrang va M ta oq sichqon aylana bo‘ylab o‘tirishibdi. Mushuk aylana bo‘ylab soat mili yo‘nalishida yurib, har S-sichqonni yeydi. Hisob kulrang sichqondan boshlanadi. Ma’lum vaqtdan so‘ng K ta kulrang va L ta oq sichqon qolgan bo‘lsa, boshida sichqonlar qanday tartibda o‘tirganini aniqlovchi dastur tuzing. Yechish:
Bu masalani yechishning juda ko‘p usuli bo‘lib, ulardan birini keltiramiz.
1-qadam. Sichqonlarning I-siga rangidan qat’iy nazar SON(I) massiv elementini mos qo‘yamiz. Agar SON(I)=1 bo‘lsa I-sichqon tirik, SON(I)=0 bo‘lsa I-sichqon yeyilgan. Masalani shartiga ko‘ra boshlang‘ich vaqtda barcha sichqonlar uchun SON(I)=1.
2-qadam. Har T-sichqon yeyilsa, ya’ni SON(I)=0 bo‘lsa, ma’lum vaqtdan (ya’ni qadamdan) keyin yeyilgan sichqonlar soni N+M-K-Lga teng bo‘lishi kerak, chunki masala shartiga ko‘ra sichqonlarning umumiy soni N+Mta; tirik qolishi kerak bo‘lgan kulrang sichqonlar soni Kta, oq sichqonlar soni Lta.
3-qadam. Masala shartiga ko‘ra hisob kulrang sichqondan boshlanadi. Shuning uchun natijani chop etishda hisobni (I=1dan boshlab) kulrang sichqonlardan boshlaymiz. H1 tirik (SON(I)=1), H2 (SON(I)=0) yeyilgan kulrang sichqonlar soni bo‘lsa, ularning soni mos ravishda (H1 va H2 noldan boshlangani uchun) K-1 va N-K-1dan oshmaydi. Qolgan sichqonlarni oq sichqon deb qaraymiz.
Program Mushuk_Sichqon;
Uses Crt;
Const nm1=100;
var n,m,s,k,l:Integer; nm,qadam:Integer; son:Array[1..nm1] of Integer;
del,_del:Integer;{Yeyilgan sichqonlar soni} i,h1,h2:Integer;
Begin
TextColor(14); TextBackground(1); ClrScr;
Write('Nechta kulrang sichqon: '); ReadLn(n);
Write('Nechta oq sichqon: '); ReadLn(m);
Write('Nechta kulrang sichqon tirik qolsin: '); ReadLn(k);
Write('Nechta oq sichqon tirik qolsin: '); ReadLn(l); Write('Nechta qadam sakrasin: '); ReadLn(s);
nm:=n+m; _del:=nm-k-l; For i:=1 To nm Do son[i]:=1; del:=0; qadam:=0; i:=0;
Repeat
Inc(i); If i>nm Then i:=i-nm;
If son[i]=1 Then Inc(qadam);
If qadam=s Then Begin qadam:=0; son[i]:=0; Inc(del) end;
Until del=_del; h1:=0; h2:=0; For i:=1 To nm Do
Begin
Case son[i] Of 1: Begin
TextColor(15);
If h1Then Begin Inc(h1); Write(i,'-k, '); end
Else Write(i,'-oq, '); end;
0: Begin
TextColor(7);
If h2Then Begin Inc(h2); Write(i,'-k, '); end
Else Write(i,'-oq, '); end; end; end;
ReadLn;
End.
2. Kenguru uzunligi N ta katak bo‘lgan maydonda faqat oldinga sakrashi mumkin. Kenguruninig sakrash imkoniyati ko‘pi bilan K ta katak bo‘lsin. Kenguruning maydonning boshidan oxirigacha necha xil usul bilan yetib borishi mumkinligini aniqlovchi dastur tuzing. Masalan, N=3, K=2 bo‘lsa, usullari:

1. 
   1, 1, 1
   
2. 
   1, 2
   
3. 
   2, 1 Javob 3.