MendoWiki: Четврти електронски натпревар 2011

More...

Календар#

Како решение на оваа задача се бараше програма која од стандарден влез (тастатура) ќе прочита два цели броеви M и G, кои означуваат одреден месец и година - соодветно, и на стандарден излез (екран) ќе отпечати колку денови имал/има/ќе има месецот M во годината G.

Решението се сведува на чување на бројот на денови кои ги има секој месец и пресметување дали една година е престапна или не (со if наредба). Следи изворниот код на официјалното решение:

C++#

#include <iostream>
using namespace std;

int main()
{    
    int days[] = {31,28,31,30,31,30,31,31,30,31,30,31};
 
    int m, y;
    cin >> m >> y;
    
    int answer = days[m-1];
    
    if (m==2) //february
       if ((y%400==0) || ((y%4==0)&&(y%100!=0)))
          answer++;
          
    cout << answer << endl;
    return 0;
}

Паскал#

program kalendar;        (** Марио Величковски **)
var m,g,d:integer;
begin
     readln(m,g);
     case m of
     1:d:=31; //januari
     2:if (g mod 400=0) or ((g mod 4=0) and (g mod 100<>0)) then d:=29 else d:=28;  //fevruari
     3:d:=31; //mart
     4:d:=30; //april
     5:d:=31; //maj
     6:d:=30; //juni
     7:d:=31; //juli
     8:d:=31; //avgust
     9:d:=30; //septemvri
     10:d:=31; //oktomvri
     11:d:=30; //noemvri
     12:d:=31; //dekemvri
     end;
     writeln(d);
     readln;
end.

Решението дадено погоре има константна сложеност O(1).

Шах#

Во оваа задача се бараше да напишеме програма која за дадена позиција на еден коњ, и позициите на N противнички фигури, ќе пресмета и отпечати колку од N-те противнички фигури се нападнати од коњот.

Задачата се решава така што, откога ќе ја прочитаме позицијата на која се наоѓа коњот, за секоја од N-те противнички фигури проверуваме, посебно, дали е таа на позиција на која што може да дојде коњот. Проверката можеме да ја направиме на повеќе начини: чувајќи ги можните потези на коњот во низа (види решение), проверка дали важи условот (abs(r1-r2)=1 AND abs(c1-c2)=2) OR (abs(r1-r2)=2 AND abs(c1-c2)=1), или па дали важи (r1-r2)2+(c1-c2)2=5. Следи изворниот код на официјалното решение:

C++#

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int row, col;
    string scol;
    
    cin >> scol >> row;
    col = scol[0] - 'a' + 1;
    
    int n;
    cin >> n;
    
    int answer = 0;
    
    int mx[] = {-2,-1,1,2, 2, 1,-1,-2};
    int my[] = {1 ,2, 2,1,-1,-2,-2,-1};
    
    for (int i=0; i<n; i++)
    {
        int cr, cc;
        string scc;
        
        cin >> scc >> cr;
        cc = scc[0] - 'a' + 1;
                        
        for (int j=0; j<8; j++)
            if (row+my[j] == cr)
               if (col+mx[j] == cc)
                  answer++;
    }
    
    cout << answer << endl;
    return 0;
}

Ова решение има линеарна сложеност O(N).