feat(Week13): Add solutions to most exercises

24 files changed, 662 insertions, 0 deletions

diff --git a/Week13/Exercise01.cpp b/Week13/Exercise01.cpp
new file mode 100644
index 0000000..ed5797e
--- /dev/null
+++ b/Week13/Exercise01.cpp
@@ -0,0 +1,37 @@
+#include <iostream>
+
+void line(unsigned n) {
+	if (n == 0) {
+		std::cout << std::endl;
+	}
+	else {
+		std::cout << '+';
+		line(n - 1);
+	}
+}
+
+/* Два начина по които да имплементираме изкарването на "стълбите" */
+
+void stairs1(unsigned i, unsigned max) {
+	if (i <= max) {
+		line(i);
+		stairs1(i + 1, max);
+	}
+}
+
+void stairs2(unsigned n) {
+	if (n > 0) {
+		stairs2(n - 1);
+		line(n);
+	}
+}
+
+int main() {
+	unsigned n;
+	std::cin >> n;
+
+	// stairs1(1, n);
+	stairs2(n);
+
+	return 0;
+}
diff --git a/Week13/Exercise02.cpp b/Week13/Exercise02.cpp
new file mode 100644
index 0000000..e144e88
--- /dev/null
+++ b/Week13/Exercise02.cpp
@@ -0,0 +1,17 @@
+#include <iostream>
+
+unsigned fib(unsigned x) {
+	if (x <= 1)
+		return x;
+	else
+		return fib(x - 1) + fib(x - 2);
+}
+
+int main() {
+	unsigned n;
+	std::cin >> n;
+
+	std::cout << fib(n) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise03.cpp b/Week13/Exercise03.cpp
new file mode 100644
index 0000000..9dc4733
--- /dev/null
+++ b/Week13/Exercise03.cpp
@@ -0,0 +1,17 @@
+#include <iostream>
+
+unsigned digitSum(unsigned x) {
+	if (x == 0)
+		return 0;
+	else
+		return x % 10 + digitSum(x / 10);
+}
+
+int main() {
+	unsigned num;
+	std::cin >> num;
+
+	std::cout << digitSum(num) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise04.cpp b/Week13/Exercise04.cpp
new file mode 100644
index 0000000..0fdc462
--- /dev/null
+++ b/Week13/Exercise04.cpp
@@ -0,0 +1,38 @@
+#include <iostream>
+#include <cstring>
+
+/* Два начина по които да имплементираме обръщането на низа */
+
+void revText1(unsigned left, unsigned right, char* str) {
+	if (left < right) {
+		char tmp = str[left];
+		str[left] = str[right];
+		str[right] = tmp;
+
+		revText1(left + 1, right - 1, str);
+	}
+}
+
+void revText2(char* left, char* right) {
+	if (left < right) {
+		char tmp = *left;
+		*left = *right;
+		*right = tmp;
+
+		revText2(left + 1, right - 1);
+	}
+}
+
+int main() {
+	const unsigned MAX_LEN = 1024;
+
+	char line[MAX_LEN];
+	std::cin.getline(line, MAX_LEN);
+
+	// revText1(0, strlen(line) - 1, line);
+	revText2(line, line + strlen(line) - 1);
+
+	std::cout << line << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise05.cpp b/Week13/Exercise05.cpp
new file mode 100644
index 0000000..7b409d5
--- /dev/null
+++ b/Week13/Exercise05.cpp
@@ -0,0 +1,29 @@
+#include <iostream>
+
+void line(unsigned n) {
+	if (n == 0) {
+		std::cout << std::endl;
+	}
+	else {
+		std::cout << '+';
+		line(n - 1);
+	}
+}
+
+void hill(unsigned i, unsigned max) {
+	if (i <= max) {
+		line(i);
+		hill(i + 1, max);
+	}
+	if (i < max)
+		line(i);
+}
+
+int main() {
+	unsigned n;
+	std::cin >> n;
+
+	hill(1, n);
+
+	return 0;
+}
diff --git a/Week13/Exercise06.cpp b/Week13/Exercise06.cpp
new file mode 100644
index 0000000..bf455d5
--- /dev/null
+++ b/Week13/Exercise06.cpp
@@ -0,0 +1,24 @@
+#include <iostream>
+
+void sumavg(int a, int b, unsigned count, int& sum, double& avg) {
+	if (a > b) {
+		avg = (double)sum / count;
+	}
+	else {
+		sum += a;
+		sumavg(a + 1, b, count + 1, sum, avg);
+	}
+}
+
+int main() {
+	int a, b;
+	std::cin >> a >> b;
+
+	int sum = 0;
+	double avg = 0.0;
+	sumavg(a, b, 0, sum, avg);
+
+	std::cout << sum << ' ' << avg << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise07.cpp b/Week13/Exercise07.cpp
new file mode 100644
index 0000000..f2aa288
--- /dev/null
+++ b/Week13/Exercise07.cpp
@@ -0,0 +1,26 @@
+#include <iostream>
+
+const unsigned MAX_BITS = 32;
+
+void printBits(unsigned bits, unsigned i, char buffer[MAX_BITS]) {
+	if (bits == 0) {
+		buffer[i] = '\0';
+		std::cout << buffer << std::endl;
+	}
+	else {
+		buffer[i] = '0';
+		printBits(bits - 1, i + 1, buffer);
+		buffer[i] = '1';
+		printBits(bits - 1, i + 1, buffer);
+	}
+}
+
+int main() {
+	unsigned bits;
+	std::cin >> bits;
+
+	char buffer[MAX_BITS];
+	printBits(bits, 0, buffer);
+
+	return 0;
+}
diff --git a/Week13/Exercise08.cpp b/Week13/Exercise08.cpp
new file mode 100644
index 0000000..850bd12
--- /dev/null
+++ b/Week13/Exercise08.cpp
@@ -0,0 +1,29 @@
+#include <iostream>
+
+unsigned fib(unsigned n) {
+	if (n <= 1)
+		return n;
+	else
+		return fib(n - 1) + fib(n - 2);
+}
+
+void intertwinedFib(unsigned i, unsigned max) {
+	if (i > max) {
+		std::cout << std::endl;
+	}
+	else {
+		if (i > 0)
+			std::cout << ' ';
+		std::cout << fib(i) << ' ' << fib(max - i);
+		intertwinedFib(i + 1, max);
+	}
+}
+
+int main() {
+	unsigned n;
+	std::cin >> n;
+
+	intertwinedFib(0, n);
+
+	return 0;
+}
diff --git a/Week13/Exercise09.cpp b/Week13/Exercise09.cpp
new file mode 100644
index 0000000..7b1f8fc
--- /dev/null
+++ b/Week13/Exercise09.cpp
@@ -0,0 +1,49 @@
+#include <iostream>
+
+/* Едно ниво на рекурсия обработва едно ниво на скоби.
+ *
+ * Тоест, при "(())", първата и последнта скоба са първото
+ * ниво на скоби, "()" в центъра са второто ниво.
+ * В "()()()" имаме три чивта скоби на едно ниво.
+ *
+ * Искаме на текущото ниво, за всяка отваряща скоба да има затваряща,
+ * и искаме това да е изпълнено и за всяко вътрешно/долно ниво.
+ *
+ * Има два начина това да не е изпълнено: ако липсва отваряща скоба
+ * или ако липсва затваряща.
+ * Съответно, или няма да влезем в цикъла или ще излезем рано от него.
+ * Което означава, че няма да инкрементираме str.
+ *
+ * Тоест, str е един вид указателя към последната буква, преди
+ * която скобите са балансирани.
+ */
+bool balanced(const char*& str) {
+	while (*str == '(') {
+		str += 1;
+
+		balanced(str);
+
+		if (*str != ')')
+			return false;
+
+		str += 1;
+	}
+
+	return *str == '\0';
+}
+
+int main() {
+	const unsigned MAX_LEN = 1024;
+
+	char line[MAX_LEN];
+	std::cin.getline(line, MAX_LEN);
+
+	const char* ptr = line;
+
+	if (balanced(ptr))
+		std::cout << "Balanced" << std::endl;
+	else
+		std::cout << "Not balanced" << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise10.cpp b/Week13/Exercise10.cpp
new file mode 100644
index 0000000..5d71e4f
--- /dev/null
+++ b/Week13/Exercise10.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+
+double sum(double totalsum, const double* elems, unsigned size) {
+	if (size == 0)
+		return totalsum;
+	else
+		return sum(totalsum + *elems, elems + 1, size - 1);
+}
+
+int main() {
+	unsigned size;
+	std::cin >> size;
+
+	double* arr = new double[size];
+	for (unsigned i = 0; i < size; ++i)
+		std::cin >> arr[i];
+
+	std::cout << sum(0.0, arr, size) << std::endl;
+
+	free(arr);
+
+	return 0;
+}
diff --git a/Week13/Exercise11.cpp b/Week13/Exercise11.cpp
new file mode 100644
index 0000000..2f29d38
--- /dev/null
+++ b/Week13/Exercise11.cpp
@@ -0,0 +1,26 @@
+#include <iostream>
+
+void threeChildren(unsigned a, unsigned b, unsigned c, unsigned prod) {
+	if (a * b * c == prod) {
+		std::cout << a << ' ' << b << ' ' << c << std::endl;
+		return;
+	}
+
+	if (b + 1 < c - 1)
+		threeChildren(a, b + 1, c - 1, prod);
+	if (b + 1 < c - 2)
+		threeChildren(a + 1, b + 1, c - 2, prod);
+}
+
+void threeChildren(unsigned sum, unsigned prod) {
+	threeChildren(1, 1, sum - 2, prod);
+}
+
+int main() {
+	unsigned sum, prod;
+	std::cin >> sum >> prod;
+
+	threeChildren(sum, prod);
+
+	return 0;
+}
diff --git a/Week13/Exercise12.cpp b/Week13/Exercise12.cpp
new file mode 100644
index 0000000..107281b
--- /dev/null
+++ b/Week13/Exercise12.cpp
@@ -0,0 +1,34 @@
+#include <iostream>
+
+unsigned max(unsigned a, unsigned b) {
+	return a > b ? a : b;
+}
+
+unsigned longestIncreasing(int* nums, unsigned size, unsigned current) {
+	if (size <= 1)
+		return current + size;
+
+	if (nums[0] < nums[1])
+		return longestIncreasing(nums + 1, size - 1, current + 1);
+	else
+		return max(current + 1, longestIncreasing(nums + 1, size - 1, 0));
+}
+
+unsigned longestIncreasing(int* nums, unsigned size) {
+	return longestIncreasing(nums, size, 0);
+}
+
+int main() {
+	unsigned N;
+	std::cin >> N;
+
+	int* nums = new int[N];
+	for (unsigned i = 0; i < N; ++i)
+		std::cin >> nums[i];
+
+	std::cout << longestIncreasing(nums, N) << std::endl;
+
+	delete[] nums;
+
+	return 0;
+}
diff --git a/Week13/Exercise13.cpp b/Week13/Exercise13.cpp
new file mode 100644
index 0000000..5f9fd40
--- /dev/null
+++ b/Week13/Exercise13.cpp
@@ -0,0 +1,90 @@
+#include <iostream>
+
+const unsigned BOARD_SIZE = 4;
+
+bool inrange(unsigned lower, unsigned x, unsigned upper) {
+	return lower <= x && x <= upper;
+}
+
+bool isSolved(int board[BOARD_SIZE][BOARD_SIZE]) {
+	unsigned firstSum = 0;
+	for (unsigned row = 0; row < BOARD_SIZE; ++row) {
+		unsigned rowSum = 0;
+
+		for (unsigned col = 0; col < BOARD_SIZE; ++col) {
+			// Валидно решение
+			if (board[row][col] != 0 && board[row][col] != 1)
+				return false;
+
+			if (row == 0)
+				firstSum += board[row][col];
+			rowSum += board[row][col];
+
+			// Последователност на 0ли и 1ци в реда
+			if (inrange(1, col, BOARD_SIZE - 2) &&
+				!inrange(1, board[row][col - 1] + board[row][col] + board[row][col + 1], 2))
+				return false;
+
+			// Последователност на 0ли и 1ци в колоната
+			if (inrange(1, row, BOARD_SIZE - 2) &&
+				!inrange(1, board[row - 1][col] + board[row][col] + board[row + 1][col], 2))
+				return false;
+		}
+
+		// Еднакъв брой нули и единици на всеки ред
+		if (firstSum != rowSum)
+			return false;
+	}
+
+	for (unsigned col = 0; col < BOARD_SIZE; ++col) {
+		unsigned colSum = 0;
+
+		for (unsigned row = 0; row < BOARD_SIZE; ++row)
+			colSum += board[row][col];
+
+		// Еднакъв брой нули и единици на всяка колона (и това еднакво с всеки ред)
+		if (firstSum != colSum)
+			return false;
+	}
+
+	return true;
+}
+
+bool solve(unsigned index, int board[BOARD_SIZE][BOARD_SIZE]) {
+	if (index == BOARD_SIZE * BOARD_SIZE)
+		return isSolved(board);
+
+	int& curr = board[index / BOARD_SIZE][index % BOARD_SIZE];
+
+	if (curr != -1)
+		return solve(index + 1, board);
+
+	curr = 0;
+	if (solve(index + 1, board))
+		return true;
+
+	curr = 1;
+	if (solve(index + 1, board))
+		return true;
+
+	curr = -1;
+	return false;
+}
+
+int main() {
+	int board[BOARD_SIZE][BOARD_SIZE];
+
+	for (unsigned row = 0; row < BOARD_SIZE; ++row)
+		for (unsigned col = 0; col < BOARD_SIZE; ++col)
+			std::cin >> board[row][col];
+
+	solve(0, board);
+
+	for (unsigned row = 0; row < BOARD_SIZE; ++row) {
+		for (unsigned col = 0; col < BOARD_SIZE; ++col)
+			std::cout << board[row][col] << ' ';
+		std::cout << std::endl;
+	}
+
+	return 0;
+}
diff --git a/Week13/Exercise14.cpp b/Week13/Exercise14.cpp
new file mode 100644
index 0000000..5a7f5dd
--- /dev/null
+++ b/Week13/Exercise14.cpp
@@ -0,0 +1,26 @@
+#include <iostream>
+
+const unsigned LEHMER_a = 16807;
+const unsigned LEHMER_m = ((unsigned long)1 << 31) - 1;
+
+void lehmerPrint(unsigned i, unsigned N, unsigned Xk) {
+	if (i >= N) {
+		std::cout << Xk << std::endl;
+		return;
+	}
+
+	if (i > 0)
+		std::cout << Xk << ' ';
+
+	lehmerPrint(i + 1, N, (LEHMER_a * Xk) % LEHMER_m);
+}
+
+int main()
+{
+	unsigned seed, N;
+	std::cin >> seed >> N;
+
+	lehmerPrint(0, N, seed);
+
+	return 0;
+}
diff --git a/Week13/Exercise15.cpp b/Week13/Exercise15.cpp
new file mode 100644
index 0000000..17f75f6
--- /dev/null
+++ b/Week13/Exercise15.cpp
@@ -0,0 +1,19 @@
+#include <iostream>
+#include <cmath>
+
+double eccentricAnomaly(double M, double e, unsigned depth) {
+	if (depth == 0)
+		return M;
+	return M + e * sin(eccentricAnomaly(M, e, depth - 1));
+}
+
+int main()
+{
+	double M, e;
+	unsigned depth;
+	std::cin >> M >> e >> depth;
+
+	std::cout << eccentricAnomaly(M, e, depth) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise16.cpp b/Week13/Exercise16.cpp
new file mode 100644
index 0000000..66f8e11
--- /dev/null
+++ b/Week13/Exercise16.cpp
@@ -0,0 +1,19 @@
+#include <iostream>
+
+unsigned gcd(unsigned a, unsigned b) {
+	if (a == b)
+		return a;
+	else if (a < b)
+		return gcd(b, a);
+	else
+		return gcd(a - b, b);
+}
+
+int main() {
+	unsigned a, b;
+	std::cin >> a >> b;
+
+	std::cout << gcd(a, b) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise17.cpp b/Week13/Exercise17.cpp
new file mode 100644
index 0000000..952143f
--- /dev/null
+++ b/Week13/Exercise17.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+#include <cstring>
+
+bool isPalindrome(unsigned left, unsigned right, const char* str) {
+	if (left >= right)
+		return true;
+	else if (str[left] != str[right])
+		return false;
+	else
+		return isPalindrome(left + 1, right - 1, str);
+}
+
+int main() {
+	const unsigned LINE_LEN = 1024;
+
+	char line[LINE_LEN];
+	std::cin.getline(line, LINE_LEN);
+
+	if (isPalindrome(0, strlen(line) - 1, line))
+		std::cout << "Is a palindrome" << std::endl;
+	else
+		std::cout << "Not a palindrome" << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise18.cpp b/Week13/Exercise18.cpp
new file mode 100644
index 0000000..1e55af5
--- /dev/null
+++ b/Week13/Exercise18.cpp
@@ -0,0 +1,17 @@
+#include <iostream>
+
+unsigned digitOccur(unsigned num, unsigned digit) {
+	if (num == 0)
+		return 0;
+	else
+		return (num % 10 == digit) + digitOccur(num / 10, digit);
+}
+
+int main() {
+	unsigned num, digit;
+	std::cin >> num >> digit;
+
+	std::cout << digitOccur(num, digit) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise19.cpp b/Week13/Exercise19.cpp
new file mode 100644
index 0000000..a0d5ace
--- /dev/null
+++ b/Week13/Exercise19.cpp
@@ -0,0 +1,16 @@
+#include <iostream>
+
+unsigned binom(unsigned n, unsigned k) {
+	if (k == 0 || n == k)
+		return 1;
+	return binom(n - 1, k - 1) + binom(n - 1, k);
+}
+
+int main() {
+	unsigned n, k;
+	std::cin >> n >> k;
+
+	std::cout << binom(n, k) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise21.cpp b/Week13/Exercise21.cpp
new file mode 100644
index 0000000..280b9fa
--- /dev/null
+++ b/Week13/Exercise21.cpp
@@ -0,0 +1,32 @@
+#include <iostream>
+#include <cstring>
+
+unsigned min(unsigned a, unsigned b, unsigned c) {
+	if (a < b)
+		return a < c ? a : c;
+	return b < c ? b : c;
+}
+
+unsigned lev(const char* a, const char* b) {
+	if (*b == '\0')
+		return strlen(a);
+	else if (*a == '\0')
+		return strlen(b);
+	else if (*a == *b)
+		return lev(a + 1, b + 1);
+	else
+		return 1 + min(lev(a, b + 1), lev(a + 1, b), lev(a + 1, b + 1));
+}
+
+int main()
+{
+	const unsigned MAX_LEN = 1024;
+	char line1[MAX_LEN], line2[MAX_LEN];
+
+	std::cin.getline(line1, MAX_LEN);
+	std::cin.getline(line2, MAX_LEN);
+
+	std::cout << lev(line1, line2) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise22.cpp b/Week13/Exercise22.cpp
new file mode 100644
index 0000000..e27d97b
--- /dev/null
+++ b/Week13/Exercise22.cpp
@@ -0,0 +1,20 @@
+#include <iostream>
+#include <cmath>
+
+double agm(double an, double gn, unsigned i) {
+	if (i == 0)
+		return (an + gn) / 2.0;
+	else
+		return agm((an + gn) / 2.0, sqrt(an * gn), i - 1);
+}
+
+int main()
+{
+	double a, b;
+	unsigned n;
+	std::cin >> a >> b >> n;
+
+	std::cout << agm(a, b, n) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/Exercise23.cpp b/Week13/Exercise23.cpp
new file mode 100644
index 0000000..c37d243
--- /dev/null
+++ b/Week13/Exercise23.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+
+int max(int maxval, const int* elems, unsigned size) {
+	if (size == 0)
+		return maxval;
+	else
+		return max(maxval > *elems ? maxval : *elems, elems + 1, size - 1);
+}
+
+int main() {
+	unsigned size;
+	std::cin >> size;
+
+	int* arr = new int[size];
+	for (unsigned i = 0; i < size; ++i)
+		std::cin >> arr[i];
+
+	std::cout << max(*arr, arr, size) << std::endl;
+
+	free(arr);
+
+	return 0;
+}
diff --git a/Week13/Exercise24.cpp b/Week13/Exercise24.cpp
new file mode 100644
index 0000000..892ed3b
--- /dev/null
+++ b/Week13/Exercise24.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+
+double ex(double x, unsigned i, unsigned n) {
+	if (i == 0)
+		return 1 + x / ex(x, i + 1, n);
+	else if (i == 1)
+		return 1 - x / ex(x, i + 1, n);
+	else if (i == n)
+		return i + x;
+	else
+		return i + x - i * x / ex(x, i + 1, n);
+}
+
+int main()
+{
+	double x;
+	unsigned n;
+	std::cin >> x >> n;
+
+	std::cout << ex(x, 0, n) << std::endl;
+
+	return 0;
+}
diff --git a/Week13/README.md b/Week13/README.md
new file mode 100644
index 0000000..89a899c
--- /dev/null
+++ b/Week13/README.md
@@ -0,0 +1,3 @@
+# Задачи
+
+<https://syndamia.com/teaching/upp-2025/week13/>