Балканска олимпиада по информатика 2005, Задача 1.3. COUPLES
Уловието на задачата може да прочетете
тук.
Решение
Описаното по-долу решение е предложено от авторите на
задачата. То работи достатъчно бързо за тестовете, използвани на състезанието.
Въпреки това могат да се изберат тестове, за които то да не работи за
позволеното от журито време от 15
секунди. В следващите статии на списанието очаквайте материал,
където ще бъде описан подход, с помощта на който може да се напише
по-ефективно решение.
Лесно се забелязва, че ако даден човек има повече от Kсрещания с друг човек, то и двамата
са участвaли
задължително на поне K+1партита. Ето защо, за решението на
тази задача входът може да се обходи два пъти. Първият път се проверява кои са
тези хора, които са посетили повече от Kпартита.
Нека тези хора образуват множеството M. При второто обхождане за всеки човек
от M се проверява колко пъти той е бил с
всеки от останалите хора от Mна едно и също парти. Двойките, които
са се срещали повече от Kпъти се преброяват. Техният брой дава
отговора на задачата.
Примерна реализация
#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 600004 // maximum number of parties
#define MAXM 20004 // maximum number of people
#define MAXK 1004 // maximum number of meetings
#define INP "couples.in"
#define OUT "couples.out"
int n,m,k;
// here the infomration about the parties is stored
vector<int> parties[MAXN];
// keeps the number attended parties by each person
int att[MAXM];
// a list of all the people that were at at least k+1 partiest
vector<int> leftp;
// the new number assigned to each of the people in the vector 'leftp'
int newnum[MAXM];
// a matrix which keeps for each couple of people in the vector 'leftp'
// how many times they have met
int* nummeet[MAXM];
// the number of people in 'leftp'
int numpos;
// the answer
int ans;
int main()
{
int i,i2,i3;
int id,tmp,brp;
FILE *f;
f = fopen(INP,"r");
fscanf(f,"%d %d %d",&n,&m,&k);
// reading the input
for(i=0;i<n;i++)
{
fscanf(f,"%d %d",&id,&brp);
for(i2=0;i2<brp;i2++)
{
fscanf(f,"%d",&tmp);
parties[i].push_back(tmp);
att[tmp]++;
}
}
fclose(f);
for(i=0;i<m;i++)
{
if(att[i]>k)
{
newnum[i] = leftp.size();
leftp.push_back(i);
}
else
newnum[i] = -1;
}
numpos = leftp.size();
for(i=0;i<numpos;i++)
{
nummeet[i] = new int[numpos];
for(i2=0;i2<numpos;i2++)
nummeet[i][i2] = 0;
}
int v1,v2;
// counting the number of meetings for each couple
for(i=0;i<n;i++)
{
for(i2=0;i2<parties[i].size();i2++)
{
if(newnum[parties[i][i2]]!=-1)
for(i3=i2+1;i3<parties[i].size();i3++)
if(newnum[parties[i][i3]]!=-1)
{
v1 =
newnum[parties[i][i2]];
v2 =
newnum[parties[i][i3]];
nummeet[v1][v2]++;
nummeet[v2][v1]++;
}
}
}
// counting the couples that have met more than k times
for(i=0;i<numpos;i++)
for(i2=i+1;i2<numpos;i2++)
if(nummeet[i][i2]>k)
ans++;
f = fopen(OUT,"w");
fprintf(f,"%d\n",ans);
fclose(f);
for(i=0;i<numpos;i++)
delete nummeet[i];
return 0;
}
Автор: Антон Димитров
обратно към брой 27
|