Шопинг#

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

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

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

int main()
{
    int n, d = 0;
    vector<int> prices;

    cin >> n >> d;
    
    for (int i=0; i<n; i++)
    {
        int price;
        cin >> price;
        prices.push_back(price);
    }
    
    sort(prices.begin(), prices.end());
    reverse(prices.begin(), prices.end());
    
    double total_price = 0.0;
    int cheaper_items = prices.size() / 3;
    
    for (int i=0; i<n; i++)
    {
        if (i < cheaper_items)
           total_price += prices[i] - prices[i] * (d/100.0);
        else
            total_price += prices[i]; //normal price
    }
       
    cout << fixed << setprecision(2);
    cout << total_price << endl;
    return 0; //exit code 0
}

Решението дадено погоре има сложеност O(nlogn), која што следи од комплексноста на алгоритамот за сортирање. Повеќе информации околу алгоритмите за сортирање можете да најдете тука и тука.

Магацин#

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

Она што требаше да се забележи од текстот на задачата е дека бројот на кутии е многу мал (максимум 8), така што можеме во многу кратко време да ги креираме сите можни редоследи на кутиите (вкупно 8!=40320 редоследи). Потоа, за секој добиен редослед, го пресметуваме напорот потребен за негово креирање и, доколку е минимален досега, го паметиме редоследот во некоја низа.

За креирање на можните редоследи (пермутации) можеме да ја користиме готовата функција next_permutation() - за оние кои што користат C++, а можеме и да ги креираме сите можни редоследи со помош на рекурзија. Тука ќе го претставиме изворниот код на функцијата која служи за креирање на редоследите (ова е многу важен алгоритам кој секој сериозен натпреварувач треба да научи да го имплементира):

void recursion(vector<int> order, int position)
{
     if (position >= n)
     {
          check_solution(order);          
     } else
     {
           int used[10];
           fill(used, used+10, 0);
           for (int i=0; i<order.size(); i++)
               used[order[i]] = 1;
           
           for (int i=1; i<=n; i++)
               if (used[i] == 0)
               {
                      order.push_back(i);
                      recursion(order, position+1);
                      order.pop_back();
               }
     }        
}

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

void check_solution(vector<int> order)
{
     int price = 0;
     int inserted[10];
     fill(inserted, inserted+10, 0);
     
     for (int i=0; i<order.size(); i++)
     {
         int box = order[i];
         inserted[box] = 1;
         price += weight[box-1] * i;
         
         vector<int> above = must_lie_above[box];
         
         for (int j=0; j<above.size(); j++)
             if (inserted[above[j]] == 0)
                return ; //not a valid solution                                  
     }
     
     if (price < best)
     {
               best = price;
               result = order;
     }
}

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

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

int n, best = 2100000000;
vector<int> must_lie_above[10];
vector<int> weight;
vector<int> result;

int main()
{    
    cin >> n;
    
    for (int i=0; i<n; i++)
    {
        int w;
        cin >> w;
        weight.push_back(w);
    }
    
    int limits;
    cin >> limits;
    
    for (int i=0; i<limits; i++)
    {
        int ai, bi;
        cin >> ai >> bi;
        
        must_lie_above[ai].push_back(bi);
    }
    
    recursion(vector<int>(), 0);
    
    for (int i=0; i<result.size(); i++)
        if (i == 0)
           cout << result[i];
        else
           cout << " " << result[i];
           
    cout << endl;
    return 0;
}

Ова решение има сложеност О(n! * n2). Решението може да се унапреди доколку користиме динамичко програмирање (мемоизација).

Тест случаи#