Let's consider two cases:

• If $$$ x \geq y $$$. In this case, the blender will mix $$$ \min(y, c) $$$ fruits every second (where $$$ c $$$ is the number of unmixed fruits). Therefore, the answer will be $$$ \lceil \frac{n}{y} \rceil $$$.
• If $$$ x < y $$$. Here, the blender will mix $$$ \min(x, c) $$$ fruits every second. In this case, the answer will be $$$ \lceil \frac{n}{x} \rceil $$$, similarly.

Thus, the final answer is $$$ \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;
    }
}

It can be noted that the value of $$$ a_{n-1} $$$ will always be negative in the final result.

Therefore, we can subtract the sum $$$ a_1 + a_2 + \ldots + a_{n-2} $$$ from $$$ a_{n-1} $$$, and then subtract $$$ a_{n-1} $$$ from $$$ a_n $$$.

Thus, the final sum will be $$$ a_1 + a_2 + \ldots + a_{n-2} - a_{n-1} + a_n $$$. This value cannot be exceeded because $$$ a_{n-1} $$$ will always be negative.

#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();
    }
}

We will initially maintain an empty string $$$ t $$$ such that $$$ t $$$ appears as a substring in $$$ s $$$.

We will increase the string $$$ t $$$ by one character until its length is less than $$$ n $$$.

We will perform $$$ n $$$ iterations. In each iteration, we will check the strings $$$ t + 0 $$$ and $$$ t + 1 $$$. If one of them appears in $$$ s $$$ as a substring, we will add the appropriate character to the end of $$$ t $$$ and proceed to the next iteration.

If neither of these two strings appears in $$$ s $$$, it means that the string $$$ t $$$ is a suffix of the string $$$ s $$$. After this iteration, we will check the string $$$ 0 + t $$$. If it appears in $$$ s $$$, we will add $$$ 0 $$$ to $$$ t $$$; otherwise, we will add $$$ 1 $$$.

Thus, in each iteration, we perform 2 queries, except for one iteration in which we perform 3 queries. However, after this iteration, we will make only 1 query, so the total number of queries will not exceed $$$ 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();
}

First statement: if $$$ a_i > a_{i+1} $$$, then it is always beneficial to perform an operation at position $$$ i $$$. Therefore, the final array will be non-decreasing.

Second statement: if the array is non-decreasing, then performing operations is not advantageous.

We will maintain a stack that holds a sorted array. Each element in the stack will represent a pair $$$ (x, cnt) $$$, where $$$ x $$$ is the value and $$$ cnt $$$ is the number of its occurrences.

When adding $$$ a_i $$$ to the stack, we will keep track of the sum of the removed elements $$$ sum $$$ from the stack and their count $$$ cnt $$$. Initially, $$$ sum = a_i $$$ and $$$ cnt = 1 $$$. We will remove the last element from the stack while it is less than $$$ \frac{sum}{cnt} $$$. After that, we recalculate $$$ sum $$$ and $$$ cnt $$$. Then we add the pairs $$$ \left( \frac{sum}{cnt}, cnt - sum \mod cnt \right) $$$ and $$$\left( \frac{sum}{cnt} + 1, sum \mod cnt \right) $$$ to the stack.

The time complexity of the algorithm is $$$ O(n) $$$, since on each iteration, no more than 2 elements are added to the stack, and each element is removed at most once.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll a[200200];
int n;

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    stack<pair<ll, int>> s;
    for(int i=1;i<=n;i++){
        ll sum = a[i], cnt = 1;
        while(s.size() && s.top().first >= sum / cnt){
            sum += s.top().first * s.top().second;
            cnt += s.top().second;
            s.pop();
        }
        s.push({sum / cnt, cnt - sum % cnt});
        if(sum % cnt != 0){
            s.push({sum / cnt + 1, sum % cnt});
        }
    }
    ll mx = s.top().first;
    while(s.size() > 1){
        s.pop();
    }
    cout << mx - s.top().first << '\n';
}

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

Let $$$ g $$$ be the greatest common divisor $$$gcd$$$ of the array $$$ a $$$. We will divide each element $$$ a_i $$$ by $$$ g $$$, and at the end, simply multiply the result by $$$ g $$$.

Now, consider the following greedy algorithm. We will start with an initially empty array $$$ b $$$ and add to the end of array $$$ b $$$ the element that minimizes the GCD with the already existing array $$$ b $$$. It can be observed that the $$$gcd$$$ will reach 1 in at most 10 iterations. After that, the remaining elements can be added in any order.

Total time complexty: $$$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();
    }
}

First, let's understand how the game proceeds. Alice and Bob start moving toward each other along the path from vertex $$$ 1 $$$ to vertex $$$ u $$$. At some vertex, one of the players can turn into a subtree of a vertex that is not on the path $$$ (1, u) $$$. After this, both players go to the furthest accessible vertex.

Let the path from vertex ( 1 ) to vertex ( u ) be denoted as ( (p_1, p_2, \dots, p_m) ), where ( p_1 = 1 ) and ( p_m = u ). Initially, Alice is at vertex ( p_1 ) and Bob is at vertex ( p_m ).

For each vertex on the path ( (p_1, p_2, \dots, p_m) ), we define two values:

• ( a_i ) — the number of vertices that Alice will visit if she descends into the subtree of vertex ( p_i ) that does not lie on the path ( (1, u) );

• ( b_i ) — the number of vertices that Bob will visit if he descends into the subtree of vertex ( p_i ) that also does not lie on this path.

Let the distance to the furthest vertex in the subtree of vertex ( p_i ) be denoted as ( d_{p_i} ). Then:

• ( a_i = d_{p_i} + i ) — the number of vertices Alice can visit if she descends into the subtree at vertex ( p_i );

• ( b_i = d_{p_i} + m — i + 1 ) — the number of vertices Bob can visit if he descends into the subtree at vertex ( p_i ).

Now, consider what happens if Alice is at vertex ( p_i ) and Bob is at vertex ( p_j ). If Alice decides to descend into the subtree of vertex ( p_i ), she will visit ( a_i ) vertices. Meanwhile, Bob can reach any vertex on the segment ( (p_i, p_{i+1}, \dots, p_j) ). It is advantageous for Bob to descend into the subtree of the vertex with the maximum value of ( b_k ), where ( k \in [i+1, j] ).

Therefore, it is beneficial for Alice to descend into the subtree of vertex ( p_i ) if the following condition holds: [ a_i > \max(b_{i+1}, b_{i+2}, \dots, b_j) ] Otherwise, she should move to vertex ( p_{i+1} ).

The situation for Bob is similar: he will descend into the subtree of vertex ( p_j ) if the condition analogous to Alice's condition holds for him.

To efficiently find the maximum on the segment ( (p_{i+1}, \dots, p_j) ), one can use a segment tree or a sparse table. This allows finding the maximum in ( O(\log n) ) for each query, resulting in an overall time complexity of ( O(n \log n) ).

However, it can be proven that instead of using a segment tree or sparse table, one can simply iterate through all vertices on the segment and terminate the loop upon finding a greater vertex. This approach will yield a solution with a time complexity of $$$ 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();
}

Прочтите разбор простой версии задачи.

Путь $$$(u, v)$$$ можно разбить на два вертикальных пути $$$(1, u)$$$ и $$$(1, v)$$$, далее мы будем решать для вершин на пути $$$(1, u)$$$, путь $$$(1, v)$$$ решается аналогично.

Для каждой вершины на пути $$$(1, u)$$$, введем два значения.

• $$$fa_i$$$ — Первая вершина на которой победит Алиса, если спустится в поддерево, когда Боб начинает с вершины $$$p_i$$$.
• $$$fb_i$$$ — Первая вершина на который Победит Боб если спустится в поддерево, когда Боб начинает с вершины $$$p_i$$$.

Утверждение, Алисе выгодно спускаться в поддерево вершины $$$v$$$, только на каком-то подотерзке вершин с которых начинает Боб. Аналогичное утверждение выполняется и для Боба.

Теперь нужно для каждой вершины Алисы, определить отрезок на котором нам будет выгодно спускаться. Левая граница отрезка для вершины $$$p_i$$$, будет равна $$$2 \cdot i$$$, так как Алиса всегда будет на левой половине пути. Не трудно заметить, что правую границу отрезка можно находиться с помощью бинарного поиска.

Переопределим значение $$$b_i$$$, приравняем его к $$$d_{p_i} - i$$$. Чтобы проверить выгодно ли нам спускаться в поддереве для фиксированной середины $$$mid$$$, нам необходимо чтобы выполнялось следующее условие: $$$a_i > max(b_{i+1}, b_{i+2}, \ldots, b_{mid - i}) + mid$$$.

Обозначним за $$$(l_j, r_j)$$$, подотрезок на котором Алисе выгодно спуститься вниз, если Боб начнет с вершины $$$p_j$$$. Тогда значение $$$fa_i$$$ ,будет равно минимальной позиции $$$j$$$, на которой выполняется следующее условие: $$$l_j \leq i \leq r_j$$$, это можно находиться с использованием сета.

Значение $$$fb_i$$$, считается аналогично.

Алиса выигрывает на вершине $$$p_i$$$, если $$$fa_i \leq i - fb_i$$$, в противном случае побеждает Боб.

Для эффективного нахождения максимума на подотрезке, можно использовать разряженную таблицу. Также использование сетов и бинарных поисков дает нам временную сложность $$$O(nlogn)$$$.

#include <bits/stdc++.h>

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

vector<int> g[maxn], del[maxn], add[maxn];
vector<int> ord;
int ans[maxn];
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 sparse {
    int mx[20][200200], lg[200200];
    int n;
    void build(vector<int> &a){
        n = a.size();
        for(int i=0;i<n;i++){
            mx[0][i] = a[i];
        }
        lg[0] = lg[1] = 0;
        for(int i=2;i<=n;i++){
            lg[i] = lg[i/2] + 1;
        }
        for(int k=1;k<20;k++){
            for(int i=0;i + (1 << k) - 1 < n;i++){
                mx[k][i] = max(mx[k-1][i], mx[k-1][i + (1 << (k - 1))]);
            }
        }
    }
    int get (int l, int r) {
        if(l > r) return -1e9;
        int k = lg[r-l+1];
        return max(mx[k][l], mx[k][r - (1 << k) + 1]);
    }
} st_a, st_b;

void solve(int v){
    ord.clear();
    calc(1, 0, v);
    reverse(ord.begin(), ord.end());
    m = ord.size();
    vector<int> a(m+1), b(m+1);
    vector<int> fa(m+1, 1e9), fb(m+1, -1e9);
    for(int i=0;i<m;i++){
        a[i] = dp[ord[i]] + i;
        b[i] = dp[ord[i]] - i;
        del[i].clear();
        add[i].clear();
    }
    st_a.build(a);
    st_b.build(b);
    multiset<int> s;
    for(int i=1;i<m;i++){
        int pos = i;
        for(int l=i+1, r=m-1;l<=r;){
            int mid = l + r >> 1;
            if(st_b.get(i+1 , mid) + mid < a[i] - i){
                pos = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if(i < pos){
            add[min(m, 2 * i)].push_back(i);
            del[min(m, pos + i)].push_back(i);
        }
        for(int x:add[i]){
            s.insert(x);
        }
        if(s.size()) fa[i] = *s.begin();
        for(int x:del[i]){
            s.erase(s.find(x));
        }
    }
    s.clear();
    for(int i=0;i<=m;i++){
        add[i].clear();
        del[i].clear();
    }
    for(int i=1;i<m;i++){
        int pos = i;
        for(int l=1, r = i-1;l<=r;){
            int mid = l + r >> 1;
            if(st_a.get(mid, i-1) - mid + 1 <= b[i] + i){
                pos = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        pos--;
        if(pos >= 0){
            add[min(m, pos + i)].push_back(i);
            del[min(m, 2 * i - 1)].push_back(i);
        }
        for(int x:add[i]){
            s.insert(x);
        }
        if(s.size()) fb[i] = *s.rbegin();
        for(int x:del[i]){
            s.erase(s.find(x));
        }
    }
    for(int i=m-1;i>0;i--){
        b[i] = max(b[i+1] + 1, dp[ord[i]]);
        if(b[i] >= st_a.get(1, i-1)){
            fb[i] = i;
        }
        if(a[0] > max(st_b.get(1, i-1) + i, b[i])){
            fa[i] = 0;
        }
        ans[ord[i]] = 0;
        if(fa[i] <= i - fb[i]){
            ans[ord[i]] = 1;
        }
    }
}

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;
    solve(u), solve(v);
    ord.clear();
    calc(v, 0, u);
    auto p = ord;
    for(int x:p){
        if(ans[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();
    }
}