Всего студенты разбились на 4 группы — те кто посетил только первый ресторан, кто только второй, кто посетил оба ресторана и кто не сдал экзамен. Один из наиболее простых вариантов отсечь все некорректные случаи — посчитать, сколько студентов оказалось в каждой группе. Для первой группы это значение равно A - C, для второй: B - C, для третьей: C, для четвертой: N - A - B + C. Теперь достаточно проверить, что в первых трех группах неотрицательное число студентов, а в последней — положительное. Если это так, то количество студентов в последней группе и есть ответ на задачу.

	int n1 = a - c;
	int n2 = b - c;
	int n3 = c;
	int n4 = n - n1 - n2 - n3;
	if (n1 >= 0 && n2 >= 0 && n3 >= 0 && n4 > 0)
		cout << n4;
	else
		cout << -1;

В общем случае, рекомендуется ознакомиться с методом включений-исключений.

Кроме того, ограничения в задаче позволяют перебрать значения количества студентов в каждой группе (кроме третьей) за O(N³) и проверить, соответствует ли такое разбиение условию. Если ни одно разбиение не подошло — вывести  - 1:

	int n3 = c;
	for (int n1 = 0; n1 <= n; n1++)
		for (int n2 = 0; n2 <= n; n2++)
			for (int n4 = 1; n4 <= n; n4++)
				if (n1 + n3 == a && n2 + n3 == b && n1 + n2 + n3 + n4 == n) {
					cout << n4;
					return 0;
				}
	cout << -1;

В этой задаче применим жадный алгоритм. Действительно, Васе выгодно сначала исправлять наиболее низкие оценки. Поэтому можно отсортировать полученные оценки в порядке возрастания и начать заменять их на 5, пока не получим желаемый результат. Для проверки результата можно после каждой операции вычислять среднее арифметическое заново (итого, сложность будет O(N²)) или поддерживать текущую сумму оценок, пересчитывая среднее арифметическое за O(1) с общей сложностью O(N), без учета сортировки, например, так:

bool check(int sum, int n) {
	// integer representation of sum / n >= 4.5
	return sum * 10 >= n * 45;
}

int main() {
	... // read integers to vector v and calculate sum
	sort(v.begin(), v.end());
	int ans = 0;
	while (!check(sum, n)) {
		sum += 5 - v[ans];
		ans++;
	}
	cout << ans;
}

Разумеется, оба подхода легко укладываются в ограничение по времени. Кроме того, рекомендуется избежать вычисление среднего арифметического значения с использованием вещественных чисел.

Несложно проверить, что для некоторого k условие выполняется (Вася съест не менее половины эклеров), то и для любого большего k это условие выполнится.

Значит, эту задачу можно решать при помощи бинарного поиска по ответу. Для проверки конкретного выбранного k можно использовать простую симуляцию процесса, описанного в условии.

bool check(long long k, long long n) {
	long long sum = 0;
	long long cur = n;
	while (cur > 0) {
		long long o = min(cur, k);
		sum += o;
		cur -= o;
		cur -= cur / 10;
	}
	return sum * 2 >= n;
}

Поскольку Петя съедает 10% от количества оставшихся эклеров, то это количество убывает экспоненциально, значит, пройдет достаточно мало дней прежде чем будут съедены все эклеры. В худшем случае ребятам потребуется 378 дней. Формально же асимптотика этого решения есть O(log(n)²).

Как и в предыдущей задаче рекомендуется избежать работы с вещественными числами и все вычисления производить в целых типах.

В этой задаче применим следующий жадный алгоритм. Будем идти по столбцам слева-направо, если мы сейчас рассматриваем столбец i и мы можем поставить фигуру, занимающую клетки столбцов i и i + 1, то нужно ее поставить. Действительно, если в оптимальном решении столбец i не занят ни одной фигурой, то в столбце i + 1 клетки заняты максимум одним слонопотамом. Значит, его можно убрать и поставить в столбцы i и i + 1, от этого ответ станет не хуже.

Немного более сложный вопрос — как именно поставить фигуру, если все 4 клетки столбцов i и i + 1 свободны (в других случаях фигуру можно поставить только одним способом)? Разумеется, в столбце i выгодно занять обе клетки. Оказывается, при этом неважно, какую именно клетку столбца i + 1 займет слонопотам. Действительно, клетки столбца i + 1 могут пригодиться только при размещении фигуры в столбцах i + 1,i + 2. Если в столбце i + 2 свободно не более одной клетки, то разместить фигуру не получится и клетки столбца i + 1 ни на что не влияют. Если же в столбце i + 2 свободны обе клетки, то мы можем разместить слонопотама при любом выборе занятой клетки столбца i + 1.

Из этого следует, что нам вообще можно не расставлять фигуры, а лишь пересчитывать количество свободных клеток в столбцах. В соответствии с описанным алгоритмом, получаем такой код:

	... // read strings s[0] and s[1]
	int ans = 0;
	int previous = 0;
	for (int i = 0; i < n; i++) {
		int current = (s[0][i] == '0') + (s[1][i] == '0');
		if (current == 0)
			previous = 0;
		if (current == 1) {
			if (previous == 2) {
				ans++;
				previous = 0;
			}
			else
				previous = 1;
		}
		if (current == 2) {
			if (previous > 0) {
				ans++;
				if (previous == 2)
					previous = 1;
				else
					previous = 0;
			}
			else
				previous = 2;
		}
	}

Более того, эту реализацию можно заметно упростить, сведя решение всего к двум случаям:

	int ans = 0;
	int empty = 0;
	for (int i = 0; i < n; i++) {
		int current = (s[0][i] == '0') + (s[1][i] == '0');
		empty += current;
		if (empty >= 3) {
			empty -= 3;
			ans++;
		}
		else
			empty = current;
	}

Формально данную реализацию можно отнести к динамическому программированию. Разумеется, ее можно написать и не обладая глубокими знаниями этого метода.

Кроме того, задачу можно решать более ''явной'' динамикой (например в качестве состояния использовать номер текущего столбца и состояние предыдущего). В этом случае реализация будет чуть более сложной, но не будет необходимости доказывать описанные выше утверждения.

Из условия следует, что цифры оригинального номера автобуса представляют собой некоторое подмножество цифр номера, увиденного Васей. Перебрать подмножество цифр можно стандартным алгоритмом за 2^k операций (где k — длина числа n). При этом каждое подмножество нужно проверить на корректность (содержит ли оно все нужные цифры) и привести к ''каноническому'' виду (например, отсортировать), чтобы избежать повторений с подмножествами, отличающимися лишь порядком цифр. Среди корректных наборов нужно оставить только уникальные.

	long long ans = 0;
	for (int i = 1; i <= (1 << k); i++) {
		string c;
		for (int j = 0; j < k; j++)
			if (i & (1 << j))
				c += n[j];
		ans += getans(c);
	}

Теперь для выбранного набора цифр нужно посчитать количество вариантов номера автобуса. Это можно сделать за O(k), использовав стандартную формулу числа перестановок мультимножества (см. секцию ''Permutations of multisets'' в статье про перестановки и мультиномиальные коэффициенты)

C = k! / (c₀! * c₁! * ... * c₉!),

где k — общее количество цифр в наборе, а c_i — количество цифр i в наборе:

long long fact[20];
int c[10];

void split(string s, int *c) {
	for (int i = 0; i < 10; i++)
		c[i] = 0;
	for (char ch : s)
		c[ch - 48]++;
}

long long getCount() {
	long long ans = fact[accumulate(c, c + 10, 0)];
	for (int i = 0; i < 10; i++)
		ans /= fact[c[i]];
	return ans;
}

Из этого числа нужно вычесть количество номеров, начинающихся на 0, если 0 присутствует в наборе. Сделать это достаточно просто: если мы поставим на первое место 0, то достаточно уменьшить k на 1 и c₀ на 1, после чего применить формулу выше — она посчитает количество способов разместить остальные цифры набора.

long long getans(string s) {
	split(s, c);

	// check whether the string contains all digits
	for (int i = 0; i < 10; i++)
		if (c0[i] && !c[i])
			return 0;

	// check whether we already processed such string
	sort(s.begin(), s.end());
	if (was.count(s))
		return 0;
	was.insert(s);

	long long ans = getCount();
	if (c[0] > 0) {
		c[0]--;
		ans -= getCount();
	}
	return ans;
}

Итого, даже при грубой оценке сложности и простой реализации получаем асимптотику O(2^k * k), где k ≤ 19 — количество цифр числа n. Легко проверить, что ответ всегда не превосходит 10¹⁸, поэтому для его вычисления достаточно ограничится стандартным 64-битовым типом.