Despre Blog

Ultimele insemnari

Categorii

Blogroll

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-06-17 19:06:21.
Revizia anterioară   Revizia următoare  

Solutii la concursul acm 2013 etapa nationala partea I

S7012MY
Petru Trimbitas
17 iunie 2013

Duminică, 16 iunie a avut loc faza naţionala a concursului acm icpc. Pagina concursului o gasiţi aici
iar clasamentul aici
La concurs au participat peste 50 echipe iar setul de probleme a fost unul echilibrat.

Voi prezenta in continuare o parte din probleme şi soluţiile acestora

G. Election Time

Aceasta a fost cea mai simplă problemă din concurs, fiind rezolvată de marea majoritate a echipelor.
Problema ne cerea să determinăm câştigătorul alegerilor dupa 2 tururi ştiind cate voturi va obţine fiecare candidat in cele 2 tururi. În plus după primul tur rămâneau doar primii k candidati.

O soluţie ar fi sortarea candidaţilor descresrescător după numărul de voturi primite în primul tur, iar pe urmă sortarea primilor k după numărul de votur din al doilea tur. Pentru a nu complica implementarea am ales sortarea unui vector de indici in funcţie de numărul de voturi.

#include <iostream>
#include <algorithm>
#define DN 50005
using namespace std;

int n,k,ind[DN],a[DN],b[DN];

bool cmp(int x,int y) {
	return a[x]>a[y];
}

bool cmp2(int x,int y) {
	return b[x]>b[y];
}

int main() {
	cin>>n>>k;
	for(int i=1; i<=n; ++i) {
		cin>>a[i]>>b[i];
		ind[i]=i;
	}
	sort(ind+1,ind+n+1,cmp);
	sort(ind+1,ind+k+1,cmp2);
	cout<<ind[1]<<'\n';
}

H. Stones II

A doua problema ca dificultate din concurs ne dădea N (N <= 100 000) grămezi de pietre şi ne cerea să le reunim cu un cost cât mai mic. Pentru a putea reuni grămezile putem lipi la un pas două grămezi cu un cost egal cu numărul de pietre din cele două grămezi la un loc.

Pentru a rezolva problema putem aplica o strategie de tip greedy în care la fiecare pas luăm cele mai mici două grămezi şi le reunim. Pentru a se încadra în timp şi pentru a fi corect e necesară folosirea unui multiset şi a tipului de date long long.

F. Average distance

După cum îi spune şi numele această problemă ne cere sa calculăm costul mediu al muchiilor dintr-un arbore.

Pentru a rezolva problema observăm că costul mediu e egal cu suma costurilor drumurilor din arbore împărţită la numărul total de drumuri.
Numărul de drumuri e egal cu N*(N-1)/2 (Combinări de N luate câte doua, fiecare drum fiind definit de 2 noduri).
Pentru a calcula suma costurilor drumurilor ne interesează fiecare muchie în câte drumuri apare.
O muchie (A,B) apare in orice drum definit de un nod din subarborele lui A(inclusiv A) şi de un nod care nu e in subarborele lui A.

//Cristian Lambru
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

typedef vector<pair<int,int> >::iterator it;

#define MaxN 110000
#define ld long double

int N;
int T[MaxN],Fii[MaxN],viz[MaxN];
vector<pair<int,int> > A[MaxN];

void citire(void)
{
    int a,b,c;

    scanf("%d",&N);
    for(int i=1;i<N;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        A[a].push_back(make_pair(b,c));
        A[b].push_back(make_pair(a,c));
    }
}

inline void DF(int nod)
{
    viz[nod] = 1;
    Fii[nod] = 1;
    
    for(it i=A[nod].begin();i<A[nod].end();i++)
        if(!viz[i->first])
        {
            DF(i->first);
            T[i->first] = nod;
            Fii[nod] += Fii[i->first];
        }
}

inline double suma(void)
{
    ld sum = 0;

    for(int i=0;i<=N;i++)
        for(it j=A[i].begin();j<A[i].end();j++)
            if(j->first > i)
            {
                if(T[i] != j->first)
                    sum += (ld)j->second*Fii[j->first]*(N-Fii[j->first]);
                else
                    sum += (ld)j->second*Fii[i]*(N-Fii[i]);
            }

    return sum/((ld)N*(N-1)/2);
}

inline void sterge(void)
{
    for(int i=0;i<N;i++)
        A[i].clear(), Fii[i] = T[i] = viz[i] = 0;
}

int main()
{
    //freopen("test.txt","r",stdin);
    int T;
    scanf("%d",&T);

    for(int i=1;i<=T;i++)
    {
        citire();    
        DF(0);

        printf("%lf\n",suma());
        sterge();
    }

    return 0;
}

E. Slim Span

Această problemă cere pentru un graf cu N (N<=100) noduri să aflăm diferenţa minimă dintre muchia de cost maxim şi cea de cost minim dintr-un arbore de acoperire al grafului.

Sursa

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
#define DN 105
using namespace std;

int n,m,pre[DN];
vector<pair<int,pair<int,int> > > mc;

int find(int x) {
	if(pre[x]==x) return x;
	pre[x]=find(pre[x]);
	return pre[x];
}

void unite(int x,int y) {
	pre[find(x)]=find(y);
}

int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	for(;;) {
		cin>>n>>m;
		if(!n && !m) break;

		for(int i=0; i<m; ++i) {
			int a,b,c;
			cin>>a>>b>>c;
			mc.push_back(make_pair(c,make_pair(a,b)));
		}
		sort(mc.begin(),mc.end());
		int rez=(1<<30);
		for(int fm=0; fm<mc.size(); ++fm) {
//Alegem muchia care să aibă costul cel mai mic din apm
			int nrm=0,mx;
			for(int i=1; i<=n; ++i) pre[i]=i;
			for(int i=fm; i<mc.size(); ++i) if(find(mc[i].y.x)!=find(mc[i].y.y)) {
				unite(mc[i].y.x,mc[i].y.y);
				mx=mc[i].x;
				++nrm;
			}
			if(nrm==n-1) rez=min(rez,mx-mc[fm].x);
		}
		if(rez!=(1<<30)) cout<<rez<<'\n';
		else cout<<"-1\n";
		mc.clear();
	}
}
Categorii: