Спасибо K1o0n за то, что он был mvp при подготовке раунда.
Идея: Vladosiya
Подготовка: K1o0n
Докажем, почему всегда лучше прибавлять к наименьшему числу. Пусть $$$a \le b \le c$$$, тогда сравним три выражения: $$$(a+1)\times b \times c$$$, $$$a \times (b+1) \times c$$$ и $$$a \times b \times (c+1)$$$. Уберем общую часть $$$a \times b \times c$$$, и получаем: $$$b \times c$$$, $$$a \times c$$$, $$$a \times b$$$.
$$$b \times c \ge a \times c$$$, так как $$$a \le b$$$, аналогично, $$$b \times c \ge a \times b$$$, так как $$$a \le c$$$. Поэтому можно просто $$$5$$$ раз найти минимум и прибавить к нему единицу. И таким образом получить ответ.
Иной, примитивный подход просто перебрать то, что мы будем прибавлять к $$$a$$$, $$$b$$$ и $$$c$$$ тремя циклами.
Так как прибавить можно всего $$$5$$$ раз, то асимптотика решения $$$O(1)$$$.
for _ in range(int(input())):
arr = sorted(list(map(int,input().split())))
for i in range(5):
arr[0]+=1
arr.sort()
print(arr[0] * arr[1] * arr[2])
Идея: Noobish_Monk
Подготовка: K1o0n
Пусть мы хотим соединить две запеканки с длинами $$$x$$$ и $$$y$$$. Мы можем разобрать одну из них на куски длины $$$1$$$ и затем присоединять их к запеканке размера $$$y$$$. Суммарно мы сделаем $$$2x - 1$$$ операций. Так как мы хотим соединить $$$k$$$ кусков, хотя бы $$$k - 1$$$ из них нам придётся разобрать, а затем присоединить к чему-то. Если мы к какому-то куску присоединяем что-то, его уже нет смысла разбирать, так как чтобы его разобрать, нам нужно будет в том числе убрать эти куски. Поэтому мы хотим выбрать какой-то кусок, к которому мы будем соединять все остальные. Оптимальным будет выбрать кусок с максимальным размером и к нему всё соединять. Таким образом, ответ получается $$$2 \cdot (n - mx) - k + 1$$$, где $$$mx$$$ $$$-$$$ длина максимального куска.
Асимптотика решения: $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
signed main() {
int T;
cin >> T;
while (T--){
int n, k;
cin >> n >> k;
vector<int> s(k);
int m = -1;
for (int i = 0; i < k; i++){
cin >> s[i];
m = max(m, s[i]);
}
cout << 2 * (n - m) - k + 1 << '\n';
}
}
for _ in range(int(input())):
n,k = map(int,input().split())
mx = max(map(int, input().split()))
print((n - mx) * 2 - (k - 1))
1992C - Горилла и перестановка
Идея: K1o0n
Подготовка: K1o0n
Пусть $$$p$$$ $$$-$$$ некоторая перестановка. Посмотрим на вклад числа $$$p_i$$$ в сумму $$$\sum_{i=1}^n {f(i)}$$$. Если оно меньше $$$k$$$, вклад равен $$$0$$$, иначе вклад равен $$$p_i \cdot (n - i + 1)$$$. Аналогично посмотрим на вклад $$$p_i$$$ в сумму $$$\sum_{i=1}^n {g(i)}$$$. Если оно больше $$$m$$$, вклад равен $$$0$$$, иначе $$$-$$$ $$$p_i \cdot (n - i + 1)$$$. Так как $$$m < k$$$, каждое число даёт вклад, больший $$$0$$$, не более чем в одну сумму. Поэтому выгодно поставить числа, не меньшие $$$k$$$, в начало, а числа, не большие $$$m$$$, в конец. Также числа, не меньшие $$$k$$$, должны идти в порядке убывания, чтобы максимизировать сумму $$$f(i)$$$. Аналогично числа, не большие $$$m$$$, должны идти в порядке возрастания, чтобы минимизировать сумму $$$g(i)$$$.
Например можно построить такую перестановку: $$$n, n - 1, \ldots, k, m + 1, m + 2, \ldots, k - 1, 1, 2, \ldots, m$$$. Легко видеть, что $$$\sum_{i=1}^n f(i)$$$ не может быть больше ни для какой другой перестановки, а $$$\sum_{i=1}^n g(i)$$$ не может быть меньше ни для какой другой перестановки, поэтому наш ответ оптимален.
Асимптотика решения: $$$O(n)$$$.
for _ in range(int(input()):
n,m,k = map(int,input().split())
print(*range(n,m,-1), *range(1,m+1))
Идея: ArSarapkin
Подготовка: K1o0n
В этой задаче есть два основных решения: динамическое программирование и жадный алгоритм.
Решение с динамикой: $$$dp_i$$$ $$$-$$$ минимальное количество метров, которое надо проплыть в воде, чтобы добраться до $$$i$$$-й клетки. База динамики: $$$dp_0 = 0$$$. Тогда пересчет происходит так: \begin{equation*} dp_i = \text{минимум из} \begin{cases} dp_{i-1} + 1& \text{если } A_i = \text{'W'} \\ min(dp_j) & \text{по всем } j, \text{таким что:} \max(0, i — m) \le j < i \text{ и } A_j = \text{'L'} \end{cases} \end{equation*} Асимптотика решения: $$$O(nm)$$$.
Решение с жадным алгоритмом: Если мы можем прыгать, мы хотим прыгать на берег, если можем. Если не можем, мы хотим прыгать на любое бревно впереди, чтобы потом прыгать с него. Если не можем, прыгаем максимально далеко, чтобы избежать крокодилов и плыть как можно меньше.
Асимптотика решения: $$$O(n)$$$.
def run() -> None:
n,m,k = map(int, input().split())
A = input()
logs = [i for i in range(n) if A[i] == "L"]
logs.append(n+1)
i = -1
next_log = 0
while i < n-1:
if m >= logs[next_log] - i:
i = logs[next_log]
else:
i+=m
if i > n-1:
print("YES")
return
while i < n and i < logs[next_log]:
if A[i] != "C" and k > 0:
i+=1
k-=1
else:
print("NO")
return
next_log +=1
print("YES")
for _ in range(int(input())):
run()
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
vector<int> dp(n + 2, -1);
dp[0] = k;
for (int i = 1; i <= n + 1; i++) {
if (i != n + 1 && s[i - 1] == 'C')
continue;
for (int t = 1; t <= m; t++)
if (i - t >= 0 && (i - t == 0 || s[i - t - 1] == 'L'))
dp[i] = max(dp[i], dp[i - t]);
if (i > 1 && s[i - 2] == 'W')
dp[i] = max(dp[i], dp[i - 1] - 1);
}
if (dp[n + 1] >= 0)
cout << "YES\n";
else
cout << "NO\n";
}
}
Идея: Noobish_Monk, K1o0n
Подготовка: K1o0n
Заметим, что $$$n * a - b$$$ строго меньше $$$10^6$$$, то есть имеет не больше $$$6$$$ цифр. Число символов в странном подсчёте $$$n * a - b$$$ равно $$$|n| * a - b$$$, где $$$|n|$$$ $$$-$$$ количество цифр в n. Давайте будем перебирать значение $$$a$$$, а дальше определим для него границы $$$minB$$$ и $$$maxB$$$ так, что $$$|n| * a > maxB$$$ и $$$|n| * a - minB \le 6$$$. Тогда: \begin{cases} minB = |n| * a- 6 \\ maxB = |n| * a- 1 \end{cases} Переберём все $$$b$$$ от $$$minB$$$ до $$$maxB$$$. Чтобы быстро проверять странный подсчёт, давайте будем находить только его первые $$$|n| * a - b$$$ цифр. Таким образом мы можем быстро найти все подходящие пары $$$(a, b)$$$. Асимптотика решения: $$$O(a)$$$.
for _ in range(int(input())):
n = int(input())
sn = str(n)
lenN = len(str(n))
ans = []
for a in range(1, 10001):
minB = max(1, lenN * a - 5)
maxB = lenN * a
for b in range(minB, maxB):
x = n * a - b
y = 0
for i in range(lenN * a - b):
y = y * 10 + int(sn[i % lenN])
if x == y:
ans.append((a, b))
print(len(ans))
for p in ans:
print(*p)
Идея: Noobish_Monk
Подготовка: Noobish_Monk
Рассмотрим жадный алгоритм "берём пока набирается". Докажем, что он работает. В любом оптимальном разбиении, если мы взяли первый отрезок не максимальной длины, мы не нарушим критерий, если от второго отрезка перекинем один элемент в первый. Следовательно приведенный жадный алгоритм корректный.
Теперь разберёмся, как быстро понимать, можем ли мы удлинить отрезок. Во-первых, найдём все делители числа $$$x$$$. Если число $$$a_i$$$ не является его делителем, то оно не может входить ни в одно множество чисел, произведение которых равно $$$x$$$, поэтому мы можем просто добавить его в отрезок. Если же $$$a_i$$$ является делителем, нам надо как-то научиться понимать, даёт ли оно в произведении с какими-то другими делителями на отрезке число $$$x$$$. Будем поддерживать множество делителей, которые являются произведениями каких-то чисел на отрезке. Чтобы обновить множество при добавлении $$$a_i$$$, пройдёмся по всем делителям этого множества и для каждого делителя $$$d$$$ добавим $$$d \cdot a_i$$$ в множество. Если же мы добавили число $$$x$$$ в множество, $$$a_i$$$ будет лежать уже в следующем отрезке и нам надо очистить множество.
P. S.: О деталях реализации и времени работы. Если поддерживать множество в структуре set, то мы получаем время работы $$$O(n \cdot d(x) \cdot \log(d(x)))$$$, где $$$d(x)$$$ $$$-$$$ число делителей $$$x$$$. Вместо множества можно сделать, например, глобальный массив $$$used$$$ размера $$$10^5 + 1$$$, а также поддерживать вектор достижимых делителей. Используя эти структуры можно получить время работы $$$O(n \cdot d(x))$$$.
#include <iostream>
#include <vector>
using namespace std;
const int A = 1e6 + 1;
bool used[A];
bool divs[A];
void solve() {
int n, x;
cin >> n >> x;
vector<int> a(n);
vector<int> vecDivs;
for (int d = 1; d * d <= x; d++) {
if (x % d == 0) {
divs[d] = true;
vecDivs.push_back(d);
if (d * d < x) {
vecDivs.push_back(x / d);
divs[x / d] = true;
}
}
}
for (int i = 0; i < n; i++)
cin >> a[i];
int ans = 1;
used[1] = true;
vector<int> cur{ 1 };
for (int i = 0; i < n; i++) {
if (!divs[a[i]])
continue;
vector<int> ncur;
bool ok = true;
for (int d : cur)
if (1ll * d * a[i] <= x && divs[d * a[i]] && !used[d * a[i]]) {
ncur.push_back(d * a[i]);
used[d * a[i]] = true;
if (d * a[i] == x)
ok = false;
}
for (int d : ncur)
cur.push_back(d);
if (!ok) {
ans++;
for (int d : cur)
used[d] = false;
used[1] = true;
used[a[i]] = true;
cur = vector<int>{ 1, a[i] };
}
}
for (int d : vecDivs) {
divs[d] = false;
used[d] = false;
}
cout << ans << '\n';
}
signed main() {
int T;
cin >> T;
while (T--)
solve();
return 0;
}
Идея: Noobish_Monk, K1o0n
Подготовка: K1o0n
Будем перебирать размер множества $$$k$$$ и его $$$\text{MEOW}$$$, $$$m$$$. Если $$$2k \geqslant n$$$, то множество $$$x$$$ заполнит все оставшиеся числа до $$$n$$$ и возможно в нём останется ещё какие-то большие $$$n$$$, поэтому $$$MEOW$$$ от всех таких множеств будет $$$2k+1$$$, а всего таких множеств для каждого $$$k$$$ будет $$$C(n, k)$$$. Если же $$$2k < n$$$, $$$m$$$ лежит в интервале от $$$k+1$$$ до $$$2k+1$$$. Заметим, что чисел до $$$m$$$ может быть ровно $$$m - 1 - k$$$, а чисел справа от $$$m$$$ соответственно $$$2k + 1 - m$$$, а значит к ответу надо прибавить $$$C_{m - 1}^{m - 1 - k} \cdot C_{n - m}^{2k + 1 - m} \cdot m$$$.
Асимптотика решения: $$$O(n^2)$$$.
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int add(int a, int b) {
if (a + b >= mod)
return a + b - mod;
return a + b;
}
int sub(int a, int b) {
if (a < b)
return a + mod - b;
return a - b;
}
int mul(int a, int b) {
return (int)((1ll * a * b) % mod);
}
int binpow(int a, int pw) {
int b = 1;
while (pw) {
if (pw & 1)
b = mul(b, a);
a = mul(a, a);
pw >>= 1;
}
return b;
}
int inv(int a) {
return binpow(a, mod - 2);
}
const int N = 15000;
int f[N], r[N];
void precalc() {
f[0] = 1;
for (int i = 1; i < N; i++)
f[i] = mul(f[i - 1], i);
r[N - 1] = inv(f[N - 1]);
for (int i = N - 2; i > -1; i--)
r[i] = mul(r[i + 1], i + 1);
}
int C(int n, int k) {
if (n < 0 || k < 0 || n < k)
return 0;
return mul(f[n], mul(r[k], r[n - k]));
}
inline void solve() {
int n;
cin >> n;
int ans = 1;
for (int k = 1; k <= n; k++) {
if (2 * k >= n) {
ans = add(ans, mul(2 * k + 1, C(n, k)));
continue;
}
for (int m = k + 1; m <= 2 * k + 1; m++) {
int c = mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m));
ans = add(ans, mul(mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m)), m));
}
}
cout << ans << '\n';
}
signed main() {
int T = 1;
cin >> T;
precalc();
while(T--)
solve();
return 0;
}