Докажем, почему всегда лучше прибавлять к наименьшему числу. Пусть $$$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])

Пусть мы хотим соединить две запеканки с длинами $$$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))

Пусть $$$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 \lt 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))

В этой задаче есть два основных решения: динамическое программирование и жадный алгоритм.

Решение с динамикой: $$$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";
    }
}

Заметим, что $$$n * a - b$$$ строго меньше $$$10^6$$$, то есть имеет не больше $$$6$$$ цифр. Число символов в странном подсчёте $$$n * a - b$$$ равно $$$|n| * a - b$$$, где $$$|n|$$$ $$$-$$$ количество цифр в n. Давайте будем перебирать значение $$$a$$$, а дальше определим для него границы $$$minB$$$ и $$$maxB$$$ так, что $$$|n| * a \gt 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)

Рассмотрим жадный алгоритм "берём пока набирается". Докажем, что он работает. В любом оптимальном разбиении, если мы взяли первый отрезок не максимальной длины, мы не нарушим критерий, если от второго отрезка перекинем один элемент в первый. Следовательно приведенный жадный алгоритм корректный.

Теперь разберёмся, как быстро понимать, можем ли мы удлинить отрезок. Во-первых, найдём все делители числа $$$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;
}

Будем перебирать размер множества $$$k$$$ и его $$$\text{MEOW}$$$, $$$m$$$. Если $$$2k \geqslant n$$$, то множество $$$x$$$ заполнит все оставшиеся числа до $$$n$$$ и возможно в нём останется ещё какие-то большие $$$n$$$, поэтому $$$MEOW$$$ от всех таких множеств будет $$$2k+1$$$, а всего таких множеств для каждого $$$k$$$ будет $$$C(n, k)$$$. Если же $$$2k \lt 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;
}