991A - If at first you don't succeed...
Всего студенты разбились на 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(N3) и проверить, соответствует ли такое разбиение условию. Если ни одно разбиение не подошло — вывести - 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(N2)) или поддерживать текущую сумму оценок, пересчитывая среднее арифметическое за 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;
}
Разумеется, оба подхода легко укладываются в ограничение по времени.