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;
In general you are recommended to view inclusion–exclusion principle.
Moreover the limitations allow to go over all possible numbers of students for each group (except for the third) in O(N3) and to check whether such numbers produce a correct solution. If no correct numbers found, just print - 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;
It is necessary to use the greedy approach: of course Vasya should redo the lowest grades firstly. So we have to sort the values in the ascending order and begin to replace the values by 5 until we get the desired result. In order to check whether the current state is suitable we may calculate the mean value after each iteration (O(N2) complexity in total), or just update sum of the grades and calculate the arithmetic mean in O(1) with O(N) total complexity (excluding sorting). For example:
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;
}
Of course, both approaches easily fit TL.
Finally, it is recommended to avoid floating-point operations while calculating the mean value.
It is easy to check that if for some value k the necessary condition is met (Vasya eats at least half of the candies), then it is met for each integer greater k.
Let's consider the number of candies remaining at the evening of each day for some selected k1 — let ai candies remain at day i. If Vasya will use another number k2 > k1 we will have less candies in the first day: b1 < a1. So Petya will eat no more candies than in the first case (for k1), but in the next day the number of candies will be not greater than in the first case (if n1 > n2 then n1 - n1 / 10 ≥ n2 - n2 / 10). The same way, including that k2 > k1 at the evening of the second day we get b2 < a2 and so on. In general, for each i we have bi < ai, so Petya will eat not more candies than in the first case in total. It means that Vasya will eat not less candies than in the first case.
So this problem can be solved using the binary search (answer) approach. In order to check whether selected k is applicable it necessary just to implement the process described in the problem statement.
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;
}
Since Petya eats 10% of candies, its amount decreases exponentially, so there will be only few days before all the candies will be eaten. In the worst case it is necessary 378 days. Formally the complexity of the solution is O(log(n)2).
Like in the previous problem it is recommended to avoid floating operations and to use only integer types.
In this problem we may use the greedy approach. Let's go through columns from left to right. If we are currently considering column i and we may place a figure occupying only cells at columns i and i + 1, we have to place this figure. Really if the optimal solution doesn't contain a bishwock at column i then column i + 1 may be occupied by at most one bishwock. So we can remove this figure and place it at columns i and i + 1, the result will be at least the same.
A bit harder question is — how exactly we should place the figure if all 4 cells of columns i and i + 1 are empty (in other cases there will be only one way to place a bishwock)? Of course, we should occupy both cells of column i. Moreover it does not matter which cell we will occupy at column i + 1 in this case. The cells of i + 1 may be used only for placing a bishwock in columns i + 1,i + 2. If column i + 2 has at most one empty cell we are unable to place such figure and the remaining empty cells of column i + 1 are useless at all. If both cells of column i + 2 are empty we may place a bishwock regardless of the position of the remaining empty cell at column i + 1.
It means that we don't have to place the figures actually — we have to calculate and update number of empty cells in columns. According to the described algorithm we may write such code:
... // 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;
}
}
Moreover this implementation can be simplified to just two cases:
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;
}
Formally such algorithm may be considered as the dynamic programming. Of course it is not necessary to have a deep understanding of DP to write such implementation and solve the problem.
This problem also can be solved by more ''obvious'' DP approach (for example we may consider index of current column and state of the cells of the previous column as a state of DP). In this case the implementation will be a bit more complicated but it won't be necessary to prove described solution.
Из условия следует, что цифры оригинального номера автобуса представляют собой некоторое подмножество цифр номера, увиденного Васей. Перебрать подмножество цифр можно стандартным алгоритмом за 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)).
