Текущ брой на Списание ИнфоМан
 


Балканска олимпиада по информатика 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