Фибоначи#

Во оваа задача се бараше да напишеме програма која ќе пресмета колку фибоначиеви броеви се наоѓаат во даден опсег (краевите на опсегот се читаат од стандарден влез). Бидејќи границите на опсегот беа мали (најмногу 20000), задачата може да се реши на тој начин што ќе ги креираме сите фибоначиеви броеви до горната граница на опсегот, и притоа ќе ги броиме само оние кои што се наоѓаат во границите на опсегот.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int countFibs(int a, int b)
{
    int counter = 0;
    vector<int> numbers;
        
    int f=0, f1=1, f2=1;
    numbers.push_back(f1);
    numbers.push_back(f2);
        
    while (f < 25000)
    {
          f = f1+f2;
          f2 = f1;
          f1 = f;
          
          numbers.push_back(f);
    }
        
    for (int i=0; i<numbers.size(); i++)
        if (numbers[i] >= a && numbers[i] <= b)
           counter++;        
               
    return counter;
}

int main()
{
    int start, end;
    cin >> start >> end;
    
    cout << countFibs(start, end) << endl;
    
    return 0;
}

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

Сортирање#

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

Јасно е дека треба да искористиме некој алгоритам за сортирање (во решението дадено подолу се користи алгоритамот Bubble Sort). Она што беше важно во задачата е и да приметиме дека е можно да има повеќе имиња со иста вредност, и дека доколку има такви нивниот редослед треба да остане непроменет (како што е даден во влезот). Алгоритмите за сортирање кои не ги изместуваат елементите со иста вредност се викаат стабилни алгоритми за сортирање. Доколку користиме C++ можеме да ја користите и функцијата stable_sort. Следи изворниот кодот на официјалното решение:

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
using namespace std;

vector<string> sortNames(vector<string> names)
{                     
   for (int i=0; i<names.size()-1; i++)
       for (int j=i+1; j>0; j--)
       {
           int sumi = 0, counti = names[j-1].size();
           for (int p=0; p<names[j-1].size(); p++)
               sumi += names[j-1][p] - 'A' + 1;
           
          int sumj = 0, countj = names[j].size();
          for (int p=0; p<names[j].size(); p++)
               sumj += names[j][p] - 'A' + 1;
           
          if (sumi*countj > sumj*counti)
          {
                string temp = names[j];
                names[j] = names[j-1];
                names[j-1] = temp;                  
          }                 
       }
       
   return names;                               
}    

int main()
{
    int n;
    cin >> n;
    
    string name;
    vector<string> names;
    
    for (int i=0; i<n; i++)
    {
        cin >> name;
        names.push_back(name);
    }
    
    names = sortNames(names);
    
    for (int i=0; i<names.size(); i++)
        cout << names[i] << endl;
    
    return 0;
}

Ова решение има сложеност О(N2), каде N е бројот на имиња. Забележете дека во изворниот код даден погоре никаде не работиме со реални броеви (наместо делење за пронаоѓање на просечната позиција, тоа е заменето преку едноставни математички операции со множење).

Тест случаи#