Revizia anterioară Revizia următoare
Solutii la concursul acm 2013 etapa nationala partea I
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;
#define MaxN 110000
#define ll 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(int i=0;i<A[nod].size();i++)
if(!viz[A[nod][i].first])
{
DF(A[nod][i].first);
T[A[nod][i].first] = nod;
Fii[nod] += Fii[A[nod][i].first];
}
}
inline double suma(void)
{
ll sum = 0;
for(int i=0;i<=N;i++)
for(int j=0;j<A[i].size();j++)
if(A[i][j].first > i)
{
if(T[i] != A[i][j].first)
sum += (ll)A[i][j].second*Fii[A[i][j].first]*(N-Fii[A[i][j].first]);
else
sum += (ll)A[i][j].second*Fii[i]*(N-Fii[i]);
}
return sum/((ll)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;
}