Максимальный объем, на который можно уменьшить посылку со сторонами $$$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;
    }
}

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

Недочет с моей стороны, поправил условие задачи.

Для каждой пары $$$X$$$, $$$Y$$$ ответ будет равен $$$X$$$ $$$div$$$ $$$gcd(X,Y) - 1$$$

Если $$$X=1$$$, то нельзя разложить дробь на цепного мутанта, а значит ответ 0. Иначе:

Если $$$X,Y$$$ не взаимнопросты, то поделим их на НОД, затем

.

Домножим получившуюся дробь на $$$K$$$, так что $$$(B \times K) mod X = 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;
	}
}

Очевидно, что ученых — конечное количество, а именно 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;
    }
}