!!Кутии

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

%%prettify 
{{{
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;


int main()
{
    vector<int> partSizes, boxSizes;

    int nparts, nboxes;    
    cin >> nparts >> nboxes;
    
    for (int i=0; i<nparts; i++)
    {
        int partSize;
        cin >> partSize;
        partSizes.push_back(partSize);
    }
    
    for (int i=0; i<nboxes; i++)
    {
        int boxSize;
        cin >> boxSize;
        boxSizes.push_back(boxSize);
    }    
        
    int used[100];  int usedboxes = 0;
    memset(used, 0, sizeof(used));
    
    for (int i=0; i<partSizes.size(); i++)
    {
        int partSize = partSizes[i];
        int boxIndex = -1;                      
        
        for (int j=0; j<boxSizes.size(); j++)
            if (used[j] == 0 && boxSizes[j] >= partSize)
            {
                boxIndex = j;
                break; //exit loop
            }
        
        if (boxIndex == -1) break; //no box found                      
        
        /* else */
        usedboxes++;
        used[boxIndex] = 1;
    }
    
    
    cout << usedboxes << endl; //usedboxes = packed parts                  
    return 0; //exit code zero
}

}}}
/%

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


!!Избори

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

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

%%prettify 
{{{
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> votes;
    
    int ncandidates;
    cin >> ncandidates;
    
    for (int i=0; i<ncandidates; i++)
    {
        int nvotes;
        cin >> nvotes;
        votes.push_back(nvotes);
    }

    int changedVotes = 0;
    
    while (true)
    {
        int bestIndex = 0;
        int bestVotes = -1;
        
        for (int i=1; i<votes.size(); i++)
            if (votes[i] > bestVotes)
            {
                bestIndex = i;
                bestVotes = votes[i];
            }
        
        if (bestVotes >= votes[0])
        {
            //change vote
            changedVotes++;
            votes[0]++;
            votes[bestIndex]--; 
        } else
        {
            //favorite candidate has most votes
            break; //break while loop
        }
    }
    
    cout << changedVotes << endl;
    return 0; //exit code zero
}

}}}
/%

Ова решение има сложеност О(V*N), каде N е бројот на кандидати, а V е максималниот број на гласови кој би ги добил еден кандидат. Ова време може да се подобри со користење на некои посложени структури како хип или бинарно дрво, но бидејќи границите на N и V се мали, немаше никаква потреба од такви експерименти.

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