MendoWiki: Трет електронски натпревар 2011

More...

Игра#

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

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

C++#

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

int main()
{
    int n, e;
    cin >> n;
    
    int result = 0;
    int current = 0;
    
    vector<int> v;
    
    for (int i=0; i<n; i++)
    {
        cin >> e;
        v.push_back(e);
        
        if (e == 1)
           current++;
        else
            current = 0;
            
        result = max(result, current);
    }
    
    cout << result << endl;
    return 0;    
}

Решението дадено погоре има линеарна сложеност O(N).

Анкета#

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

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

C++#

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

int main()
{
    int m = 0;
    vector<string> v;    
        
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++)
    {
            string str;
            cin >> str;
            
            v.push_back(str);
    }
    
    for (int i=0; i<n; i++)
    {
        int current = 0;
        
        for (int j=0; j<n; j++)
            if (v[i] == v[j])
               current++;
               
        m = max(m, current);
    }
    
    for (int i=0; i<n; i++)
    {
        int current = 0;
        
        for (int j=0; j<n; j++)
            if (v[i] == v[j])
               current++;
               
        if (current == m) //found max value
        {
                    cout << v[i] << endl;
                    break;
        }                    
    }
    
    return 0;
}

Ова решение има квадратна сложеност O(N2). Постојат решениja и со помала сложеност (на пример, може да ги подредиме имињата, или да користиме некоја сложена структура).