[PJWSTK] ASD – Projekt 1 – Rozwiązanie

Pierwszy projekt z ASD:

Rozważmy zbiór P={p(0), p(1), ..., p(n-1)} składający się z n społeczności lokalnych, dla których ustalona jest relacja bezpośredniego sąsiedztwa. Ze zbioru P wybieramy k róznych elementów, które będą stanowiły punkty startowe kampanii wyborczych k kandydatów q(0), q(1), ..., q(k-1). Dalej proces realizacji kampanii wyborczych przebiega w turach tak, że:

• tura 0: każdy z kandydatów q(j) dla 0<=j<=k-1 zakłada w punkcie startowym swojej kampanii sztab wyborczy,
• ...
• tura i, kork I: każdy z kandydatów z każdego sztabu wyborczego zlokalizowanego w dowolnej społecznosci p(j)dla 0<=j<=n-1, odwiedza wszystkie społeczności bezpośrednio sąsiednie z w/w elementem zbioru P, gdzie zakłada swoje komitety wyborcze, pod warunkiem, że nie ma w nich już własnych sztabów wyborczych, bądź sztabów wyborczych innych kandydatów,
• tura i, krok II: w każdej społeczności p(j) dla 0<=j<=n-1, dla której założony jest komitet wyborczy co najmniej jednego kandydata odbywają się prawybory, w których zwycięża ten kandydat, którego liczba sztabów wyborczych w społecznościach bezpośrednio sąsiednich (stan z początku i-tej tury) ze społecznością p(j) jest:

wariant A: najmniejsza (w przypadku remisu wygrywa kandydat o większej wartości indeksu l dla q(l)),

• wariant B: największa (w przypadku remisu wygrywa kandydat o mniejszej wartości indeksu l dla q(l)).

• tura i, kork III: zwycięstow w prawyborach w danej społeczności uprawnia kandydata do założenia sztabu wyborczego w miejsce komitetu wyborczego,
• ...

i kończy się z chwilą, gdy wszystkie społeczności lokalne należące do zbioru P mają ustalone sztaby wyborcze kandydatów.

Ustal finansowanie kosztów kampanii wyborczej, w zależności od przyjętego wariantu rozstrzygania prawyborów (wariant A albo wariant B), dla każdego z k kandydatów, jeżeli koszty kampanii wyborczej mierzymy ostateczną liczbą założonych sztabów wyborczych w obrębie rozważanego zbioru społeczności lokalnych P.

Wejście

Kolejno:

• liczba naturalna dodatnia definiujaca liczbę 1<=n<=10^4 społeczności lokalnych, znak nowego wiersza/linii (ASCII kod 10),
• ciąg 0<=m<=10^6 wierszy postaci liczba naturalna x znak odstępu/spacjii (ASCII kod 32) liczba naturalna y znak nowego wiersza/linii (ASCII kod 10) zakończony wierszem specjalnym postaci -1 znak odstępu/spacjii (ASCII kod 32) -1 znak nowego wiersza/linii (ASCII kod 10), z których każdy właściwy wiersz reprezentuje bezpośrednie sąsiedztwo społeczności lokalnych indeksowanych kolejno liczbami x i y,
• liczba naturalna dodatnia definiujaca liczbę 1<=k<=10^4 i k<=n kandydatów, znak nowego wiersza/linii (ASCII kod 10),
• ciąg k wierszy postaci liczba naturalna z znak nowego wiersza/linii (ASCII kod 10), gdzie liczba z zawarta w i-tym wierszu reprezentuje indeks punktu startowego (społeczności lokalnej) każdego kolejnego kandydata począwszy od kandydata q(0).

Wyjście

Ciąg k wierszy postaci liczba naturalna a znak odstępu/spacjii (ASCII kod 32) liczba naturalna b znak nowego wiersza/linii (ASCII kod 10), z których każdy reprezentuje kolejno koszt kampanii wyborczej w wariancie A (wartość a) i w wariancie B (wartość b) każdego kolejnego kandydata począwszy od kandydata q(0).

Złożoności i limity

Złożoność czasowa O((n^2)k), złożoność pamięciowa O(n+m+k), gdzie n jest liczbą społeczności lokalnych, m jest rozmiarem relacji sąsiedztwa na zbiorze P, a k jest liczbą kandydatów. Fizyczny limit pamięci ograniczony przez 10 MB.

Przykład 1

Wejście:

3
0 1
1 2
0 2
-1 -1
2
0
1

Wyjście:

1 2
2 1

Przykład 2

Wejście:

6
1 0
2 1
3 0
3 1
3 2
4 2
4 3
5 0
5 2
-1 -1
3
0
1
5

Wyjście:

1 3
2 2
3 1

Rozwiązanie w C++:

#include<stdio.h>

class Town;
class Thief;

class ListElementTown
{
    public:
		Town* town;
		ListElementTown* next;

		ListElementTown(Town* m)
		{
			this->town = m;
			this->next = NULL;
		}

		ListElementTown(Town* m, ListElementTown* next)
		{
			this->town = m;
			this->next = next;
		}
};

class ListTowns
{
	public:
		ListElementTown* first;
		int elementsCounter;

		ListTowns()
		{
			first = NULL;
			elementsCounter = 0;
		}

		Town* get(int elementIterator)
		{
			ListElementTown* tmp = first;
			for(int i = 0; i < elementIterator; i++)
				tmp = tmp->next;

			return tmp->town;
		}

		void add(Town* m)
		{
			if(this->first == NULL)
				this->first = new ListElementTown(m);
			else
				first = new ListElementTown(m, first);

			elementsCounter++;
		}

		bool contains(Town* m)
		{
			ListElementTown* tmp = first;
			while(tmp)
			{
				if(m == tmp->town)
					return true;

				tmp = tmp->next;
			}
			return false;
		}

		void clear()
		{
			first = NULL;
			elementsCounter = 0;
		}
};

class ListElementThief
{
	public:
		Thief* thief;
		ListElementThief* next;

		ListElementThief(Thief* t)
		{
			this->thief = t;
			this->next = NULL;
		}

		ListElementThief(Thief* t, ListElementThief* next)
		{
			this->thief = t;
			this->next = next;
		}
};

class ListThiefs
{
	public:
		ListElementThief* first;
		int elementsCounter;

		ListThiefs()
		{
			first = NULL;
			elementsCounter = 0;
		}

		Thief* get(int elementIterator)
		{
			ListElementThief* tmp = first;
			for(int i = 0; i < elementIterator; i++)
				tmp = tmp->next;

			return tmp->thief;
		}

		void add(Thief* t)
		{
			if(this->first == NULL)
				this->first = new ListElementThief(t);
			else
			{
				first = new ListElementThief(t, first);
			}
			elementsCounter++;
		}

		bool contains(Thief* t)
		{
			ListElementThief* tmp = first;
			while(tmp)
			{
				if(t == tmp->thief)
					return true;

				tmp = tmp->next;
			}
			return false;
		}

		void clear()
		{
			first = NULL;
			elementsCounter = 0;
		}
};
class Town
{
	public:
		bool koniec;
		int id;
		Thief* electionStaffA;
		Thief* electionStaffB;
		Thief* tmpWinnerA;
		Thief* tmpWinnerB;
		ListThiefs* candidatesA;
		ListThiefs* candidatesB;
		ListTowns* neighbors;

		Town(int i)
		{
			koniec = false;
			id = i;
			electionStaffA = NULL;
			electionStaffB = NULL;
			tmpWinnerA = NULL;
			tmpWinnerB = NULL;
			candidatesA = new ListThiefs();
			candidatesB = new ListThiefs();
			neighbors = new ListTowns();
		}
};

class Thief
{
	public:
		int id;
		int tmpCounterA;
		int tmpCounterB;
		int campaignCostA;
		int campaignCostB;

		Thief(int indeks)
		{
			this->id = indeks;
			this->tmpCounterA = 0;
			this->tmpCounterB = 0;
			this->campaignCostA = 0;
			this->campaignCostB = 0;
		}
};

int main()
{ 
	int workingElectionStaffCounterA = 0;
	int workingElectionStaffCounterB = 0;
	int liczba_miast = 0;
	int liczba_kandydatow = 0;
	fscanf(stdin, "%d", &liczba_miast);
	Town* towns[liczba_miast];
	for(int i = 0; i < liczba_miast; i++)
	{
		towns[i] = new Town(i);
	}
	int towna;
	int townb;
	fscanf(stdin, "%d", &towna);
	fscanf(stdin, "%d", &townb);
	while(towna != -1 && townb != -1)
	{
		towns[towna]->neighbors->add(towns[townb]);
		towns[townb]->neighbors->add(towns[towna]);
		fscanf(stdin, "%d", &towna);
		fscanf(stdin, "%d", &townb);
	}
	fscanf(stdin, "%d", &liczba_kandydatow);
	Thief* candidates[liczba_kandydatow];
	for(int i = 0; i < liczba_kandydatow; i++)
	{
		candidates[i] = new Thief(i);
	}
	int sztab;
	for(int i = 0; i < liczba_kandydatow; i++)
	{
		fscanf(stdin, "%d", &sztab);
		towns[sztab]->electionStaffA = candidates[i];
		candidates[i]->campaignCostA++;
		workingElectionStaffCounterA++;
		towns[sztab]->electionStaffB = candidates[i];
		candidates[i]->campaignCostB++;
		workingElectionStaffCounterB++;
	}
	ListTowns* modifiedTowns = new ListTowns();
	while(workingElectionStaffCounterA != liczba_miast && workingElectionStaffCounterB != liczba_miast)
	{
		modifiedTowns->clear();
		for(int i = 0; i < liczba_miast; i++)
		{
			if(towns[i]->electionStaffA != NULL && towns[i]->electionStaffB != NULL)
			{
				for(int i2 = 0; i2 < towns[i]->neighbors->elementsCounter; i2++)
				{
					if(towns[i]->neighbors->get(i2)->electionStaffA == NULL && towns[i]->neighbors->get(i2)->electionStaffB == NULL)
					{
						if(!(towns[i]->neighbors->get(i2)->candidatesA->contains(towns[i]->electionStaffA)))
						{
							towns[i]->neighbors->get(i2)->candidatesA->add(towns[i]->electionStaffA);
						}
						if(!(towns[i]->neighbors->get(i2)->candidatesB->contains(towns[i]->electionStaffB)))
						{
							towns[i]->neighbors->get(i2)->candidatesB->add(towns[i]->electionStaffB);
						}
						if(!(modifiedTowns->contains(towns[i]->neighbors->get(i2))))
						{
							modifiedTowns->add(towns[i]->neighbors->get(i2));
						}
					}
				}
			}
		}
		ListElementTown* startElement = modifiedTowns->first;
		int loopsCounter = modifiedTowns->elementsCounter;
		for(int i = 0; i < loopsCounter; i++)
		{
			Town* currentTown = startElement->town;
			Thief* tmpCandidate = NULL;
			for(int x = 0; x < liczba_kandydatow; x++)
			{
				candidates[x]->tmpCounterA = 0;
				candidates[x]->tmpCounterB = 0;
			}
			int loopsCounter_2 = currentTown->neighbors->elementsCounter;
			ListElementTown* neighborsLoop = currentTown->neighbors->first;
			for(int ii = 0; ii < loopsCounter_2; ii++)
			{
				Town* tmpTown = neighborsLoop->town;
				if(tmpTown->electionStaffA != NULL)
				{
					tmpTown->electionStaffA->tmpCounterA++;
					tmpTown->electionStaffB->tmpCounterB++;
				}
				neighborsLoop = neighborsLoop->next;
			}
			Thief* winnerA = currentTown->candidatesA->get(0);
			Thief* winnerB = currentTown->candidatesB->get(0);

			loopsCounter_2 = currentTown->candidatesA->elementsCounter;
			for(int i2 = 1; i2 < loopsCounter_2; i2++)
			{
				tmpCandidate = currentTown->candidatesA->get(i2);
				if((winnerA->tmpCounterA > tmpCandidate->tmpCounterA) || (winnerA->tmpCounterA == tmpCandidate->tmpCounterA && winnerA->id < tmpCandidate->id))
					winnerA = tmpCandidate;
			}
			currentTown->tmpWinnerA = winnerA;
			currentTown->candidatesA->clear();
			loopsCounter_2 = currentTown->candidatesB->elementsCounter;
			for(int i2 = 1; i2 < loopsCounter_2; i2++)
			{
				tmpCandidate = currentTown->candidatesB->get(i2);
				if((winnerB->tmpCounterB < tmpCandidate->tmpCounterB) || (winnerB->tmpCounterB == tmpCandidate->tmpCounterB && winnerB->id > tmpCandidate->id))
					winnerB = tmpCandidate;
			}
			currentTown->tmpWinnerB = winnerB;
			currentTown->candidatesB->clear();
			startElement = startElement->next;
		}
		startElement = modifiedTowns->first;
		loopsCounter = modifiedTowns->elementsCounter;
		for(int i = 0; i < loopsCounter; i++)
		{
			Town* tmpTown = startElement->town;
			tmpTown->electionStaffA = tmpTown->tmpWinnerA;
			tmpTown->electionStaffB = tmpTown->tmpWinnerB;
			tmpTown->electionStaffA->campaignCostA++;
			tmpTown->electionStaffB->campaignCostB++;
			workingElectionStaffCounterA++;
			workingElectionStaffCounterB++;
			startElement = startElement->next;
		}
	}
	for(int i = 0; i < liczba_kandydatow; i++)
	{
		fprintf(stdout, "%d %d\n",candidates[i]->campaignCostA,candidates[i]->campaignCostB);
	}
	return 0;
}