[w5] Added solutions

4 files changed, 240 insertions, 0 deletions

diff --git a/week05/ex1.cpp b/week05/ex1.cpp
new file mode 100644
index 0000000..66a55af
--- /dev/null
+++ b/week05/ex1.cpp
@@ -0,0 +1,13 @@
+#include <iostream>
+
+void pointSum(double x1, double y1, double x2, double y2, double *x, double *y) {
+	*x = x1 + x2;
+	*y = y1 + y2;
+}
+
+int main() {
+	double x1, y1, x2, y2, sumX, sumY;
+	std::cin >> x1 >> y1 >> x2 >> y2;
+	pointSum(x1, y1, x2, y2, &sumX, &sumY);
+	std::cout << sumX << " " << sumY << std::endl;
+}
diff --git a/week05/ex2.cpp b/week05/ex2.cpp
new file mode 100644
index 0000000..ad81345
--- /dev/null
+++ b/week05/ex2.cpp
@@ -0,0 +1,123 @@
+#include <iostream>
+
+const size_t NUM_W = 30;
+
+/* Помощни, за удобство */
+
+void readNum(int num[NUM_W]) {
+	for (size_t i = 0; i < NUM_W; i++) {
+		std::cin >> num[i];
+	}
+}
+
+void printNum(int num[NUM_W]) {
+	bool pastLeadingZeroes = false;
+	for (size_t i = 0; i < NUM_W; i++) {
+		if ((!pastLeadingZeroes && num[i] != 0) || i == NUM_W - 1) {
+			pastLeadingZeroes = true;
+		}
+		if (pastLeadingZeroes) {
+			std::cout << num[i];
+		}
+	}
+	std::cout << std::endl;
+}
+
+/* Логика от задачата */
+
+void sum(int num1[NUM_W], int num2[NUM_W], int onum[NUM_W]) {
+	/* Не забравяйте, че ако е въведено числото 9000...0358, тогава
+	 * в нашия масив ще сме запазили цифрите в същата последователност,
+	 * тоест най-лявата стойност е 9, тази в дясно е 0 и так. нат.
+	 *
+	 * Обаче, най-лявата стойност в масива е на индекс 0, докато ние
+	 * искаме да сумираме цифри от дясно наляво, тоест въртим в обратен ред цикъла.
+	 *
+	 * Друг проблем - size_t е unsigned, тоест не можем да направим условието да е
+	 * i >= 0, защото когато направим i-- при i=0, ще получим underflow и числото ще
+	 * стане най-голямото възможно за size_t и забиваме в безкраен цикъл.
+	 * Затова правим друго - нека запазим същата идея и 0 да означава край на цикъла.
+	 * Тогава нашето i ще бъде между 30 и 0, като когато е между 30 и 1 индексираме в
+	 * масива, и затова правим i-1, защото при i=1 искаме най-левия елемент в масива.
+	 */
+	for (size_t i = NUM_W; i > 0; i--) {
+		onum[i-1] += num1[i-1] + num2[i-1];
+
+		/* Логика за преливане:
+		 * Ако имаме ... 0 9 + ... 0 1, трябва да получим ... 1 0
+		 * Тоест, ако сумата на i-тите цифри е >= 10, значи преливаме в цифрата в ляво.
+		 * Колко най-много може да бъде тази сума? Еми, една цифра може да е максимум 9,
+		 * така че сумата на две цифри може да е максимум 9+9=18. 
+		 *
+		 * Следователно, ако имаме примерно сума 18, искаме i-тата цифра да бъде 8 и
+		 * цифрата в ляво от нея да бъде 1.
+		 * Лявата винаги я правим 1, няма какво друго да бъде, а i-тата става втората
+		 * цифра на 18, тоест 8. Това го получаваме с % 10
+		 */
+		if (onum[i-1] >= 10 && i > 1) {
+			onum[i-2] = 1;
+			onum[i-1] %= 10;
+		}
+	}
+
+	/* Преливане при най-лявата цифра:
+	 * Какво става ако най-лявата цифра е (примерно) 18?
+	 * В нашия цикъл няма да я преливаме, защото няма друга лява цифра, в която да прелее.
+	 * Обаче не може да я оставим да е > 9
+	 *
+	 * Компоромис - пак правим преливането, обаче никъде не слагаме прелялата 1ца.
+	 * Тоест, нашата сума ще съдържа най-десните 30 цифри от "истинската" сума.
+	 */
+	if (onum[0] >= 10) {
+		onum[0] %= 10;
+	}
+}
+
+void sub(int num1[NUM_W], int num2[NUM_W], int onum[NUM_W]) {
+	/* Отновно индексиране погледни в sum функцията
+	 */
+	for (size_t i = NUM_W; i > 0; i--) {
+		onum[i-1] += num1[i-1] - num2[i-1];
+
+		/* Логика при underflow:
+		 * Какво става, когато трябва да вземем "на ум", тоест примерно при
+		 * ... 1 0 - ... 0 5?
+		 * Ако се намираме на най-дясната цифра, тогава имаме 0-5=-5
+		 * За вземане на ум искаме от лявата цифра да извадим 1ца и сегашната да бъде
+		 * 10-5=5 вместо 0-5=-5.
+		 */
+		if (onum[i-1] < 0 && i > 1) {
+			onum[i-2] = -1;
+			onum[i-1] += 10;
+		}
+	}
+
+	/* Underflow на най-лявата цифра:
+	 * Какво става ако най-лявата цифра също е в underflow, примерно при 0 ... 0 0 - 0 ... 0 1?
+	 *
+	 * Както при сумата, предстаявме си, че сме взели от някъде единица от лявата цифра, затова
+	 * оправяме сегашната с това in mind.
+	 * Така отново, ние пазим най-десните 30 цифри от истинската разлика, които са коректни.
+	 */
+	if (onum[0] < 0) {
+		onum[0] += 10;
+	}
+}
+
+int main() {
+	int num1[NUM_W] = { 0 }, num2[NUM_W] = { 0 }, res[NUM_W] = { 0 };
+
+	readNum(num1);
+	readNum(num2);
+
+	char op;
+	std::cin >> op;
+	if (op == '+') {
+		sum(num1, num2, res);
+	}
+	else if (op == '-') {
+		sub(num1, num2, res);
+	}
+
+	printNum(res);
+}
diff --git a/week05/ex3.cpp b/week05/ex3.cpp
new file mode 100644
index 0000000..81aafa1
--- /dev/null
+++ b/week05/ex3.cpp
@@ -0,0 +1,71 @@
+#include <iostream>
+
+int max(int a, int b) {
+	return (a > b) ? a : b;
+}
+
+void moveBack(int arr[], size_t size, size_t start, size_t moveBy) {
+	for (size_t i = start; i < size - moveBy; i++) {
+		arr[i] = arr[i + moveBy];
+	}
+}
+
+size_t repeatedChars(int arr[], size_t size, size_t start) {
+	size_t count = 0;
+	int ref = arr[start];
+	while (start < size && arr[start] == ref) {
+		count++;
+		start++;
+	}
+	return count;
+}
+
+int main() {
+	// Вход
+	size_t N;
+	std::cin >> N;
+
+	int nums[40];
+	for (size_t i = 0; i < N; i++) {
+		std::cin >> nums[i];
+	}
+
+	// Премахване
+	/* Логика:
+	 * Движим се от ляво на дясно през масива. На всяка позиция поглеждаме колко
+	 * пъти последователно се повтаря текущата цифра, тоест ако сме на индекс 0
+	 * и имаме стойности "8 8 8 1 2 8", тогава текущата цифра е 8 и тя се повтаря 3 пъти
+	 * последователно.
+	 *
+	 * По условие, ако повтарянето е поне 3 пъти, тогава трябва да "премахнем" цифрите.
+	 * Това как става? Еми, с презаписване, изместваме всички цифри назад и намаляваме
+	 * използваната дължина на масива.
+	 * Тоест, ако имахме масив със стойности { 8, 8, 8, 1, 2, 8, 6 }, и искаме да премахнем първите
+	 * три 8ци, първо ги презаписваме с цифрите след тях, масива става { 1, 2, 8, 6, 2, 8, 6 } и сега
+	 * последните три цифри са старите стойности, които не искаме да пипаме, затова намаляме и N.
+	 *
+	 * Обаче, след едно премахване може да се появи второ ново, трябва да върнем индекса назад, но с колко?
+	 * Да погледнем примери:
+	 * 1 1 1 2 2 2 1
+	 * По условие първо премахваме първата 3ка 1ци, после 2ките, тоест в масива остава "1", нямаме месетене назад
+	 * 1 1 2 2 2 1
+	 * Първо премахваме 2ките, имаме "1 1 1", премахваме тях, остава "". Тоест, трябва да преместим назад с 2 позиции,
+	 * за да се озовем в първата от 3те 1ци.
+	 * 1 2 2 2 1 1
+	 * Аналогично на предходния пример, обаче трябва да се върнем назад с 1 позиция, понеже удряме началото на масива.
+	 */
+	for (size_t i = 0; i < N; i++) {
+		size_t rep = repeatedChars(nums, N, i);
+		if (rep >= 3) {
+			moveBack(nums, N, i, rep);
+			i = max(i - 3, -1);
+			N -= rep;
+		}
+	}
+
+	// Изход
+	for (size_t i = 0; i < N; i++) {
+		std::cout << nums[i] << " ";
+	}
+	std::cout << std::endl;
+}
diff --git a/week05/ex4.cpp b/week05/ex4.cpp
new file mode 100644
index 0000000..2e77c9d
--- /dev/null
+++ b/week05/ex4.cpp
@@ -0,0 +1,33 @@
+#include <iostream>
+
+int main() {
+	size_t N, nums[30];
+	std::cin >> N;
+	for (size_t i = 0; i < N; i++) {
+		std::cin >> nums[i];
+	}
+
+	size_t maxJumpsIndex = 0, maxJumpsCount = 0;
+	bool visited[30] = { false };
+
+	for (size_t start = 0; start < N; start++) {
+		size_t current = start, jumpsCount = 0;
+
+		while (!visited[current]) {
+			visited[current] = true;
+			current = nums[current];
+			jumpsCount++;
+		}
+
+		if (jumpsCount > maxJumpsCount) {
+			maxJumpsCount = jumpsCount;
+			maxJumpsIndex = start;
+		}
+
+		for (size_t j = 0; j < N; j++) {
+			visited[j] = false;
+		}
+	}
+
+	std::cout << maxJumpsIndex << " " << maxJumpsCount << std::endl;
+}