!!Шопинг

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

%%prettify 
{{{
#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), која што следи од комплексноста на алгоритамот за сортирање. Повеќе информации околу алгоритмите за сортирање можете да најдете [тука|Материјали За Подготовка] и [тука|ПИН 2009].


!!Магацин

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

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

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

%%prettify 
{{{
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();
               }
     }        
}
}}}
/%

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

%%prettify 
{{{
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;
     }
}
}}}
/%

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

%%prettify 
{{{
#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! * n%%sup 2/%). Решението може да се унапреди доколку користиме динамичко програмирање (мемоизација).


!!Тест случаи
Тест случаите можете да ги симнете како .zip архива [тука|Втор електронски натпревар/testovi_vtor_elektronski_2010.zip]. \\
Текстот и решенијата дадени погоре можете слободно да ги коментирате на форумот.