Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-06-17 19:48:33.
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<vector>
using namespace std;

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

#define MaxN 110000
#define ld long double

int N;
ld Suma = 0;
int Fii[MaxN],viz[MaxN];
vector<pair<int,int> > A[MaxN];

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

            Suma += (ld)(i->second)*Fii[i->first]*(N-Fii[i->first]);
        }
}

int main()
{
    citire();    
    parcurgere(0);

    cout << Suma/((ld)N*(N-1)/2);
}

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.

Dimensiunea datelor de intrare ne permite ca pentru fiecare muchie să alegem doar muchii de cost mai mare până când obţinem un arbore de acoperire şi să alegem cea mai bună diferenţă dintre toţi arborii de acoperire obţinuţi.

I. More lumber is required

J. Template Library Management

K. Fast Arrangement

Categorii: