Pirmojo etapo uždavinių sąlygos

30. LOGINIS REIŠKINYS. Loginis reiškinys, turintis tris kintamuosius, vaizduojamas šitokia teisingumo lentele:
 

a	b	c
0	0	0	x
0	0	1	x
0	1	0	x
0	1	1	x
1	0	0	x
1	0	1	x
1	1	0	x
1	1	1	x

Čia loginė reikšmė false žymima 0, o true – 1. Reiškinio reikšmės, pažymėtos x, apibrėžia konkretų reiškinį ir yra pradiniai duomenys. Reiškinio reikšmė gali ir nepriklausyti nuo kai kurių (ar net visų) kintamųjų, įrašytų į lentelę, reikšmių.

Parašykite algoritmą, kuris rastų, nuo kelių kintamųjų iš tikrųjų priklauso duoto loginio reiškinio reikšmė.

31. OPERACIJŲ ŽENKLAI. Aritmetiniame reiškinyje
a ? b ? c ? d ? e = r
operacijų ženklai uždengti.

Parašykite algoritmą operacijų ženklams nustatyti. Jeigu galimi keli variantai – pakanka rasti vieną.

32. DVEJETAINIS KODAS. Skaičiaus a dvejetainis kodas perduodamas lygiagrečiai – kiekviena skiltis atskiru laidu. Pirmuoju laidu perduodama žemiausia (dešiniausia) skaičiaus skiltis, antruoju – antroji skiltis iš dešinės ir t. t. Iš priimto kodo gaunamas skaičius b. Jei perdavimo linija veikia gerai, tai a = b. Jei a <> b, tai įtariama, kad nutrūkęs vienas laidas: tuomet laido gale visada gaunamas dvejetainis nulis.

Parašykite algoritmą šiai hipotezei patikrinti. Jeigu ji teisinga, reikia nustatyti nutrūkusio laido eilės numerį.

a) praleistas skaitmuo, pavyzdžiui, vietoj 2537 surinkta 237;
b) netyčia paspaustas klavišas ir į skaičių įterptas nereikalingas skaitmuo („šiukšlė“, pavyzdžiui vietoj 1992 surinkta 19092);
c) paspaudus ne tą klavišą surinktas kitas skaitmuo, pavyzdžiui, vietoj 1993 surinkta 1923.

a) trečiasis skaičius turi būti lygus pirmųjų dviejų skaičių sumai;
b) renkant skaičius galėjo būti padaryta viena iš minėtųjų klaidų, bet tik viename skaičiuje.

35. SKAITMENŲ SUMA IR SANDAUGA. Parašykite algoritmą mažiausiam natūraliajam skaičiui rasti, kai duota to skaičiaus skaitmenų suma ir sandauga.

Parašykite algoritmą šiam uždaviniui spręsti.

37.  BŪDVARDŽIO LINKSNIUOTĖ. Duotas būdvardžio vienaskaitos ir daugiskaitos vardininkas. Parašykite algoritmą jo linksniuotei nustatyti .

1) vaikai gautų po lygiai riestainių;
2) kiekvienas riestainis būtų pjaustomas tik į lygias dalis;
3) pjaustymų skaičius būtų mažiausias.

RIESTAINIŲ       Į KIEK DALIŲ       KIEK DALIŲ DUOTI
KIEKIS               PJAUSTYTI           KIEKVIENAM VAIKUI
     3                              2                             1
     2                              3                             1
 

39. PERPIEŠTAS ORNAMENTAS. Į 50x50 langelių dydžio popieriaus lapą iš knygos perpiešiamas ornamentas, rašto langeliai nuspalvinami juodai. Knygoje ornamentas simetriškas horizontaliosios ir vertikaliosios ašių, einančių langelių kraštinėmis, atžvilgiu. Tačiau perpiešiant gali būti padaryta klaida: trūkti vieno juodo langelio arba būti vienu juodu langeliu perdaug.

Parašykite programą, kuri nustatytų, ar teisingai perpieštas ornamentas, o jeigu ne – rastų neteisingo langelio koordinates.

a) PERPIEŠTA TEISINGAI;
b) REIKIA PAPILDYTI LANGELIU (X, Y);
c) REIKIA PAŠALINTI LANGELĮ (X, Y);
d) YRA DAUGIAU KAIP VIENA KLAIDA.

Kompiuteris šiuo atveju turi spausdinti:

REIKIA PAPILDYTI LANGELIU (9,11)

Sudužus laivui, į salą patenka 5 žmonės ir 1 beždžionė. Pirmą dieną visi renka kokoso riešutus. Naktį vienas iš žmonių nutaria pasiimti savo dalį riešutų. Jis padalija riešutus į 5 krūveles, likusį vieną riešutą atiduoda beždžionei ir, paslėpęs savąją krūvelę, vėl atsigula.

Netrukus pabunda kitas keleivis ir padaro tą patį: padalija riešutus į 5 krūveles, likusį vieną riešutą atiduoda beždžionei, savąją krūvelę paslepia ir atsigula miegoti.

Toliau paeiliui pabunda trečiasis, ketvirtasis ir penktasis bendrakeleiviai ir padaro tą patį, ką ir pirmieji du. Ryte visi pasidalija likusius riešutus, šį kartą riešuto beždžionei nelieka. Kiek riešutų buvo surinkta?

Parašykite algoritmą bendresniam uždaviniui: kai yra n žmonių ir viena beždžionė. Pradinis duomuo (žmonių skaičius n) ir rezultatas rašomi displėjaus ekrane.

41. VALIUTOS KEITIMAS. N valstybių turi skirtingas valiutas. Kiekvienos valstybės bankas perka kitų valstybių valiutą ir moka už ją sava valiuta. Valiutų supirkimo kainos pateiktos N x N dydžio lentelėje: i eilutės j stulpelyje nurodoma i valstybės valiutos vieneto kaina j valstybės valiuta. Nulis rodo, kad j valstybė i valstybės valiutos neperka.

Turėdami tam tikrą pradinės valstybės valiutos kiekį ir aplankę kelias valstybes, kiekvienoje jų keisdami valiutą, vėl grįžtame į pradinę valstybę. Jei grįžę turėsime daugiau valiutos, negu jos buvome pasiėmę iš pradžių, tai reikš, kad maršrutas pelningas. (Kelionės išlaidos neskaičiuojamos.)

Reikia nustatyti, ar yra bent vienas pelningas valiutų keitimo maršrutas.

1) iš tekstinės bylos perskaitytų valiutų supirkimo kainų lentelę;
2) rastų bent vieną pelningą maršrutą; jei tokio maršruto nėra, išvestų pranešimą: PELNINGO MARŠRUTO NĖRA;
3) jei pelningas maršrutas yra, parodytų ekrane visų aplankytų valstybių numerius ir pelno, kuris gaunamas nukeliavus tuo maršrutu vieną kartą, dydį procentais.

Ekrane galėtų būti pateiktas toks rezultatas:
PELNINGAS MARŠRUTAS: 1 3 2
PELNAS: 71.6%

42. ALGORITMŲ ANALIZĖ. Pateiktos trys programos (4ol_42.zip), sprendžiančios antrojo etapo antrąjį uždavinį (39). Išanalizuokite šias programas, pasirinkite vieną iš jų, kuri, jūsų manymu, tinkamiausia tobulinti, ir patobulinkite taip, kad ji duotų teisingus rezultatus bet kuriems pradiniams duomenims, be to būtų ekonomiška, vaizdi, tenkintų programavimo kultūros reikalavimus.

Pirmoji programa

program ornamentas;

var
  mas : array [1..50,1..50] of boolean;     { Visų langelių masyvas }
  klaidos,x,y,a,b,c : integer;
  kamp : array [1..4] of boolean;      { 4 simetriškų langelių masyvas }
  byla : text;
  ch : char;
  gerai : boolean;
  bx,by,          { Blogo langelio koordinatės   }
  cx,cy,          { Ornamento centro koordinatės }
  w ,h :integer;  { Ornamento plotis ir aukštis  }

begin
  assign(byla,'ORNAM.DAT');
  reset(byla);
  cy:=51; cx:=51;
  h:=0;   w:=0;
  for y:=1 to 50 do begin
    for x:=1 to 50 do begin
      read(byla,ch);
      mas[x,y]:=ch='1';  {  Skaitomi duomenys iš bylos 'DUOMENYS.DAT' ir }
      if mas[x,y] then   {  ieškoma labiausiai nutolusių juodų langelių  }
        begin
          if x<cx then cx:=x;
          if x>w then w:=x;
          if y<cy then cy:=y;
          if y>h then h:=y
        end
    end;
    readln(byla)
  end;

  w:=(w-cx+1)div 2;  h:=(h-cy+1)div 2;  { Skaičiuojamas plotis, aukštis }
  cx:=cx+w;  cy:=cy+h;                  {   ir centro koordinatės      }
  klaidos:=0;     { Pradinis klaidų skaičius }
  for x:=1 to w do
   for y:=1 to h do
     begin
      kamp[1]:=mas[cx-x,cy-y];  { Tikrinami 4 simetriški langeliai }
      kamp[2]:=mas[cx-x,cy+y-1];
      kamp[3]:=mas[cx+x-1,cy+y-1];
      kamp[4]:=mas[cx+x-1,cy-y];
      b:=0;
      for a:=1 to 4 do
       if kamp[a] then b:=b+1;{ Skaičiuojama,kiek simetriškų juodų langelių}
      case b of
        2:klaidos:=klaidos+2;    { Jei tik 2 langeliai vienodi }
        1:begin                  { Jei 1 langelis nereikalingas }
            gerai:=false;
            klaidos:=klaidos+1;
            for a:=1 to 4 do
              if kamp[a] then c:=a
          end;
        3:begin                   {  Jei 1 langelio trūksta }
            gerai:=true;
            klaidos:=klaidos+1;
            for a:=1 to 4 do
              if not kamp[a] then c:=a
          end
      end;
      if (b=1) or (b=3) then   { Randamos blogo langelio koordinatės }
        case c of
          1:begin
              bx:=cx-x;
              by:=cy-y
            end;
          2:begin
              bx:=cx-x;
              by:=cy+y-1
            end;
          3:begin
              bx:=cx+x-1;
              by:=cy+y-1
            end;
          4:begin
              bx:=cx+x-1;
              by:=cy-y
            end
        end
     end;

    { Rezultato spausdinimas }
  if klaidos=0 then writeln('Perpiešta teisingai')
               else
   if klaidos>1
    then writeln('Yra daugiau kaip viena klaida (',
                 klaidos,')')
    else
    if gerai
     then writeln('Reikia papildyti langeliu (',bx,',',by,')')
     else writeln('Reikia pašalinti langelį (',bx,',',by,')');

  writeln;
  writeln(' Paspauskite Enter klavišą...');  { Pauzė }
  readln
end.

Antroji programa

Program Olimpiada2;

uses
  Crt;

const
  Byla = 'ORNAM.DAT';
  MaxX = 50;
  MaxY = 50;

type Masyvas = array[1..MaxY] of String[MaxX];

var Fl    : Text;
    mas   : Masyvas;
    Xrez,Yrez : Byte;  { vietos, kurią reikia pataisyti, koordinatės }

procedure Pakeisk(x,y : Byte);
begin
  if mas[y][x]='1' then mas[y][x]:= '0'
                   else mas[y][x]:= '1';
end;

function Tikrink(galima : Boolean) : Byte;

{ Rekursinė funkcija,kuri tikrina, ar teisingas piešinys.
  Radus klaidą, bandoma ją taisyti (funkcija kreipiasi į save
  su parametru galima=False). Pavykus darbas baigiamas.

  Kai funkcijos parametras
  galima=False, tai jokių pakeitimų masyve daryti negalima;
  galima=True,  tai galime pakeisti vieną elementą. }

var xmin,xmax,ymin,ymax,  { ribinės piešinio koordinatės }
    x,y,
    Ats        : Byte;    { pagalbiniai kintamieji }

begin

  xmin:= MaxX+1;                 { nustatome xmin ir xmax }
  xmax:= 0;
  for y:= 1 to MaxY do
    for x:= 1 to MaxX do
      if mas[y][x]='1' then
         begin
          if x<xmin then xmin:= x;
          if x>xmax then xmax:= x
         end;

  ymin:= MaxY+1;                 { nustatome ymin ir ymax }
  ymax:= 0;
  for y:= 1 to MaxY do
    if Pos('1',mas[y])>0 then
       begin
         if y<ymin then ymin:= y;
         if y>ymax then ymax:= y
       end;

  if (xmax=0) and (ymax=0) then Tikrink:= 1  { jei tuščias laukas,tai
                                       &n bsp;                                         &nbs p;          perpiešta teisingai }
  else begin
    Ats:= 1;
    y:= ymin;
    repeat
      x:= xmin;
      repeat
        if (mas[y][x]<>mas[y][xmax+xmin-x]) or
           (mas[y][x]<>mas[ymax+ymin-y][x]) then
           if galima then
              begin
                Pakeisk(x,y);        { pataisome piešinį }

                if Tikrink(False)=1  { tikriname, ar pataisytas piešinys
                                       teisingas }
                   then begin
                          Xrez:= x;
                          Yrez:= y;
                          if mas[y][x]='0' then Ats:= 3
                                                 { reikėjo pašalinti }
                                            else Ats:= 2
                                                 { reikėjo papildyti }
                        end
                   else Ats:= 4;

                Pakeisk(x,y)         { atstatome piešinį }
              end
           else Ats:= 4;
        Inc(x)
      until (Ats=4) and not galima or  { pataisytas piešinys neteisingas }
            (Ats in [2,3]) or           { pavyko pataisyti }
            (x>xmax);                   { baigėsi tikrinama eilutė }
      Inc(y)
    until (Ats=4) and not galima or
          (Ats in [2,3]) or
          (y>ymax);                     { peržiūrėtas visas piešinys }

    Tikrink:= Ats
  end
end;

Begin { Olimpiada2 }

  ClrScr;
  Assign(Fl, Byla);
  Reset (Fl);

  for Yrez:= 1 to MaxY do
    ReadLn(Fl,mas[Yrez]);

  Close (Fl);

  Xrez:= 0; Yrez:=0;

  case Tikrink(True) of
   1: WriteLn('Perpiešta teisingai.');
   2: WriteLn('Reikia papildyti langeliu (',Xrez,',',Yrez,').');
   3: WriteLn('Reikia pašalinti langelį (',Xrez,',',Yrez,').');
   4: WriteLn('Yra daugiau kaip viena klaida.')
  end;

  WriteLn;
  WriteLn('Paspauskite Enter klavišą ...');
  ReadLn

End. { Olimpiada2 }
 

Trečioji programa

program ornamentas;
  type lapas = 1..50;
       ornam = array [ lapas,lapas ] of '0'..'1';
  var orn : ornam;
      ss  : text;
      x,y : lapas;
  procedure centras ( var x,y :lapas );
  { Randa ornamento centrą }
    var prx,pry,glx,gly, { Pirmų ir paskutinių juodų langelių koordinatės }
        k,l : 0..50;
  begin
    prx := 0 ; pry := 0 ;
    glx := 0 ; gly := 0 ;
    for k := 1 to 50 do
      for l := 1 to 50 do
        if orn [ l,k ] = '1'
           then begin
                  if prx = 0 then prx := k;
                  if glx < l then glx:= k;
                  if pry = 0 then pry := l ;
                  if gly < l then gly:= l
                end;
    x := ( prx + glx ) div 2 ;  { Centro           }
    y := ( pry + gly ) div 2    { koordinatės      }
  end;
  procedure tikrinti ;
  { Tikrina,ar nėra klaidų, ir ,jei jų yra, parodo pranešimą }
    var i,j,a,b,a1,b1 : 0..50 ; { Įvairios koordinatės       }
        r : string[4];
        daug,           { Parodo , ar ne per daug klaidų }
        p : boolean ;   { Parodo , ar reikia pašalinti ar pridėti langelį }
        m,n : integer ;
  begin
    daug := false ;
    p:=false ;
    i := 0; j := 0;
    for b := 1 to y do
       for a := 1 to x do
         if not daug
            then begin
                   b1 := y*2+1-b ;   { Tolimiausio taško   }
                   a1 := x*2+1-a ;   { koordinatės (a1;b1) }
                   r := orn [a,b] + orn [a1,b] + orn [a,b1] +
                        orn [a1,b1];{ Langeliai,simetriški langeliui (a;b) }
                   val (r,m,n);
                   case m of
                    1110: if i = 0
                          then begin p := true ; i := a1 ;
                                     j := b1
                               end
                          else daug := true;
                    1101: if i = 0
                          then begin p := true ; i := a ;
                                     j := b1
                               end
                          else daug := true;
                    1011: if i = 0
                          then begin p := true ; i := a1 ;
                                     j := b
                               end
                          else daug := true;
                    0111: if i = 0
                          then begin p := true ; i := a ;
                                     j := b
                               end
                          else daug := true;
                    0001: if i = 0
                          then begin p := false ; i := a1 ;
                                     j := b1
                               end
                          else daug := true;
                    0010: if i = 0
                          then begin p := false ; i := a ;
                                 j := b1
                               end
                           else daug := true;
                    0100: if i = 0
                           then begin p := false ; i := a1 ;
                                  j := b
                                end
                           else daug := true;
                    1000: if i = 0
                          then begin p := false ; i := a ;
                                     j := b
                               end
                          else daug := true;
                    1111,
                    0000: ; { Tvarka ! }
                    else daug := true
                   end
                 end;
   if (i=0) and not daug
   then writeln ('Perpiešta teisingai')
   else if daug
        then writeln ('Yra daugiau kaip viena klaida')
        else if p then writeln ('Reikia papildyti langeliu (', i,',',j,')')
                  else writeln ('Reikia pašalinti langelį (',i,',',j,')')
  end;
begin
  assign ( ss,'ORNAM.dat' );
  reset ( ss );
  for y := 1 to 50 do
    begin
      for x := 1 to 50 do
        read ( ss,orn[x,y] );
      readln ( ss )
    end;
  close ( ss );
  centras ( x,y );
  tikrinti
end.

43. INVESTICINIŲ ČEKIŲ AUKCIONAS. Investiciniais čekiais prekiaujama aukcione. Kiekvienas aukciono dalyvis pateikia jo organizatoriams užklijuotą voką su prašymu. Asmuo, norintis pirkti čekius, prašyme nurodo, kiek čekių jis pirktų ir kokią didžiausią kainą mokėtų už vieną čekį. Asmuo, norintis parduoti, nurodo kiek čekių parduotų ir už kokią žemiausią kainą. Čekio kaina neturi viršyti 5 litų ir išreiškiama šimtųjų lito dalių tikslumu.

Aukciono pradžioje visi vokai atplėšiami, išanalizuojama čekių pasiūla bei paklausa ir nustatoma visiems aukciono dalyviams vienoda čekių kaina. Kaina nustatoma tokia, kad būtų parduota kuo daugiau čekių.

1) perskaitytų pradinius duomenis ir ekrane grafiškai pavaizduotų parduodamų ir perkamų čekių skaičiaus pasiskirstymą pagal kainas. Galima vartoti tik kompiuterio abėcėlės simbolius (tarp jų – ir pseudografikos). Vaizdavimo pavidalą parinkite patys. Jis turi būti informatyvus, lengvai suvokiamas ir meniškas;
2) apskaičiuotų investicinio čekio kainą. Jeigu galima parinkti daugiau negu vieną kainą, kuriai esant būtų parduotas didžiausias čekių kiekis, tai iš jų reikia parinkti didžiausią kainą;
3) apskaičiuotų, kiek čekių parduota aukcione.

44. PASLAPTINGI ŽEMYNAI. Žemėlapis – tai stačiakampis, sudarytas iš 48 x 16 langelių. Du langeliai vadinami kaimyniniais, jeigu jie turi vieną bendrą kraštinę.

Sausumos tipai (ST) yra keturi: S (SAUSUMA), K (KALNAS), P (PUSIASALIS) ir R (PAKRANTĖ). Vandenų tipai (VT) yra taip pat keturi: V (VANDUO), O (OKEANAS), J (JŪRA) ir E (EŽERAS). Laikoma, kad žemėlapio išorėje yra OKEANAS (O). Iš pradžių žinoma tik tai, kad kiekvienas žemėlapio langelis yra arba VANDUO (V), arba SAUSUMA (S).

Yra apibrėžtos tam tikros geografinės taisyklės langelių tipui pakeisti. Langelis gali tapti:

• KALNU (K), jei jis yra ST langelis ir yra kaimyninis keturiems kitiems ST langeliams;
• PUSIASALIU (P), jei jis yra ST langelis ir yra kaimyninis arba trims VT langeliams, arba dviems VT langeliams ir bent vienam P langeliui, arba vienam VT langeliui ir bent dviems P langeliams;
• PAKRANTE ( R ), jei  jis yra ST langelis ir nėra nei K, nei P;
• OKEANU (O), jei jis yra V langelis ir yra kaimyninis bent vienam O langeliui;
• JŪRA (J), jei jis yra O langelis ir yra kaimyninis arba bent dviems J langeliams ir daugiausiai vienam O langeliui, arba vienam J langeliui ir bent dviems ST langeliams, arba bent dviems ST langeliams ir bent vienam O langeliui;
• EŽERU (E), jei jis yra V langelis ir lieka nepakitęs net ir tada, kai daugiau jokių pakeitimų žemėlapyje atlikti neįmanoma.

Žemėlapis laikomas ištirtu, kai neįmanoma pakeisti daugiau nė vieno jo langelio.

1) iš tekstinės bylos perskaitytų žemėlapį, kuriame pavaizduotas nežinomas žemynas, displėjaus ekrane pateiktų šį žemėlapį kartu su statistine informacija, kiek kokio tipo langelių perskaitytame žemėlapyje;
2) ištirtų duotąjį žemėlapį ir pakeistų jo S ir V langelius į K, P, R, O, J ir E tipo langelius pagal nurodytas geografines taisykles;
3) pateiktų displėjaus ekrane pakeistąjį (ištirtąjį) žemėlapį kartu su galutine statistine informacija, kiek kokio tipo langelių yra šiame žemėlapyje;
4) įrašytų ištirtąjį žemėlapį kartu su galutine statistine informacija į tekstinę bylą. Jos vardas turi sutapti su bylos, kurioje įrašyta jūsų sudaryta programa, vardu, o vardo plėtinys turi būti .OUT.

Rezultatai:
Displėjaus ekrane turėtų būti pateiktas žemėlapis (jo neperspausdiname) bei statistinė informacija:
NEŽINOMA: S=61 V=707 IŠ VISO: 768

Displėjaus ekrane ištirtas žemėlapis kartu su galutine statistine informacija turėtų atrodyti taip:
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOORRRRRROOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOORREERROOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOORKPERROOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOORREERRJJJRRRJPOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOJRRRRRRRRKRRRRJOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOJRKRJJJRROOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOORKRJOORROOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOORKKPOORROOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOJRRJOORROOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOJPJOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOJPJOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOPPPOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
IŠTIRTA: P=8 R=47 K=6 O=685 J=17 E=5 IŠ VISO: 768