path: root / Year 1 / Programming introduction / Practice-15.11.21.cpp

#include <iostream>
#include <cmath>

using namespace std;

/* Exercises:
 */

// Задача първа:
// От клавиатурата се въвеждат n цели числа (1 ≤ n ≤ 20),
// всяко от които е между 1 и 50. Да се напише програма, която намира сбора и
// произведението им.

void ex1() {
	const int MAX_NUMS = 20;

	int n;
	cin >> n;

	// Get input
	int nums[MAX_NUMS] = { 0 };
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	// Calculate sum and multiples
	int sum = 0, mult = 1;
	for (int i = 0; i < n; i++) {
		sum += nums[i];
		mult *= nums[i];
	}

	cout << sum << " " << mult << endl;
}

// Задача втора:
// Въвеждат се n реални числа (n ≤ 1000).
// Да се изкарат в обратен ред с помощта на помощен масив.
// Пример:
// Вход:
// 4
// 1 2 3 4
// Изход:
// 4 3 2 1

void ex2() {
	const int MAX_NUMS = 1000;

	int n;
	cin >> n;

	// Get input
	int nums[MAX_NUMS] = { 0 };
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	// Print numbers in reverse
	for (int i = n - 1; i >= 0; i--)
		cout << nums[i] << " ";
	cout << endl;
}

// Задача трета:
// Въвеждат се n реални числа. Да се намерят и изкарат в конзолата най-малко и
// най-голямото от тях.

void ex3() {
	const int MAX_INT = 2147483647, MIN_INT = -MAX_INT + 1, LINE_BUFFER_SIZE = 10000;

	int n;
	cin >> n;

	// Get input
	int nums[LINE_BUFFER_SIZE] = { 0 };
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	// Find min and max numbers
	int max = MIN_INT, min = MAX_INT;
	for (int i = 0; i < n; i++) {
		if (nums[i] < min) min = nums[i];
		if (nums[i] > max) max = nums[i];
	}

	cout << min << " " << max << endl;
}

// Задача четвърта:
// Въвеждат се n цели числа. Да се отпечата да конзолата броят на простите числа,
// както и самите те.

bool isPrime(int n) {
	int root = sqrt(n);
	for (int i = 2; i <= root; i++)
		if (n % i == 0) return false;
	return true;
}

void ex4() {
	const int LINE_BUFFER_SIZE = 10000;

	int n;
	cin >> n;

	// Get input
	int nums[LINE_BUFFER_SIZE] = { 0 };
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	// Save primes to array and count them
	int primes[LINE_BUFFER_SIZE] = { 0 }, primeI = 0;
	for (int i = 0; i < n; i++) {
		if (isPrime(nums[i]))
			primes[primeI++] = nums[i];
	}

	// Print prime count and primes themselves
	cout << primeI << endl;
	for (int i = 0; i < primeI; i++)
		cout << primes[i] << " ";
	cout << endl;
}

// Задача пета*:
// От стандартния вход се четат две четири битови числа и извежда сбора им.
// Пример:
// Вход:
// 1000 0011
// Изход:
// 1011

void ex5() {
	const int MAX_NUM_LEN = 4;

	int a, b;
	cin >> a >> b;

	int res[MAX_NUM_LEN] = { 0 };
	for (int i = MAX_NUM_LEN - 1; i >= 0; i--) {
		int sum = a % 10 + b % 10 + res[i];

		if (sum >= 2) { // Overflow
			res[i] = sum % 2;
			res[i - 1] = sum / 2;
		} else
			res[i] = sum;

		a /= 10;
		b /= 10;
	}

	for (int i = 0; i < MAX_NUM_LEN; i++)
		cout << res[i];
	cout << endl;
}

// Задача шеста*:
// Имаме масив с дължина 2n + 1. В него имаме n двойки от типа (k, k) и едно
// единствено число, което не образува такава двойка. Напишете функция, която
// намира това число.
// Пример:
// Вход:
// { 1, 2, 3, 4, 5, 1, 3, 2, 4 }
// Изход:
// 5

int findOutsider(int nums[], int numCount) {
	for (int i = 0, j = 0; i < numCount - 1; i++) {
		for (j = i + 1; j < numCount; j++)
			if (nums[i] == nums[j]) break;

		if (j == numCount) return nums[i];
	}
	return -1; // required default case
}

void ex6() {
	const int LINE_BUFFER_SIZE = 10000;

	int n;
	cin >> n;

	// Get input
	int nums[LINE_BUFFER_SIZE] = { 0 }, numCount = 2 * n + 1;
	for (int i = 0; i < numCount; i++)
		cin >> nums[i];

	cout << findOutsider(nums, numCount) << endl;
}

// Задача седма
// Въвеждат се n на брой цели числа, както и даден затворен интервал от числа,
// зададен с двата си края.
// Да се провери дали всички числа от дадения интервал се срещат измежду
// въведените n.
// Пример:
// Вход:
// 10 -> брой на числата
// 4 12 -> интервал
// 5 8 4 1 9 6 7 11 10 12
// Изход:
// true

bool allInInterval(int nums[], int numLen, int a, int b) {
	for (int i = 0; i < numLen; i++) {
		if (nums[i] < a || nums[i] > b)
			return false;
	}
	return true;
}

void ex7() {
	const int LINE_BUFFER_SIZE = 10000;

	int n, a, b;
	cin >> n >> a >> b;

	// Get input
	int nums[LINE_BUFFER_SIZE] = { 0 };
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	cout << ((allInInterval(nums, n, a, b)) ? "true" : "false") << endl;
}

// Bonus: 1-D Game of Life
// В тази задача трябва да се имплементира наша версия на популярната игра Game
// of Life. В нашата версия използваме едномерен масив като еволюирането става по
// следния начин:
// • Клетка Х има 4 съседни клетки YYXYY.
// • Жива клетка се представя чрез 1 а мъртва чрез 0.
// • Мъртва клетка оживява ако 2 или 3 съседа са живи.
// • Жива клетка оцелява ако 2 или 4 клетки са живи. В противен случай умира.
// • Имаме циркулярна репрезентация т.е. съседите на клетка с индекс [n-1] са
// клетките [n-2], [n-3], [0], [1].
// Програмата очаква като вход: две числа n и m, символизиращи броя на клетките и
// броя на еволюциите. Клетките са винаги повече от 4. След това се прочитат
// стойностите на клетките. Като изход се извежда масивът след m-тата еволюция.
// Пример:
// Вход:
// 11 10
// 0 0 0 1 1 0 1 1 0 0 0
// Изход: 0 0 1 1 0 1 0 1 1 0 0

int neighbourIndex(int len, int currentCell, int neighbour) {
	int offset = currentCell + neighbour;

	// This is a bit more readable than nested ternary operators
	if (offset < 0) return len + offset;
	if (offset >= 0) return offset - len;
	return offset;
}

void cpyValuesTo(bool src[], bool dst[], int len) {
	for (int i = 0; i < len; i++)
		dst[i] = src[i];
}

void evolve(bool cells[], int len, int evolutions) {
	bool evCells[len];

	for (int evolution = 0; evolution < evolutions; evolution++) {
		cpyValuesTo(cells, evCells, len);

		for (int i = 0; i < len; i++) {
			// Calculate alive neighbours
			int n1 = neighbourIndex(len, i, -2),
				n2 = neighbourIndex(len, i, -1),
				n3 = neighbourIndex(len, i, 1),
				n4 = neighbourIndex(len, i, 2);
			int aliveNeigh = cells[n1] + cells[n2] + cells[n3] + cells[n4];

			// Determine if a cell should change state
			if (!cells[i] && (aliveNeigh == 2 || aliveNeigh == 3))
				evCells[i] = true;
			else if (cells[i] && !(aliveNeigh == 2 || aliveNeigh == 4))
				evCells[i] = false;
		}

		cpyValuesTo(evCells, cells, len);
	}
}

void bonus() {
	const int LINE_BUFFER_SIZE = 10000;

	int n, m;
	cin >> n >> m;

	// Get input
	bool cells[LINE_BUFFER_SIZE];
	for (int i = 0; i < n; i++)
		cin >> cells[i];

	evolve(cells, n, m);

	// Print result
	for (int i = 0; i < n; i++)
		cout << cells[i] << " ";
	cout << endl;
}

int main() {
	bonus();
}