Фудбал#

Во оваа задача се бараше да напишеме програма која од стандарден влез ќе прочита информации за резултатите на N фудбалски екипи, и на стандарден излез ќе го отпечати максималниот број на поени кои ги освоила една од N-те екипи... Решението е доста едноставно: во циклус ги изминуваме сите екипи, пресметуваме колку поени освоила секоја од нив (притоа, во секој чекор од for-циклусот го паметиме резултатот на екипата која освоила најмногу поени). Решението има линеарна сложеност, која следува од тоа што мораме да ги изминеме сите екипи пред да можеме да бидеме сигурно дека сме ја пронашле екипата со најмногу поени. Следи изворниот код на официјалното решение:

#include <iostream>
using namespace std;

int main()
{
    int best = 0, n;
    cin >> n;
    
    for (int i=0; i<n; i++)
    {
        int wi, di, li;
        cin >> wi >> di >> li;
        
        int points = 3*wi + di;
        
        if (points > best)
           best = points;
    }
    
    cout << best << endl;
    return 0;        
}

Паскал#

program fudbal;                           (* Марио Величковски *)
var n,wi,di,li,b,max,p:longint;
begin
     readln(n);
     readln(wi,di,li);
     p:=wi*3+di*1;
     max:=p;
     for b:=2 to n do
     begin
     readln(wi,di,li);
     p:=wi*3+di*1;
     if p>max then max:=p;
     end;
     writeln(max);
     readln;
end.

Како што напоменавме и погоре, ова решение има линеарна сложеност O(n).

Факторизација#

Она што всушност се бараше како решение на оваа задача е да се напише програма која ќе прочита еден цел број од стандарден влез, и на излез ќе ја отпечати факторизација на тој број (ќе го претстави бројот како производ од прости фактори). Решението на задачата се состои во следното: додека бројот е поголем од 1 (сеуште има фактори кои не сме ги пронашле), ги проверуваме сите можни основи и за нив го пресметуваме степенот на факторот (почнувајќи од најмалата основа - 2, бидејќи во текстот на задачата се бара од нас да ги печатиме факторите подредени од оној со најмала кон оној со најголема основа). Вториот проблем во задачата е печатењето на резултатите (особено поставеноста на знакот за множење), но решението и на овој проблем е доста едноставно (воведуваме само уште една променлива која ќе памети дали го печатиме првиот фактор или не). Следи изворниот код на програмата:

#include <iostream>
using namespace std;

int main()
{
    int n, base=2, deg, first=1;
    cin >> n; //read n from console
    
    while (n >= 2)
    {
          deg = 0;
          
          while (n%base == 0)
          {
                n /= base;
                deg = deg+1;
          }
                
          if (deg > 0)
          {
                  if (first == 1)
                  {
                     cout << "(" << base << "^" << deg << ")";
                     first = 0; //printed the first factor
                  } else
                  {
                     cout << "*" << "(" << base << "^" << deg << ")";
                  }                  
          }
          
          base = base + 1;                     
    }
    
    cout << endl;
    return 0;
}

Иако на прв поглед, решението има два вгнездени while циклуси, сепак комплексноста не е квадратна, туку ова решение има линеарна сложеност О(n). Во пракса, решението работи многу побрзо и од тоа.

Тест случаи#