Wszystko czego potrzebują studenci

Drugi projekt z ASD:

Rozważmy nieskierowany pełny graf ważony G=(V,E,w), gdzie V={v(0), v(1), …, v(n-1)} jest zbiorem wierzchołków grafu. Waga krawędzi w(i,j) łączącej pewne dwa wierzchołki grafu v(i) oraz v(j) jest równa

w(i,j)=((i+1)*(j+1)) mod p + 1,

gdzie p jest zadaną dodatnią liczbą naturalną. Dalej pajączkiem nazywamy acykliczny podzbiór krawędzi grafu Gpowstały zgodnie z następującym schematem:

• krok 1: wybieramy pewien podzbiór startowy V’ zbioru wierzchołków V i tworzymy początkowo pusty zbiór krawędzi E’,
• krok 2: spośród wszystkich niewykluczonych krawędzi incydentnych z dowolnym wierzchołkiem zbioru V’wybieramy krawędź (v’,w’) o minimalnej wadze, remisy rozstrzygamy zgodnie z porządkiem < na liczbach utworzonych z etykiet wierzchołków krańcowych krawędzi uporządkowanych w kolejności niemalejącej i zapisanych w systemie n-arnym, np. dla krawędzi (34,111) i (122,17) mamy odpowiednio 17 122 < 34 111,
• krok 3: jeżeli zbiór E’ powiększony o wybrana krawędź (v’,w’) tworzy acykliczny podzbiór krawędzi grafu G, to do zbioru E’ dodajemy tą właśnie krawędź, a zbiór V’ powiększamy o wierzchołki krańcowe rozważanej krawędzi, odpowiednio v’ oraz w’ (suma algebraiczna zbiorów V’ i {v’,w’}), następnie krawędź (v’,w’) uznajemy zawykluczoną,
• krok 4: jeżeli istnieje o najmniej jedna niewykluczona krawędź incydentna z dowolnym wierzchołkiem ze zbioruV’, to powracamy do kroku 2, w przeciwnym przypadku pajączka uznajemy za nieaktywnego.

Dalej zbiór S={s(0), s(1), …, s(k-1)} jest zbiorem pajączków. Ustal ostateczną liczbę krawędzi składowych oraz łączną sumę wag krawędzi składowych każdego z k pajączków przyjmując następujący schemat równoczesnej konstrukcji pajączków:

• krok I: dla każdego z pajączków wykonaj krok 1,
• krok II: spośród wszystkich aktywnych pajączków wybieramy pajączka s’, którego aktualna suma wag krawędzi składowych jest minimalna, remisy rozstrzygamy na korzyść pajączka o mniejszym indeksie,
• krok III: dla pajączka s’ wykonujemy jednokrotnie złożenie kroków 2, 3 i 4,
• krok IV: jeżeli istnieje co najmniej jeden aktywny pajączek, to powracamy do kroku II, w przeciwnym przypadku kończymy działanie algorytmu,

zakładając, że krawędź użyta przez dowolnego pajączka (tj. włączona do stosownego zbioru E’) nie może być ponownie użyta przez żadnego innego pajączka.

Wejście

Kolejno:

• liczba naturalna dodatnia definiująca liczbę 1<=n<=10^3 wierzchołków grafu G, znak nowego wiersza/linii (ASCII kod 10),
• liczba naturalna dodatnia definiująca liczbę 1<=p<=10^6, znak nowego wiersza/linii (ASCII kod 10),
• liczba naturalna dodatnia definiująca liczbę 1<=k<=10^3 pajączków, znak nowego wiersza/linii (ASCII kod 10),
• ciąg k wierszy postaci liczba naturalna l znak odstępu/spacji (ASCII kod 32) ciąg l liczb naturalnych v1, v2, …, vl, oddzielonych znakiem odstępu/spacji (ASCII kod 32) i zakończonych znakiem nowego wiersza/linii (ASCII kod 10), gdzie l jest licznością zbioru startowego V’ każdego kolejnego pajączka począwszy od s(0) do s(k-1)włącznie, a v1, v2, …, vl jest postacią tego zbioru (ciąg elementów zbioru).

Wyjście

Ciąg k wierszy postaci liczba naturalna x znak odstępu/spacji (ASCII kod 32) liczba naturalna y znak nowego wiersza/linii (ASCII kod 10), gdzie x jest ostateczną liczbą krawędzi składowych a y jest łączną sumą wag krawędzi składowych każdego kolejnego pajączka począwszy od s(0) do s(k-1) włącznie.

Złożoności i limity

Koszt czasowy i pamięciowy rozwiązania ograniczony przez limity dostępnego czasu i dostępnej pamięci ustalone dla rozważanego zadania na automatycznej platformie sprawdzającej.

Przykład 1

Wejście:
4
5
1
2 0 1

Wyjście:
3 8

Przykład 2

Wejście:
5
7
2
2 0 2
1 4

Wyjście:
4 15
4 18

Rozwiązanie w Javie:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;

class Edge
{
    short node_1 = 0;
	short node_2 = 0;
	int points = 0;

	Edge(short node_1, short node_2, int points)
	{
		this.node_1 = node_1;
		this.node_2 = node_2;
		this.points = points;
	}
};

class EdgesSorter implements Comparator<Edge>
{
	@Override
	public int compare(Edge edge_1, Edge edge_2)
	{
		if(edge_1.points != edge_2.points)
		{
			return edge_1.points - edge_2.points;
		}
		else
		{
			return edge_1.node_1 - edge_2.node_1;
		}
	}
}

class Spider
{
	short id = 0;
	int points = 0;
	short edgesCount = 0;
	boolean[] nodes = null;
	short[] parentNode = null;
	Spider(short id)
	{
		this.id = id;
		nodes = new boolean[Main.nodesCount];
		parentNode = new short[Main.nodesCount];
	}
}

public class Main
{
	static int nodesCount = 0;
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		nodesCount = scanner.nextInt();
		int pNumber = scanner.nextInt();
		short spidersCount = scanner.nextShort();
		Spider[] spidersList = new Spider[spidersCount];
		Spider[] sortedSpiders = new Spider[spidersCount];
		short spiderNodesCount = 0;
		Spider spider = null;
		for(short spiderID = 0; spiderID < spidersCount; spiderID++)
		{
			spider = new Spider(spiderID);
			spidersList[spiderID] = spider;
			sortedSpiders[spiderID] = spider;
			spiderNodesCount = scanner.nextShort();
			boolean[] nodes = new boolean[nodesCount];
			while(spiderNodesCount-- > 0)
			{
				nodes[scanner.nextShort()] = true;
			}
			spider.nodes = nodes;
			short[] parentNode = new short[nodesCount];
			for(short node = 0; node < nodesCount; node++)
			{
				parentNode[node] = node;
			}
			spider.parentNode = parentNode;
		}
		List<Edge> edgesList = new ArrayList<Edge>();
		for(short node_1 = 1; node_1 <= nodesCount; node_1++)
		{
			for(short node_2 = (short) (node_1+1); node_2 <= nodesCount; node_2++)
			{
				edgesList.add(new Edge((short) (node_1 - 1), (short) (node_2 - 1), ((node_1 * node_2) % pNumber) + 1));
			}
		}
		Collections.sort(edgesList, new EdgesSorter());
		short topParent_1 = 0;
		short topParent_2 = 0;
		short activeSpidersCount = spidersCount;
		boolean deactiveSpider = true;
		short highestPrioritySpiderID = 0;
		short tmpNode = 0;
		while(activeSpidersCount > 0)
		{
			for(short activeSpiderID = 0; activeSpiderID < activeSpidersCount; activeSpiderID++)
			{
				spider = spidersList[activeSpiderID];
				Spider mSpider = spidersList[highestPrioritySpiderID];
				if(spider.points < mSpider.points || (spider.points == mSpider.points && spider.id < mSpider.id))
				{
					highestPrioritySpiderID = activeSpiderID;
				}
			}
			spider = spidersList[highestPrioritySpiderID];
			deactiveSpider = true;
			for(Edge edge : edgesList)
			{
				if(spider.nodes[edge.node_1] == true || spider.nodes[edge.node_2] == true)
				{
					tmpNode = edge.node_1;
					topParent_1 = spider.parentNode[tmpNode];
					while(tmpNode != topParent_1)
					{
						tmpNode = topParent_1;
						topParent_1 = spider.parentNode[topParent_1];
					}
					tmpNode = edge.node_2;
					topParent_2 = spider.parentNode[tmpNode];
					while(tmpNode != topParent_2)
					{
						tmpNode = topParent_2;
						topParent_2 = spider.parentNode[topParent_2];
					}
					if(topParent_1 != topParent_2)
					{
						spider.nodes[edge.node_1] = true;
						spider.nodes[edge.node_2] = true;
						spider.points += edge.points;
						spider.edgesCount++;
						spider.parentNode[topParent_1] = topParent_2;
						deactiveSpider = false;
						edgesList.remove(edge);
						break;
					}
				}
			}
			if(deactiveSpider)
			{
				spidersList[highestPrioritySpiderID] = spidersList[--activeSpidersCount];
			}
			highestPrioritySpiderID = 0;
		}
		for(Spider sortedSpider : sortedSpiders)
		{
			System.out.println(sortedSpider.edgesCount + " " + sortedSpider.points);
		}
	}
}

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;
}

Czwarte zadanie z ASD:

Rozważmy uporządkowany ciąg C różnych liczb naturalnych długości n>0 oraz wybrany element c tego ciągu. Dalej przyjmujemy, że algorytm wyszukiwania binarnego jest zgodny z poniższym (zakładamy indeksowanie elementów ciągu od wartości początkowej 0):

1  l:=0, r:=n-1, m:=(l+r)/2;
2  
3  while (C[m]!=c) {
4    if (C[m]<c)
5      l:=m+1;
6    else
7      r:=m-1;
8    m:=(l+r)/2;
9  }

Wprowadzamy teraz modyfikacje algorytmu wyszukiwania binarnego polegającą na tym, że w miejsce instrukcji zawartych w wierszach 4-8 w pewnej iteracji rozważanego algorytmu wykonujemy sekwencyjne przeszukanie pozostałego fragmentu ciągu począwszy od pozycji l aż do skutku, tj.

4  while (C[l]!=c)
5    l:=l+1;
6
7  m:=l;
8

Załóżmy, że koszt wykonania algorytmu wszykiwania binarnego (zarówno bez i z w/w modyfikacją) oznaczamy jako COST i definiujemy zależnością:

COST=sqrt(a)*div+cmp

gdzie a jest pewną dodatnią stałą naturalną, sqrt(a) jest funkcją, której rezultatem jest część naturalna z pierwiastka z liczby a oraz div i cmp to odpowiednio liczba operacji dzielenia przez 2 (wiersze 1 i 8) oraz liczba operacji prówniania z elementami ciągu C występujacych w rozważanym algorytmie (wiersze 3 i 4).

Wyznacz najmniejszą możliwą wartość stałej a, dla której wykonanie algorytmu wyszukiwania binarnego z modyfikacją sekwencyjną niezależnie od wybranej iteracji zastosowania tej modyfikacji, prowadzi w każdym przypadku do rozwiązania o koszcie mniejszym niż standardowe wyszukiwanie binarne (tj. algorytm bez modyfikacji sekwencyjnej).

Wejście

Wiersz zawierający ciąg liczb naturlanych oddzielonych znakiem odstępu/spacji (ASCII kod 32) i zakończony znakiem końca pliku (EOF), gdzie:

• pierwszy element ciągu definiuje długość n ciągu C tak, że n zawarte jest w przedziale wartości [1,10^6],
• kolejne elementy ciągu reprezentują elementy właściwe ciagu C i zawarte są w przedziale wartości [0,10^9],
• ostatni element ciągu wejściowego reprezentuje wybrane element c ciągu C.

Wyjście

Wiersz zawierajacy pojedynczą liczbę naturalną nie większą niż 10^9 będącą rozwiązaniem postawionego problemu (wiersz pusty w przypadku braku rozwiązania).

Złożoności i limity

Złożoność czasowa O(n), złożoność pamięciowa O(n), gdzie n jest długością ciągu podanego na wejściu. Fizyczny limit pamięci zależny od rozmiaru danych wejściowych i ograniczony przez 4n B + 1 KB.

Przykład 1

Wejście:
3 1 2 3 3

Wyjście:
9

Przykład 2

Wejście:
10 0 1 2 3 4 5 6 7 8 9 0

Wyjście:
1

Rozwiązanie w C++:

#include <stdio.h>

int main()
{
    int n;
    fscanf(stdin, "%i", &n);
	int* C = new int[n];
	for(int i = 0; i < n; i++)
	{
		fscanf(stdin, "%i", &C[i]);
	}
	int c;
	fscanf(stdin, "%i", &c);
	n--;
	int l = 0;
	int r = n;
	int m = (l + r) / 2;
	int binarneDzielenie = 1;
	int binarnePorownania = 1;
	while(C[m] != c)
	{
		binarnePorownania++;
		if(C[m] < c)
			l = m + 1;
		else
			r = m - 1;
		binarnePorownania++;
		m = (l + r) / 2;
		binarneDzielenie++;
	}
	int indeksWyniku = m;
	l = 0;
	r = n;
	m = (l + r) / 2;
	int minimalneA = 0;
	int sekwencyjneDzielenie = 1;
	int sekwencyjnePorownania = 1;
	while(C[m] != c)
	{	
		sekwencyjnePorownania++;
		int iloscPorownan = sekwencyjnePorownania + indeksWyniku - l + 1;
		int a = ((iloscPorownan - binarnePorownania) / (binarneDzielenie - sekwencyjneDzielenie)) + 1;
		if(a > minimalneA)
			minimalneA = a;
		if(C[m] < c)
			l = m + 1;
		else
			r = m - 1;
		sekwencyjnePorownania++;
		m = (l + r) / 2;
		sekwencyjneDzielenie++;
	}
	fprintf(stdout, "%i", minimalneA * minimalneA);
	return 0;
}

Trzecie zadanie z ASD:

Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L – lewa krawędź, P – prawa krawędź) jakie pokonamy przechodząc w drzewie T ścieżkę od korzenia do wierzchołka x (przykłady poniżej).

Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T, korzeń drzewa T.

Wejście

Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący w sposób poprawny pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowego wiersza/linii (ASCII kod 10) opisujący pozycję wierzchołka w drzewie T i zawierający:

małą literę alfabetu nagielskiego (ASCII kod od 97 do 122) – etykieta wirzchołka,
znak odstępu/spacji (ASCII kod 32),
ciąg znaków L (ASCII kod 76) oraz R (ASCII kod 82) – ciąg skierowań krawędzi.
Liczba wierzchołków drzwa T ograniczona zawarta w przedziale [1,10^6]. Wysokość drzewa T ograniczona przez 2^6.

Wyjście

Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.

Złożoności i limity

Złożoność czasowa O(nh), złożoność pamięciowa O(n) bez uwzględnienia kosztów mechanizmu rekursji, gdzie n jest liczbą wierzchołków drzewa T a h jest jego wysokością. Fizyczny limit pamięci, bez uwzględnienia kosztu mechanizmu rekursji, zależny od rozmiaru danych wejściowych i ograniczony przez 10n B+1 KB.

Przykład 1

Wejście:
a LL
d
a R
s L

Wyjście:
asd
Przykład 2

Wejście:
s LR
o LRR
m RR
p LRLRL
k
w LRL
a LL
t L
h R
j LRLR

Wyjście:
pjwstk

Jedno z wielu możliwych rozwiązań:

#include<iostream>
using namespace std;

class Element
{
    public:
	char value;
	Element* left;
	Element* right;
	Element()
	{
		value = NULL;
		left = NULL;
		right = NULL;
	}
};

void showTree(Element* element)
{
	if(element->left)
		showTree(element->left);
	if(element->right)
		showTree(element->right);
	cout << element->value;
}

char isOneNode(Element* element)
{
	if(element->left && element->right)
		return 0;
	else if(element->left)
		return isOneNode(element->left);
	else if(element->right)
		return isOneNode(element->right);
	else
		return 1;
}

char getTheBest(Element* element)
{
	char r1 = 0;
	char r2 = 0;
	if(!element->left && !element->right)
	{
		return element->value - 70;
	}
	else
	{
		if(element->left)
		{
			r1 = getTheBest(element->left);
		}
		if(element->right)
		{
			r2 = getTheBest(element->right);
		}
	}
	if(r1 != 0 && r1 < 90)
	{
		delete element->left;
		element->left = NULL;
		r1 = r1 + 70;
	}
	if(r2 != 0 && r2 < 90)
	{
		delete element->right;
		element->right = NULL;
		r2 = r2 + 70;
	}
	if(r1 > r2)
	{
		delete element->right;
		element->right = NULL;
		return r1;
	}
	else if(r1 < r2)
	{
		delete element->left;
		element->left = NULL;
		return r2;
	}
	return r2;
}

int main()
{
	char lastChar;
	char tmpChar;
	Element* root = new Element();
	Element* currentNode = root;
	cin >> lastChar;
	while(cin >> tmpChar)
	{
		if(tmpChar == 'L')
		{
			if(currentNode->left == NULL)
			{
				currentNode->left = new Element();
			}
			currentNode = currentNode->left;
		}
		else if(tmpChar == 'R')
		{
			if(currentNode->right == NULL)
			{
				currentNode->right = new Element();
			}
			currentNode = currentNode->right;
		}
		else
		{
			currentNode->value = lastChar;
			lastChar = tmpChar;
			currentNode = root;
		}
	}
	currentNode->value = lastChar;
	while(!isOneNode(root))
	{
		cout << getTheBest(root);
	}
	showTree(root);
	return 0;
}

Drugie zadanie z ASD:

Rozważmy dowolny indeksowany ciąg liczb naturlanych C, dla którego definiujemy pojęcie wskaźnika aktualnej pozycji POS. Dalej wprowadzamy dwie operacje na elementach tego ciągu:

R() – usunięcie elementu c ciągu o indeksie POS+1, następnie przesunięcie wskaźnika POS o c elementów w prawo,
X() – wstawienie tuż po (pozycja POS+1) elemencie c ciągu o indeksie POS elementu o wartości c-1, następnie przesunięcie wskaźnika POS o c elementów w prawo.
Wyznacz postać ciagu wejściowego C po t-krotnym wykonaniu schematu operacji R() i X():

jeżeli elementu ciągu o indeksie POS jest liczbą:
parzystą, to wykonaj operację R(),
nieparzystą, to wykonaj operację X(),
przyjmując, że:

początkowo wskaźnik POS wskazuje na pierwszy element ciągu wejściowego (jeżeli taki istnieje),
jeżeli zachodzi taka konieczność przesuwanie wskaźnika POS w prawo odbywaja się w sposób cykliczny względem elementów ciągu C.
Wejście

Wierszy zawiera kolejno:

liczbę definiująca krotność t powtórzeń schematu operacji R() i X() zakończoną znakiem odstępu/spacji (ASCII kod 32),
elementy ciągu oddzielone znakiem odstępu/spacji i zakończone znakiem końca pliku (EOF).
Długość początkowa ciągu C zawarta w przedziale [0,10^6]. Liczba t powtórzeń schamatu operacji R() i X() ograniczona przez 10^6. Zakres przesunięcia wskaźnika POS w prawo określony przedziałem [0,10^9].

Wyjście

Wiersz zakończony znakiem nowego wiersza/linii (ASCII kod 10) zawierajacy ciąg liczb naturalnych będący rozwiązaniem postawionego problemu wypisany cyklicznie, jeżeli zachodzi taka konieczność, począwszy od elementu ciągu wynikowego znajdującego się na pozycji wskazywanej przez wskaźnik POS w kierunku w prawo. Elementy ciągu wynikowego oddzielone znakiem odstępu/spacji (ASCII kod 32).

Złożoności i limity

Złożoność czasowa O(tn), złożoność pamięciowa O(n), gdzie n jest długością początkową ciągu C, t krotnością powtórzeń schamatu operacji R() i X(). Fizyczny limit pamięci zależny od rozmiaru danych wejściowych i ograniczony przez 12(n+t) B + 1 KB.

Przykład 1

Wejście:
3 1 2 3
Wyjście:
0 0 3 1

Przykład 2

Wejście:
8 5 1 2 3
Wyjście:
2 2

A tutaj kodzik w C++:

#include <stdio.h>
#include <iostream>

struct C
{
  unsigned int c;
  C* next;
  C(unsigned int value)
  {
    c = value;
    next = NULL;
  }
};

int main()
{
  unsigned int rounds;
  fscanf(stdin, "%u", &rounds);
  if(!feof(stdin))
  {
    unsigned int elements = 0;
    unsigned int tmp;
    fscanf(stdin, "%u", &tmp);
    C* first = new C(tmp);
    elements++;
    C* current = first;
    while(std::cin >> tmp)
    {
      current->next = new C(tmp);
      current = current->next;
      elements++;
    }
    current->next = first;
    current = first;
    for(int i = 0; i < rounds; i++)
    {
      if(elements == 0)
        break;
      unsigned int value;
      if(current->c & 1)
      {
        value = current->c;
        C* newC = new C(value-1);
        newC->next = current->next;
        current->next = newC;
        elements++;
      }
      else
      {
        value = current->next->c;
        C* toDelete = current->next;
        current->next = toDelete->next;
        delete toDelete;
        elements--;
      }
      if(elements > 0)
      {
        value = value % elements;
        for(int ii = 0; ii < value; ii++)
        {
          current = current->next;
        }
      }
    }
    if(elements > 0)
    {
      first = current;
      fprintf(stdout, "%u", current->c);
      current = current->next;
      while(first != current)
      {
        fprintf(stdout, " %u", current->c);
        current = current->next;
      }
    }
  }
  fprintf(stdout, "\n");
  return 0;
}

Rozwiązanie na 100%. Treść:

Rozważmy rodzinę C ciągów rekurencyjnych C{n}, gdzie n jest pewną liczbą naturalną, których elementy zawarte są w zbiorze liczb naturalnych. Dalej i-ty element ciągu C{n} zapisujemy jako C{n}(i) i definiujemy rekurencyjnie w następujący sposób:

• n, dla i=0,
• C{n}(i-1)/2, dla i>0 oraz C{n}(i-1) będącego liczbą parzystą,
• 3C{n}(i-1)+1, dla i>0 oraz C{n}(i-1) będącego liczbą nieparzystą.

Na przykład dla n=7 ciąg C{7} ma postać:

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, …

Sprawdź, czy podany na wejściu ciąg liczba naturalnych jest prefiksem pewnego ciągu z rodziny C. Jeżeli odpowiedź jest twierdząca wypisz na wyjściu OK, w przeciwnym przypadku wypisz sufiks ciagu wejściowego, którego pierwszy element jest zarazem pierwszym elementem tego ciągu, ze względu na który ten że ciąg przstał być prefiksem pewnego ciagu z rodziny C (przykłady poniżej).

Wejście

Wiersz zawierający ciąg liczb naturlanych dodatniej długości i zakończony znakiem końca pliku (EOF). Długość ciągu ograniczona przez 10^9. Elementy ciągu oddzielone znakiem odstępu/spacji (ASCII kod 32) i zawarte w przedziale wartości [0,10^9].

Wyjście

Wiersz zawierajacy słowo OK jeżeli wejście spełnia kryteria założone w zadaniu. W przeciwnym przypadku wiersz zawierający stosowny sufiks ciągu wejściowego. Elementy ciągu oddzielone znakiem odstępu/spacji (ASCII kod 32).

Złożoności i limity

Złożoność czasowa O(n), złożoność pamięciowa O(1), gdzie n jest długością ciągu podanego na wejściu. Fizyczny limit pamięci niezależny od rozmiaru danych wejściowych i ograniczony przez 1 KB.

Przykład 1

Wejście:
64 32 16 8 4 2 1 4 2 1 4
Wyjście:
OK

Przykład 2

Wejście:
7 22 11 34 17 52 26 13 30 20 10 5 17 8 4 1
Wyjście:
30 20 10 5 17 8 4 1

Rozwiązanie w C:

#include 
int main()
{
    int current;
	int next;

	int validInput = 1;
	fscanf(stdin, "%i", &current);
	while(!feof(stdin))
	{
		fscanf(stdin, "%i", &next);
		if(current & 1)
		{
			if(current != (next-1)/3)
			{
				validInput = 0;
				break;
			}
		}
		else if(current != next*2)
		{
			validInput = 0;
			break;
		}
		current = next;
	}

	if(validInput == 1)
	{
		fprintf(stdout, "OK");
	}
	else
	{
		fprintf(stdout, "%i", next);
		while(!feof(stdin))
		{
			fscanf(stdin, "%i", &next);
			fprintf(stdout, " %i", next);
		}
	}
	return 0;
}

Nie było takie trudne co nie? 🙂

Gdyby ktoś nie pamiętał adresu do testowania kodu:
http://asd.spox.spoj.pl/

Najlepsze rozwiązanie to kod w C, używa najmniej pamięci i wykonuje się w 0.09 sec (wynik: 100%).

#include <stdio.h>
int main()
{
    unsigned int iloscDoWczytania;
    fscanf(stdin, "%u", &iloscDoWczytania);
    unsigned int podstawa;
    fscanf(stdin, "%u", &podstawa);
    unsigned int suma = 0;
    unsigned short int wczytany = 1;
    while(iloscDoWczytania-- > 0)
    {
        fscanf(stdin, "%hu", &wczytany);
        suma += wczytany;
    }
    unsigned int iloscZnakow = 1;
    if(podstawa == 0)
    {
        iloscZnakow = 0;
    }
    else if(podstawa == 1)
    {
        iloscZnakow = suma;
    }
    else
    {
        while(suma > podstawa)
        {
            iloscZnakow++;
            suma = suma / podstawa;
        }
    }
    fprintf(stdout, "%u", iloscZnakow);
    return 0;
}

Inne (o dziwo – jak w kolejnych zadaniach będzie coś z tablicami to raczej PHP nie ma szans na wykonanie obliczeń w wymaganym czasie) dobre rozwiązanie to użycie PHP, wykonuje się w 0.68 sec. (wynik: 100%):

<?PHP
$message = file_get_contents('php://stdin');
$d = explode(chr(0x20), $message);
$iloscDoWczytania = $d[0];
$podstawa = $d[1];
$suma = 0;
$idDoWczytania = 2;
while($iloscDoWczytania-- > 0)
{
    $suma += $d[$idDoWczytania++];
}
$iloscZnakow = 1;
if($podstawa == 0)
{
	$iloscZnakow = 0;
}
else if($podstawa == 1)
{
	$iloscZnakow = $suma;
}
else
{
	while($suma > $podstawa)
	{
		$iloscZnakow++;
		$suma = (int) ($suma / $podstawa);
	}
}
echo $iloscZnakow;

Dla osób co liczyły na pisanie w Javie mam niestety smutną wiadomość: Java jest za wolna! Ostatni test (w którym jest podane ponad 65000 parametrów/liczb) wykonuje się ponad 2 sekundy i nie zalicza ostatniego testu (wynik: 80% [4 z 5 testów]).

import java.util.Scanner;

public class Main
{
    public static void main(String[] argumenty)
	{
		Scanner in = new Scanner(System.in);
	    int iloscDoWczytania = in.nextInt();
	    int podstawa = in.nextInt();
	    int suma = 0;
	    while(iloscDoWczytania-- > 0)
	    {
	        suma += in.nextInt();
	    }
	    int iloscZnakow = 1;
	    if(podstawa == 0)
	    {
	        iloscZnakow = 0;
	    }
	    else if(podstawa == 1)
	    {
	        iloscZnakow = suma;
	    }
	    else
	    {
	        while(suma > podstawa)
	        {
	            iloscZnakow++;
	            suma = suma / podstawa;
	        }
	    }
	    System.out.print(iloscZnakow);
	}
}