Контест, к которому написан разбор
[problem:278521A]
Максимальный объем, на который можно уменьшить посылку со сторонами $$$a$$$, $$$b$$$, $$$c$$$ это $$$a \times b \times c$$$. Тогда , чтобы получить минимальный уменьшаемый объём — нужно максимизировать объем, который поместится в устройство с размерами $$$w \times h$$$ и бесконечной длиной.
Для этого можно для каждой пары сторон смотреть помещаются ли они — если нет, то по этим сторонам посылку можно уменьшить, затем получившиеся стороны домножить на третью. И так для всех пар сторон — $$$(a,b)$$$, $$$(b,c)$$$, $$$(a,c)$$$, $$$(b,a)$$$, $$$(c,b)$$$, $$$(c,a)$$$.
И из $$$a \times b \times c$$$ вычесть максимальное получившиеся значение.
Ответ мог превосходить $$$int$$$, но не все участники сразу догадались об этом =(
#include <iostream>
using namespace std;
long long n, w, h, a[3];
long long solve(int x) {
if (x > 2) return 0 ; else
return max(max(min(a[x], w) * min(a[(x + 1) % 3], h) * a[(x + 2) % 3],
min(a[x], h) * min(a[(x + 1) % 3], w) * a[(x + 2) % 3])
, solve(x + 1));
}
int main() {
cin >> n >> w >> h;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) cin >> a[j];
cout << a[0]*a[1]*a[2] - solve(0) << endl;
}
}
[problem:278521B]
Необходимо реализовать бинпоиск по ответу. А для того, чтобы проверить можно ли достичь значения $$$mid$$$ сделаем ДП:
Возьмем любую пару значений $$$A_i$$$ и $$$A_j$$$, если $$$mid$$$ подходит как ответ, то значит $$$|A_i-A_j| \le |i-j| \times mid$$$ .
А в $$$dp_i$$$ будем считать кол-во необходимых изменений для того, чтобы $$$mid$$$ , был ответом для отрезка $$$[1 \ldots i]$$$, при этом само значение $$$A_i$$$ мы не меняем. Теперь для каждого $$$dp_i$$$ перебираем $$$A_j, j \in [1 \ldots i-1]$$$, это значит что элемент $$$A_j$$$ тоже не трогаем, а все, что между ними можем поменять.
Затем вычисляем $$$ans$$$ — количество необходимых изменений , чтобы $$$mid$$$ был ответом —
#include <iostream>
#include <vector>
using namespace std;
vector <long long> dp, a;
long long n, k;
bool ok(long long mid) {
long long ans = 100000000;
for (int i = 0; i < n; i++) {
dp[i] = i;
for (int j = 0; j < i; j++) {
if (abs(a[i] - a[j]) <= (i - j) * mid)
dp[i] = min(dp[i], dp[j] + i - j - 1);
}
ans = min(ans, dp[i] + n - i - 1);
}
return (ans <= k);
}
int main() {
cin >> n >> k;
a.resize(n);
dp.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long l, r;
l = -1;
r = 2000000001;
while (l + 1 < r) {
long long mid = (l + r) / 2;
if (ok(mid)) r = mid;
else l = mid;
}
cout << r;
}
[problem:278521C]
Недочет с моей стороны, поправил условие задачи.
Для каждой пары $$$X$$$, $$$Y$$$ ответ будет равен $$$X$$$ $$$div$$$ $$$gcd(X,Y) - 1$$$
Если $$$X=1$$$, то нельзя разложить дробь на цепного мутанта, а значит ответ 0. Иначе:
Если $$$X,Y$$$ не взаимнопросты, то поделим их на НОД, затем
.
Домножим получившуюся дробь на $$$K$$$, так что $$$(B \times K) mod X = X-1$$$ . Это всегда возможно.
Возьмем $$$i$$$, $$$j$$$, такие $$$ 0 \le i < j < X$$$. Предположим, что есть такая пара $$$i$$$, $$$j$$$, что $$$(B \times i) mod X = (B \times j) mod X = T$$$, тогда $$$B \times i = n \times X + T$$$, $$$B \times j = m \times X + T$$$,
отсюда получаем
Помним, что $$$X,B$$$ взаимнопросты, значит $$$(m-n)$$$ делится на $$$B$$$ и результат деления не меньше 1.
Получаем $$$(j-i) = X \times \cfrac{m-n}{B}$$$ , что невозможно, так как $$$ 0 \le i < j < X $$$ . Значит не может существовать два одинаковых остатка для $$$K \in [0 \ldots X-1]$$$, и можно получить остаток $$$X-1$$$.
$$$ \cfrac{1}{A + \cfrac{B}{X}} = \cfrac{K}{A \times K + \cfrac{X-1}{X}}$$$ , далее аналогичным образом будем раскладывать $$$\cfrac{X-1}{X} = \cfrac{1}{(\cfrac{X}{X-1})} = \cfrac{1}{1+\cfrac{1}{X-1}}$$$, получили аналогичную дробь, с которой можно проделать точно такие же операции.
Таким образом каждый раз знаменатель будет уменьшаться на 1, пока не достигнет 2. При знаменателе 2 дальнейшее разложение невозможно.
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
long long n, x, y;
cin >> n;
while (n > 0) {
--n;
cin >> x >> y;
cout << x / gcd(x, y) - 1 << endl;
}
}
[problem:278521D]
Очевидно, что ученых — конечное количество, а именно 1022.
Сгенерируем все id ученых, отсортируем их по возрастанию, а затем просто будем обрабатывать входящие строки и выводить порядковый номер ученого( например, бинпоиском. Но ограничения позволяют и линейно находить) , в id которого используются те же цифры, что и во входящей строке.
Сложность заключалась в генерации id всех ученых.
id любого ученого имеет не более 10 цифр.
Для генерации можно использовать полный рекурсивный перебор: Начнем генерацию с пустой строки. Первый символ может быть $$$[1 \ldots 9]$$$, второй либо $$$0$$$, либо символ, который больше предыдущего, все следующие символы должны быть больше предыдущих. Таким образом сгенерируем все id ученых.
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
vector<int> idList;
void gen(string id, int dig) {
if (dig > 10)
return;
if (id.size() == 1)
gen(id + '0', dig);
for (int i = dig; i < 10; i++)
gen(id + char('0' + i), i + 1);
if (id.size())
idList.push_back(stoi(id));
}
int main() {
gen("", 1);
sort(all(idList));
idList.resize(unique(all(idList)) - idList.begin());
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string X;
cin >> X;
sort(all(X));
X.resize(unique(all(X)) - X.begin());
if (X.front() == '0' && X.size() > 1)
swap(X[0], X[1]);
int num = lower_bound(all(idList), stoi(X)) - idList.begin();
cout << num + 1 << endl;
}
}
Во-первых, код должен быть красивым. Как это сделать, можно прочитать тут.
Далее по разбору:
"Очевидно, что если $$$K \leq N - 1$$$, то ответ $$$0$$$" — сомнительно. Кстати, даже при $$$K = N - 1$$$ бинпоиск все равно будет работать, поэтому в отдельный пункт это выносить нет смысла.
"Затем вычисляем $$$ans$$$ — кол-во необходимых изменений, чтобы $$$mid$$$ был ответом" — как?
Для многоточия есть специальная команда в LaTex:
\ldots
"Размер цепного мутанта — это его порядок" — спасибо, теперь то я все понял. А что такое порядок?
"Домножим получившуюся дробь на $$$K$$$, так что $$$(B \times K) \mod {X} = X - 1$$$" — почему это всегда возможно? Здесь стоит хотя бы упомянуть соответствующую теорему.
Ну и в последней задаче наверное стоит явно сказать, что для генерации можно использовать полный рекурсивный перебор.
И зачем вы везде сокращаете слово "количество"? Я понимаю, это может быть разумно, когда вы конспектируете лекцию, чтобы писать быстрее. Но тут то вас никто не торопит. Гораздо приятнее смотреть на текст без таких сокращений.
Благодарю за замечания! Поправил разбор =)