Давайте рассмотрим $$$2$$$ случая.

• $$$x >= y$$$ можно заметить, что каждую секунду блендер будет смешивать $$$/min(y, c)$$$ фруктов (где $$$c$$$ это количество не смешанных фруктов), следовательно ответ $$$\lceil {\frac{n}{y}} \rceil$$$.
• $$$x < y$$$ можно заметить что каждую секунду блендер будет смешивать $$$/min(x, c)$$$ фруктов, ответ $$$\lceil {\frac{n}{x}} \rceil$$$ аналогично.

Значит ответ это $$$\lceil {\frac{n}{min(x, y)}} \rceil$$$.

#include <iostream>

using namespace std;

int main(){
    int t = 1;
    cin >> t;
    while(t--){
        int n, x, y;
        cin >> n >> x >> y;
        x = min(x, y);
        cout << (n + x - 1) / x << endl;
    }
}

Можно заметить, что всегда $$$a_{n-1}$$$ будет отрицательным в итоговом ответе.

Следовательно, мы можем отнять $$$a_1 + a_2 + \ldots + a_{n-2}$$$ из $$$a_{n-1}$$$, после этого можно отнять $$$a_{n-1}$$$ из $$$a_n$$$.

Итого получаем сумму $$$a_1 + a_2 + \ldots + a_{n-2} - a_{n-1} + a_n$$$, больше этого нельзя получить, так как $$$a_{n-1}$$$ всегда будет отрицательным.

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int mod = 1e9 + 7;
 
void solve(){
    int n;
    cin >> n;
    ll ans = 0;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
        ans += a[i];
    }
    cout << ans - 2 * a[n - 2] << '\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

Будем поддерживать изначально пустую строку $$$t$$$, так чтобы $$$t$$$ встречалась в $$$s$$$ как подстрока.

Будем увеличивать строку $$$t$$$ на один символ, пока ее длина меньше $$$n$$$.

Проведем $$$n$$$ итераций, на каждой из них будем спрашивать строки $$$t + 0$$$ и $$$t + 1$$$. Если одна из них встречалась в $$$s$$$ как подстрока, то добавим нужную в конец и перейдем к следующей итерации.

Если же не одна из этих двух строк не встречалась в $$$s$$$, то значит строка $$$t$$$ это суффикс строки $$$s$$$. После этой итерации будем спрашивать строку $$$0 + t$$$, если она встречалась то добавим припишем $$$0$$$ к $$$t$$$, иначе припишем $$$1$$$.

Итого на каждой итерации проводим по 2 запроса, кроме одной итерации с 3 запросами, но после нее мы будем делать только по 1 запросу, поэтому суммарно выйдет не более $$$2 \cdot n$$$ запросов.

#include <iostream>
#include <vector>
#include <string>
#include <array>
 
using namespace std;
 
bool ask(string t) {
    cout << "? " << t << endl;
    int res;
    cin >> res;
    return res;
}
 
void result(string s) {
    cout << "! " << s << endl;
}
 
void solve() {
    int n;
    cin >> n;
    string cur;
    while (cur.size() < n) {
        if (ask(cur + "0")) {
            cur += "0";
        } else if (ask(cur + "1")) {
            cur += "1";
        } else {
            break;
        }
    }
    while ((int) cur.size() < n) {
        if (ask("0" + cur)) {
            cur = "0" + cur;
        } else{
            cur = "1" + cur;
        }
    }
    result(cur);
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
}

Пусть $$$g$$$ будет наибольшим общим делителем массива $$$a$$$, поделим каждый $$$a_i$$$ на $$$g$$$, в конце просто умножим на g.

Рассмотрим следующий жадный алгоритм, создадим изначально пустой массив $$$b$$$, будем добавлять в конец массива $$$b$$$ элемент который минимизирует НОД массив $$$b$$$. Можно заметить, что НОД через максимум 10 итераций станет равным 1, после этого можно в любом порядке поставить оставшиеся элементы.

Временная сложность $$$O(n \cdot 10)$$$.

#include <bits/stdc++.h>

using namespace std;

int a[200200];
int n;

void solve(){
    cin >> n;
    int g = 0, cur = 0;
    long long ans = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        g = __gcd(g, a[i]);
    }
    for(int i=0;i<n;i++){
        a[i] /= g;
    }
    for(int t=0;t<n;t++){
        int nc = 1e9;
        for(int i=0;i<n;i++){
            nc = min(nc, __gcd(cur, a[i]));
        }
        cur = nc;
        ans += cur;
        if(cur == 1) {
            ans += n - t - 1;
            break;
        }
    }
    cout << ans * g << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
     cin >> t;
    while(t--){
        solve();
    }
}

Сначала поймем как будет проходить игра, Алиса и Боб будут идти к друг-другу. Но в какой-то момент один из игроков спускается вниз в поддерево вершины, которое не лежит на пути $$$(1, u)$$$, после этого оба игрока идут в самую дальнюю доступную вершину.

Пусть $$$(p_1, p_2, \cdots, p_m)$$$, это путь от $$$(1, u)$$$. Изначально Алиса стоит в вершине $$$p_1$$$, а Боб в $$$p_m$$$ соответственно. Для каждой вершины на пути посчитаем два значения, $$$a_i$$$ — это количество вершин которые посетит Алиса если она спуститься вниз в поддерево на вершине $$$p_i$$$, $$$b_i$$$ то же самое значение для Боба. Обозначим расстояние до самой дальней вершины в поддереве $$$v$$$, которая не лежит на пути $$$(1, u)$$$ за $$$d_v$$$. То тогда $$$a_i = d_{p_i} + i, b_i = d_{p_i} + m - i + 1$$$. Пусть Алиса сейчас стоит на вершине $$$p_i$$$, а Боб на вершине $$$p_j$$$ соответственно. Если Алиса сейчас спуститься в поддерево вершины $$$p_i$$$ то она посетит $$$a_i$$$ вершин, а Боб может пойти до любой вершины на подотрезке $$$(p_i, p_{i+1}, \ldots, p_j)$$$, Бобу выгодно спуститься вниз на вершине с максимальным значением $$$b_i$$$ на подотрезке $$$(p_i, p_j)$$$. Следовательно, Алиса выгодно спуститься вниз на вершине $$$p_i$$$, если $$$a_i > max(b_{i+1}, b_{i+2}, \ldots, b_j)$$$, иначе она переходит на вершину $$$p_{i+1}$$$. Случай для Боба решается аналогично.

Максимум на подотрезке можно находить с помощью дерева отрезков или разреженной таблицой. Временная сложность $$$O(nlogn)$$$.

Можно доказать, что если вместо дерево отрезков пробегаться по всем вершинам на подотрезке, и если нашлась вершина больше то брейкать фор, это будет работать за $$$O(n)$$$ по времени.

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 12;

vector<int> g[maxn];
vector<int> ord;
int dp[maxn];
int n, m, k;

bool calc(int v, int p, int f){
    bool is = 0;
    if(v == f) is = 1;
    dp[v] = 1;
    for(int to:g[v]){
        if(to == p){
            continue;
        }
        bool fg = calc(to, v, f);
        is |= fg;
        if(fg == 0){
            dp[v] = max(dp[v], dp[to] + 1);
        }
    }
    if(is){
        ord.push_back(v);
    }
    return is;
}

struct segtree {
    int t[maxn * 4];
    void build (int v, int tl, int tr, vector <int>& a) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build (v * 2, tl, tm, a);
        build (v * 2 + 1, tm + 1, tr, a);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
    int get (int v, int tl, int tr, int l, int r) {
        if (tr < l || r < tl) return 0;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
    }
} st_a, st_b;

int get(int v){
    ord.clear();
    calc(1, 0 , v);
    int m = ord.size();
    reverse(ord.begin(), ord.end());
    vector<int> a(m), b(m);
    for(int i=0;i<m;i++){
        a[i] = dp[ord[i]] + i;
        b[i] = dp[ord[m - i - 1]] + i;
    }
    st_a.build(1, 0, m-1, a);
    st_b.build(1, 0, m-1, b);
    for(int i=0;i < (m + 1) / 2;i++){
        if(a[i] > st_b.get(1, 0, m-1, i, m - i - 2)){
            return 1;
        }
        if(b[i] >= st_a.get(1, 0, m-1, i + 1, m - i - 2)){
            return 0;
        }
    }
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        g[i].clear();
    }
    for(int i=1;i<n;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int u, v;
    cin >> u >> v;
    ord.clear();
    calc(v, 0, u);
    auto p = ord;
    for(int x:p){
        if(get(x) == 1){
            cout << "Alice\n";
        }
        else{
            cout << "Bob\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

int dfs(int v, int p, int to, const vector<vector<int>> &g, vector<int> &max_depth) {
    int ans = 0;
    bool has_to = false;
    for (int i : g[v]) {
        if (i == p) {
            continue;
        }
        int tmp = dfs(i, v, to, g, max_depth);
        if (tmp == -1) {
            has_to = true;
        } else {
            ans = max(ans, tmp + 1);
        }
    }
    if (has_to || v == to) {
        max_depth.emplace_back(ans);
        return -1;
    } else {
        return ans;
    }
}

int solve(const vector<vector<int>> &g, int to) {
    vector<int> max_depth;
    dfs(0, -1, to, g, max_depth);
    int n = max_depth.size();
    reverse(max_depth.begin(), max_depth.end());
    int first = 0, second = n - 1;
    while (true) {
        {
            int value1 = max_depth[first] + first;
            bool valid = true;
            for (int j = second; j > first; --j) {
                if (value1 <= max_depth[j] + (n - j - 1)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return 0;
            }
            ++first;
            if (first == second) {
                return 1;
            }
        }
        {
            int value2 = max_depth[second] + (n - second - 1);
            bool valid = true;
            for (int j = first; j < second; ++j) {
                if (value2 < max_depth[j] + j) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return 1;
            }
            --second;
            if (first == second) {
                return 0;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    int s, f;
    cin >> s >> f;
    --s, --f;
    int ans = solve(g, s);
    if (ans == 0) {
        cout << "Alice\n";
    } else {
        cout << "Bob\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
        solve();
}

сигма

сигма