991A - If at first you don't succeed...
There are 4 groups of students — those who visited only the first restaurant, who visited only the second, who visited both places and who stayed at home. One of the easiest ways to detect all the incorrect situations is to calculate number of students in each group. For the first group it is A - C, for the second: B - C, for the third: C and for the fourth: N - A - B + C. Now we must just to check that there are non-negative numbers in the first three groups and the positive number for the last group. If such conditions are met the answer is the number of students in the fourth group.
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;
}
Разумеется, оба подхода легко укладываются в ограничение по времени. Кроме того, рекомендуется избежать вычисление среднего арифметического значения с использованием вещественных чисел.
Несложно проверить, что для некоторого k условие выполняется (Вася съест не менее половины эклеров), то и для любого большего k это условие выполнится.
Действительно, рассмотрим количество эклеров, которое останется вечером каждого дня при некотором выбранном k1 — пусть в день i останется ai эклеров. Если мы возьмем для Васи другое число k2 > k1, то в первый вечер останется меньше эклеров: b1 < a1. Но тогда Петя вечером съест эклеров не больше, чем в первом случае и на следующий день их будет меньше. Аналогично с учетом k2 > k1 и к вечеру второго дня b2 < a2 и так далее. Таким образом, для любого i получаем bi < ai, а значит и Петя каждый день будет есть не больше эклеров, чем в первом случае. Значит, Петя в сумме съест не больше эклеров, чем в первом случае, а Вася — не меньше.
Значит, эту задачу можно решать при помощи бинарного поиска по ответу. Для проверки конкретного выбранного 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)2).
Как и в предыдущей задаче рекомендуется избежать работы с вещественными числами и все вычисления производить в целых типах.
В этой задаче применим следующий жадный алгоритм. Будем идти по столбцам слева-направо, если мы сейчас рассматриваем столбец 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;
}
Формально данную реализацию можно отнести к динамическому программированию. Разумеется, ее можно написать и не обладая глубокими знаниями этого метода.
Кроме того, задачу можно решать более ''явной'' динамикой (например в качестве состояния использовать номер текущего столбца и состояние предыдущего). В этом случае реализация будет чуть более сложной, но не будет необходимости доказывать описанные выше утверждения.
Из условия следует, что цифры оригинального номера автобуса представляют собой некоторое подмножество цифр номера, увиденного Васей. Перебрать подмножество цифр можно стандартным алгоритмом за 2k операций (где 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! / (c0! * c1! * ... * c9!),
где k — общее количество цифр в наборе, а ci — количество цифр 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 и c0 на 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(2k * k), где k ≤ 19 — количество цифр числа n. Легко проверить, что ответ всегда не превосходит 1018, поэтому для его вычисления достаточно ограничиться стандартным 64-битовым типом.
Все числа в задаче (кроме числа 1010, которое дано в примере) содержат максимум 10 цифр. Значит, если мы хотим найти более короткое представление, оно должно содержать максимум 9 цифр. Заметим, что длина суммы двух чисел не превосходит суммы длин чисел, поэтому в оптимальном представлении максимум одно слагаемое является числом, а остальные слагаемые — выражения содержащие * или ^. Каждое выражение имеет длину хотя бы 3 символа, значит, в представлении может быть максимум 3 слагаемых. Максимальное число, которое можно представить 3 слагаемыми: 9^9+9^9+9, но это число содержит лишь 9 знаков, а выражения с 3 слагаемыми всегда содержит минимум 9 знаков. Значит, всегда существует оптимальное представление, содержащее максимум два слагаемых.
Тогда существует 3 варианта, как можно представить исходное число:
n = a^bn = x+yn = x*y
где x и y — выражения (в первом случае a и b — числа), не содержащие знаков +. Причем, во всех случаях эти выражения содержат максимум 7 символов.
Давайте найдем для каждого x, не превосходящего n, эквивалентное выражение m[x], содержащие не более 7 символов (если оно короче, чем само число), а так же для каждой длины d — список чисел s[d], которые можно представить выражением длины d. Для этого удобно использовать, например, стандартные контейнеры map и set в C++:
map<long long, string> m;
set<long long> s[10];
string get(long long x) {
if (m.count(x))
return m[x];
return toString(x);
}
void relax(long long x, string str) {
// obviously not optimal
if (x > n || str.length() >= getlen(x))
return;
// already have better
if (m.count(x) && m[x].length() <= str.length())
return;
s[m[x].length()].erase(x);
m[x] = str;
s[str.length()].insert(x);
}
Сначала добавим все возможные выражения вида a^b — их будет порядка sqrt(n).
void generatePowers() {
for (long long x = 2; x * x <= n; x++) {
long long c = x * x;
int p = 2;
while (c <= n) {
string tmp = toString(x) + "^" + toString(p);
relax(c, tmp);
c *= x;
p++;
}
}
}
Теперь рассмотрим выражения, состоящие из нескольких множителей. Заметим, что аналогично со сложением, в выражении максимум один множитель является числом. Тогда выражение может иметь только вид:
x = a^b*c^dx = a^b*c
где a, b, c и d — некоторые числа. Давайте переберем длину i первого множителя и пройдем по всем значениям контейнера s[i]. Тогда второй множитель может иметь длину максимум d = 7 - i - 1 и вариантов выбрать этот множитель будет достаточно мало. Второй множитель можно перебрать, пройдя по контейнерам длины до d в первом случае, либо перебрать числа от 1 до 10d во втором случае. Всего при этом мы добавим в m порядка k = 150000 чисел:
void generatePowerAndPower(int maxlen) {
for (int i = 1; i <= maxlen; i++)
for (int j = i; i + j + 1 <= maxlen; j++)
for (auto x : s[i])
for (auto y : s[j])
relax(x * y, get(x) + "*" + get(y));
}
void generateSimpleAndPower(int maxlen) {
for (int i = 1; i + 2 <= maxlen; i++)
for (long long x = 1; x < p10[maxlen - 1 - i]; x++)
for (long long y : s[i])
relax(x * y, toString(x) + "*" + get(y));
}
void precalc() {
generatePowers();
generatePowerAndPower(7);
generateSimpleAndPower(7);
}
Теперь вернемся к представлению исходного числа. Для случая a^b мы уже добавили выражения в m. Для случаев x+y и x*y заметим, что можно считать, что длина выражения x не больше 4. Давайте переберем x среди найденных выражений длины до 4, а так же среди чисел от 1 до 104. Для каждого варианта x мы однозначно определяем значение y, оптимальное представление которого уже записано в m или просто равняется числу. Таким образом, для каждого x мы сможем найти оптимальный ответ за одно обращение к m — log(k) операций.
string ans;
void relaxAns(string s) {
if (ans.length() > s.length())
ans = s;
}
void check2() {
for (int i = 1; i * 2 + 1 < ans.length(); i++) {
for (long long x = 1; x <= p10[i]; x++) {
relaxAns(get(n - x) + "+" + get(x));
if (n % x == 0)
relaxAns(get(n / x) + "*" + get(x));
}
for (auto x : s[i]) {
relaxAns(get(n - x) + "+" + get(x));
if (n % x == 0)
relaxAns(get(n / x) + "*" + get(x));
}
}
}
int main() {
... // read n, calculate powers of 10
precalc();
ans = get(n);
check2();
cout << ans;
}
Итого, общая сложность алгоритма есть O((sqrt(n) + k + 104) * log(k)).
