Решенија државен 2011

Ајмо ставајте ваши решенија за задачите од државен. Еве ги моите:

Одземање:

#include <iostream>
using namespace std;

void bubblesort(string &a)
{
    char tmp;
    for(int i=0; i<a.length(); i++)
    {
        for(int j=0; j<a.length()-1; j++)
        {
            if(a[j]>a[j+1])
            {
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
        }
    }
}

void bubblesortrev(string &a)
{
    char tmp;
    for(int i=0; i<a.length(); i++)
    {
        for(int j=0; j<a.length()-1; j++)
        {
            if(a[j]<a[j+1])
            {
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
        }
    }
}

int main()
{
    char min='9';
    string broj, minbroj;
    cin>>broj;
    minbroj=broj;
    bubblesort(minbroj);
    bubblesortrev(broj);
    for(int i=0; i<broj.length(); i++)
    {
        if(broj[i]-minbroj[i]+'0'<'0')
        {
            for(int j=i-1; j>=0; j--)
            {
                if(broj[j]-1>='0')
                {
                    broj[j]--;
                    break;
                }
                else
                {
                    broj[j]='9';
                }
            }
            broj[i]=broj[i]-minbroj[i]+'9'+1;
        }
        else broj[i]=broj[i]-minbroj[i]+'0';
    }
    int loc=broj.length()-1;
    for(int i=0; i<broj.length(); i++)
    {
        if(broj[i]=='0')
        continue;
        else
        {
            loc=i;
            break;
        }
    }
    for(int i=loc; i<broj.length(); i++)
    {
        cout<<broj[i];
    }
    return 0;
}

Прегледување:

Регистрација:

Финкимен:

#include <iostream>
using namespace std;

int r, c, minpole=999999, minr, minc;
int pole[50][50];

bool check()
{
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
        {
            if(pole[i][j]!=-1)
                return false;
        }
    }
    return true;
}

void findmin()
{
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
        {
            if((pole[i][j]!=-1)&&(pole[i][j]<minpole))
            {
                minpole=pole[i][j];
                minr=i;
                minc=j;
            }
        }
    }
}

void fill(int x, int y)
{
    int val=pole[x][y];
    pole[x][y]=-1;
    if((x+1<r)&&(pole[x+1][y]>=val)) fill(x+1, y);
    if((x-1>=0)&&(pole[x-1][y]>=val)) fill(x-1, y);
    if((y+1<c)&&(pole[x][y+1]>=val)) fill(x, y+1);
    if((y-1>=0)&&(pole[x][y-1]>=val)) fill(x, y-1);
}

int main()
{
    int res=0;
    cin>>r>>c;
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
        {
            cin>>pole[i][j];
            if(pole[i][j]<minpole)
            {
                minr=i;
                minc=j;
                minpole=pole[i][j];
            }
        }
    }
    while(check()==false)
    {
        fill(minr, minc);
        res++;
        minpole=999999;
        findmin();
    }
    cout<<res;
    return 0;
}

Ајде камо open-source дух!

Моиве решенија ги ставив на Wiki-то

This message was edited 2 times. Last update was at 05/04/2011 01:07:18

Odzemanje:

This message was edited 2 times. Last update was at 05/04/2011 20:06:06

Задача Прекин, државен 2011 напредна група - задача 3.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<cmath>
#include<ctime>
#include<fstream>
#include<string>
#include<cstring>
#include<climits>

using namespace std;

#define sz(x) (int)((x).size())
#define all(c) (c).begin(),(c).end()
#define DBGM(x,y) if(DEBUG) cout << #x << ' ' << #y << ": " << x << ' ' << y << '\n'
#define MSI(x,y) memset((x),(y),sizeof(x));

#define DEBUG true;

class dijk
{
    public:
    int nd,cost,orig;
};

bool operator<(dijk a,dijk b)
{
    if(a.cost==b.cost) return a.nd>b.nd;
    return a.cost>b.cost;
}

list<int> bgn,en;
int res;
int remnr;
int n,m;
int taken;

list<int> cnn[101];
list<int> cost[101];
bool vis[101],add;
priority_queue<dijk> * que;

void proc(dijk in)
{
    if(vis[in.nd]) return;

dijk tmp;
    list<int>::iterator it,it2;

if(add)
    {
        bgn.push_back(in.orig);
        en.push_back(in.nd);
    }

vis[in.nd]=true;
    taken++;
    res+=in.cost;
    it=cnn[in.nd].begin();
    it2=cost[in.nd].begin();

while(it!=cnn[in.nd].end())
    {
        if(!vis[*it])
        {
            tmp.nd=*it;
            tmp.cost=*it2;
            tmp.orig=in.nd;
            que->push(tmp);
        }
        it++;
        it2++;
    }

}

int span()
{
    MSI(vis,0);
    res=0;
    taken=0;
    dijk tmp;
    tmp.nd=0;
    tmp.cost=0;
    tmp.orig=-1;

que->push(tmp);

while(taken<n && !que->empty())
    {
        tmp=que->top();
        que->pop();

proc(tmp);
    }
    if(taken<n)
    {
        return INT_MAX;
    }
    return res;
}

int main()
{
    int a,b,c,i,j,ares,bres=INT_MAX;
    que=new priority_queue<dijk>;
    add=true;

scanf("%d %d",&n,&m);

for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        a--;
        b--;
        cnn[a].push_back(b);
        cost[a].push_back(c);
        cnn[b].push_back(a);
        cost[b].push_back(c);
    }

ares=span();
    add=false;

list<int>::iterator ita,itb,itan,itbn,itc,itcn,itd,itdn;

while(bgn.begin()!=bgn.end())
    {
        if(*bgn.begin()==-1 || *en.begin()==-1)
        {
            bgn.pop_front();
            en.pop_front();
            continue;
        }

ita=cnn[*bgn.begin()].begin();
        itb=cost[*bgn.begin()].begin();
        itc=cnn[*en.begin()].begin();
        itd=cost[*en.begin()].begin();
        while(*ita!=*en.begin())
        {
            ita++;
            itb++;
        }
        itan=ita;
        itan++;
        cnn[*bgn.begin()].erase(ita);
        remnr=*itb;
        itbn=itb;
        itbn++;
        cost[*bgn.begin()].erase(itb);

while(*itc!=*bgn.begin())
        {
            itc++;
            itd++;
        }
        itcn=itc;
        itcn++;
        itdn=itd;
        itdn++;
        cnn[*en.begin()].erase(itc);
        cost[*en.begin()].erase(itd);

delete que;
        que=new priority_queue<dijk>;

bres=min(bres,span());

ita=itan;
        itb=itbn;
        itc=itcn;
        itd=itdn;
        cnn[*bgn.begin()].push_back(*en.begin());
        cnn[*en.begin()].push_back(*bgn.begin());
        cost[*bgn.begin()].push_back(remnr);
        cost[*en.begin()].push_back(remnr);
        bgn.pop_front();
        en.pop_front();
    }
    printf("%d %d\n",min(ares,bres),max(ares,bres));
   
    return 0;
}

This message was edited 1 time. Last update was at 05/04/2011 22:47:34

може објаснување за Прекин?

This message was edited 1 time. Last update was at 06/04/2011 16:01:14

frezeex koga ke imas vreme napisi objasnuvanje za finkimen.. Dupka sum u BFS & DFS..

ова е уствари дфс решение, со тоа што секогаш се означува поминатото поле со -1. Почнуваш од минимална висини и се движиш кон поголемите колку што можеш после пак бараш друго минимално поле па и од тоа почнуваш, и така на крајот све ќе поминеш и ќе изброиш колку пати така требало да се бара минимум. секое поминување на еден дфс проверуваш дали сите членови се -1. Ако се, прекинуваш и печатиш решение

FREEZX wrote:може објаснување за Прекин?

Задачата ја решавам со алгоритам на Прим за наоѓање minimum spanning tree во граф. Тоа го прави функцијата span().

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

Прим има сложеност V log E, и во најлош случај се пушта E пати, така да сложеноста на ова решение е V * E * log E, што комотно поминува во дадените ограничувања.

Постои уште едно решение за 100 поени, со користење на Прим заедно со Union-Find структура и алгоритам, ама сметам дека тоа е доста потешко од ова...