#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<string> carpet(n);
        for (int i = 0; i < n; ++i) {
            cin >> carpet[i];
        }
        string vika = "vika";
        int fnd = 0;
        for (int i = 0; i < m; ++i) {
            bool check = false;
            for (int j = 0; j < n; ++j) {
                if (carpet[j][i] == vika[fnd]) {
                    check = true;
                }
            }
            if (check) {
                ++fnd;
                if (fnd == 4) {
                    break;
                }
            }
        }
        if (fnd == 4) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        vector<int> a;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            if (i && a.back() > x) {
                a.push_back(1);
            }
            a.push_back(x);
        }
        cout << a.size() << "\n";
        for (int el : a)
            cout << el << " ";
        cout << "\n";
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        if (a[1] != n) {
            cout << "NO" << '\n';
            continue;
        }
        vector<int> b;
        for (int i = n; i >= 1; i--) {
            while (b.size() < a[i]) {
                b.push_back(i);
            }
        }
        bool meow = true;
        for (int i = 1; i <= n; i++) {
            if (a[i] != b[i - 1]) {
                cout << "NO" << '\n';
                meow = false;
                break;
            }
        }
        if (meow) {
            cout << "YES" << '\n';
        }
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        int l = 0, r = min<int>(2e9, 2 * n);
        while (r - l > 1) {
            int m = (l + r) >> 1;
            // m = x + y, answer = x + 2 * y
            if (m * (m - 1) / 2 + m < n) {
                l = m;
            } else {
                r = m;
            }
        }
        int y = n - r * (r - 1) / 2;
        if ((r + 1) * r / 2 <= n) {
            cout << min(r + y, r + 1 + n - (r + 1) * r / 2) << "\n";
        } else {
            cout << r + y << "\n";
        }
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n, m, d;
        cin >> n >> m >> d;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        int ans = 0;
        set<pair<int, int>> s;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            int cur = sum + a[i] - d * (i + 1);
            ans = max(ans, cur);
            if (a[i] > 0) {
                s.insert({a[i], i});
                sum += a[i];
                if (s.size() >= m) {
                    sum -= (s.begin()->first);
                    s.erase(s.begin());
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int w, f, n;
        cin >> w >> f >> n;
        vector<int> s(n);
        int sum_s = 0;
        for (int i = 0; i < n; ++i) {
            cin >> s[i];
            sum_s += s[i];
        }
        vector<bool> dp(sum_s + 1);
        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int w = sum_s; w - s[i] >= 0; --w) {
                dp[w] = dp[w] || dp[w - s[i]];
            }
        }
        int ans = 2e9;
        for (int i = 0; i <= sum_s; ++i) {
            if (dp[i]) {
                ans = min(ans, max((i + w - 1) / w, (sum_s - i + f - 1) / f));
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        if (n == 1) {
            int q;
            scanf("%d", &q);
            while (q--) {
                int pos, val;
                scanf("%d %d", &pos, &val);
                cout << val << " ";
            }
            cout << "\n";
            continue;
        }
        multiset<int> aset;
        for (int i = 0; i < n; ++i) {
            aset.insert(a[i]);
        }
        multiset<int> deltas;
        for (auto it = ++aset.begin(); it != aset.end(); ++it) {
            auto prev = it;
            --prev;
            deltas.insert(*it - *prev);
        }
        int q;
        scanf("%d", &q);
        while (q--) {
            int pos, val;
            scanf("%d %d", &pos, &val);
            auto it = aset.find(a[pos - 1]);
            auto nxt = it, prev = it;
            ++nxt; --prev;
            if (it == aset.begin()) {
                deltas.erase(deltas.find(*nxt - *it));
            } else if (it == --aset.end()) {
                deltas.erase(deltas.find(*it - *prev));
            } else {
                deltas.erase(deltas.find(*nxt - *it));
                deltas.erase(deltas.find(*it - *prev));
                deltas.insert(*nxt - *prev);
            }
            aset.erase(it);
            aset.insert(val);
            it = aset.find(val);
            nxt = it, prev = it;
            ++nxt; --prev;
            if (it == aset.begin()) {
                deltas.insert(*nxt - *it);
            } else if (it == --aset.end()) {
                deltas.insert(*it - *prev);
            } else {
                deltas.insert(*nxt - *it);
                deltas.insert(*it - *prev);
                deltas.erase(deltas.find(*nxt - *prev));
            }
            a[pos - 1] = val;
            cout << *--aset.end() + *--deltas.end() << " ";
        }
        cout << "\n";
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        int x, y;
        cin >> x >> y;
        string ans = "YES\n";
        for (int i = 0; i < k; ++i) {
            int xx, yy;
            cin >> xx >> yy;
            if ((x + y) % 2 == (xx + yy) % 2) {
                ans = "NO\n";
            }
        }
        cout << ans;
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> c(n);
        for (int i = 0; i < n; ++i) {
            cin >> c[i];
        }
        vector<int> last(k, -1);
        vector<int> max_step(k), max2_step(k);
        for (int i = 0; i < n; ++i) {
            int step = i - last[c[i] - 1];
            if (step > max_step[c[i] - 1]) {
                max2_step[c[i] - 1] = max_step[c[i] - 1];
                max_step[c[i] - 1] = step;
            } else if (step > max2_step[c[i] - 1]) {
                max2_step[c[i] - 1] = step;
            }
            last[c[i] - 1] = i;
        }
        for (int i = 0; i < k; ++i) {
            int step = n - last[i];
            if (step > max_step[i]) {
                max2_step[i] = max_step[i];
                max_step[i] = step;
            } else if (step > max2_step[i]) {
                max2_step[i] = step;
            }
        }
        int ans = 1e9;
        for (int i = 0; i < k; ++i) {
            ans = min(ans, max((max_step[i] + 1) / 2, max2_step[i]));
        }
        cout << ans - 1 << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int gcd(int a, int b) {
    if (a == 0) {
        return 0;
    }
    if (b == 0) {
        return 1;
    }
    if (a >= b) {
        int r = a % b;
        int k = a / b;
        if (k % 2 == 1) {
            return gcd(b, r) + k + k / 2;
        } else {
            return gcd(r, b) + k + k / 2;
        }
    }
    return 1 + gcd(b, abs(a - b));
}
 
int calc(int a, int b) {
    if (a == 0) {
        return 0;
    }
    if (b == 0) {
        return 1;
    }
    return 1 + calc(b, abs(a - b));
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<int> b(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
        }
        set<int> cnt;
        for (int i = 0; i < n; ++i) {
            if (a[i] == 0 && b[i] == 0) {
                continue;
            }
            cnt.insert(gcd(a[i], b[i]) % 3);
        }
        if (cnt.size() <= 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int f(int s, int k) {
    // (s + 20x) * (k - 4x)
    // (-80)x^2 + (20k - 4s)x + (sk)
    // -b/2a = (5k-s)/40
    int x = (5 * k - s) / 40;
    x = min(x, k / 4);
    int res = s * k;
    if (x > 0) {
        res = max(res, (s + 20 * x) * (k - 4 * x));
    }
    x = min(x + 1, k / 4);
    if (x > 0) {
        res = max(res, (s + 20 * x) * (k - 4 * x));
    }
    return res;
}
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int s, k;
        cin >> s >> k;
        int ans = s * k;
        if (s % 10 == 5) {
            ans = max(ans, (s + 5) * (k - 1));
        } else if (s % 10) {
            if (s % 2 == 1) {
                s += s % 10;
                --k;
            }
            for (int i = 0; i < 4; ++i) {
                if (k > 0) {
                    ans = max(ans, f(s, k));
                }
                s += s % 10;
                --k;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int K = 1e6;
 
#define int long long
 
int mod;
 
int dp[K + 1];
int cnt[K + 1];
 
const int MM = 3e6 + 7;
 
int inv[MM];
 
int cc = 0;
 
int mul(int a, int b) {
    int bb = b;
    while (bb % mod == 0) {
        ++cc;
        bb /= mod;
    }
    return (a * (bb % mod)) % mod;
}
 
int dv(int a, int b) {
    int bb = b;
    while (bb % mod == 0) {
        --cc;
        bb /= mod;
    }
    return (a * inv[bb % mod]) % mod;
}
 
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int x, q;
    cin >> x >> q >> mod;
    inv[1] = 1;
    for (int i = 2; i < MM && i < mod; i++) {
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
    }
    int y = x;
    for (int i = 3; i <= K; i += 2) {
        if (dp[i]) {
            continue;
        }
        for (int j = i; j <= K; j += 2 * i) {
            dp[j] = i;
        }
    }
    int ans = 1;
    while (x % 2 == 0) {
        x /= 2;
    }
    for (int i = 3; i <= K; i += 2) {
        while (x % i == 0) {
            ans = dv(ans, cnt[i] + 1);
            ++cnt[i];
            ans = mul(ans, cnt[i] + 1);
            x /= i;
        }
    }
    int f = 1;
    if (x > 1) {
        ans = mul(ans, 2);
    }
    x = y;
    for (int i = 0; i < q; ++i) {
        int d;
        cin >> d;
        while (d % 2 == 0) {
            d /= 2;
        }
        int k = d;
        while (dp[k]) {
            ans = dv(ans, cnt[dp[k]] + 1);
            ++cnt[dp[k]];
            ans = mul(ans, cnt[dp[k]] + 1);
            k /= dp[k];
        }
        if (cc) {
            cout << 0 << '\n';
        } else {
            cout << ans << '\n';
        }
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = (1 << 20);
 
int a[MAXN];
 
int solve(int n) {
    if (n == 1) {
        if (a[0] == 0) {
            return 0;
        } else {
            return 1;
        }
    }
    int fl = true;
    for (int i = 0; i < n / 2; ++i) {
        if (a[i] != a[i + n / 2]) {
            fl = false;
        }
    }
    if (fl) {
        return solve(n / 2);
    }
    for (int i = 0; i < n / 2; ++i) {
        a[i] ^= a[i + n / 2];
    }
    return n / 2 + solve(n / 2);
}
 
int32_t main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    cout << solve(n) << endl;
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        int i = 0;
        while (i < n) {
            int start = i;
            cout << s[i++];
            while (s[i++] != s[start]);
        }
        cout << endl;
    }
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        k = min(k, 30);
        cout << min(n, (1 << k) - 1) + 1 << "\n";
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

testCases = int(input())
 
for testCase in range(testCases):
    n, k, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    
    ans = 0
    len = 0
    for i in range(n):
        if a[i] <= q:
            len += 1
        else:
            if len >= k:
                ans += (len - k + 1) * (len - k + 2) // 2
            len = 0
    
    if len >= k:
        ans += (len - k + 1) * (len - k + 2) // 2
    print(ans)

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        int l = -1, r = 1e9;
        while (r - l > 1) {
            int m = (l + r) >> 1;
            int i = 0;
            while (i + 1 < a.size() && a[i + 1] - a[0] <= 2 * m) {
                ++i;
            }
            int j = n - 1;
            while (j - 1 >= 0 && a.back() - a[j - 1] <= 2 * m) {
                --j;
            }
            ++i; --j;
            if (i > j || a[j] - a[i] <= 2 * m) {
                r = m;
            } else {
                l = m;
            }
        }
        cout << r << "\n";
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int x;
    cin >> x;
    while (x--) {
        vector<string> s(2);
        cin >> s[0] >> s[1];
        int n = s[0].size();
        int bad = 0;
        for (int i = 0; i < n; ++i) {
            if (s[0][i] != s[1][i]) {
                ++bad;
            }
        }
        int t, q;
        cin >> t >> q;
        queue<pair<int, int>> unblock;
        for (int i = 0; i < q; ++i) {
            while (!unblock.empty() && unblock.front().first == i) {
                if (s[0][unblock.front().second] != s[1][unblock.front().second]) {
                    ++bad;
                }
                unblock.pop();
            }
            int type;
            cin >> type;
            if (type == 1) {
                int pos;
                cin >> pos;
                if (s[0][pos - 1] != s[1][pos - 1]) {
                    --bad;
                }
                unblock.emplace(i + t, pos - 1);
            } else if (type == 2) {
                int num1, pos1, num2, pos2;
                cin >> num1 >> pos1 >> num2 >> pos2;
                --num1; --pos1; --num2; --pos2;
                if (s[num1][pos1] != s[1 ^ num1][pos1]) {
                    --bad;
                }
                if (s[num2][pos2] != s[1 ^ num2][pos2]) {
                    --bad;
                }
                swap(s[num1][pos1], s[num2][pos2]);
                if (s[num1][pos1] != s[1 ^ num1][pos1]) {
                    ++bad;
                }
                if (s[num2][pos2] != s[1 ^ num2][pos2]) {
                    ++bad;
                }
            } else {
                cout << (!bad ? "YES" : "NO") << "\n";
            }
        }
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        int r;
        cin >> r;
        bool free[n + 1][m + 1][r + 1];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= r; ++k) {
                    free[i][j][k] = true;
                }
            }
        }
        for (int i = 0; i < r; ++i) {
            int t, d, coord;
            cin >> t >> d >> coord;
            if (d == 1) {
                for (int j = 0; j <= m; ++j) {
                    if (0 <= t - coord - j && t - coord - j <= r) {
                        free[coord][j][t - coord - j] = false;
                    }
                }
            } else {
                for (int j = 0; j <= n; ++j) {
                    if (0 <= t - coord - j && t - coord - j <= r) {
                        free[j][coord][t - coord - j] = false;
                    }
                }
            }
        }
        bool dp[n + 1][m + 1][r + 1];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= r; ++k) {
                    dp[i][j][k] = !(i || j || k);
                    if (free[i][j][k]) {
                        if (i && dp[i - 1][j][k]) {
                            dp[i][j][k] = true;
                        }
                        if (j && dp[i][j - 1][k]) {
                            dp[i][j][k] = true;
                        }
                        if (k && dp[i][j][k - 1]) {
                            dp[i][j][k] = true;
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int t = r; t >= 0; --t) {
            if (dp[n][m][t]) {
                ans = n + m + t;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int MAXN = 1e6 + 7;
 
int pos[MAXN];
 
int32_t main() {
    int num;
    cin >> num;
    int ans = 0;
    int cur = 1;
    pos[num] = 1;
    for (int i = 0; i < 1000; ++i) {
        cout << '+' << " " << 1 << endl;
        ++cur;
        cin >> num;
        if (pos[num]) {
            cout << '!' << " " << cur - pos[num] << endl;
            return 0;
        }
        pos[num] = cur;
    }
    while (true) {
        cout << '+' << " " << 1000 << endl;
        cur += 1000;
        cin >> num;
        if (pos[num]) {
            cout << '!' << " " << cur - pos[num] << endl;
            return 0;
        }
        pos[num] = cur;
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int MAXN = 1e6 + 7;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int pos[MAXN];
 
const int K = 400;
const int T = 300;
 
int get() {
    return rng() % MAXN;
}
 
int32_t main() {
    int num;
    cin >> num;
    int start = num;
    int cur_delta = 0;
    int N0 = num;
    for (int i = 0; i < K; ++i) {
        int delta = get();
        cout << '+' << " " << delta << endl;
        cur_delta += delta;
        cin >> num;
        N0 = max(N0, num);
    }
    cout << '-' << " " << cur_delta << endl;
    cin >> num;
    cout << '+' << " " << N0 - 1 << endl;
    cur_delta = N0 - 1;
    cin >> num;
    pos[num] = N0;
    for (int i = 0; i < T; ++i) {
        ++cur_delta;
        cout << '+' << " " << 1 << endl;
        cin >> num;
        pos[num] = N0 + i + 1;
        if (num == start) {
            cout << '!' << " " << N0 + i << endl;
            return 0;
        }
    }
    cout << '-' << " " << cur_delta << endl;
    cin >> num;
    int ans = 0;
    while (true) {
        cout << '-' << " " << T << endl;
        ans += T;
        cin >> num;
        if (pos[num]) {
            cout << '!' << " " << ans + pos[num] - 1 << endl;
            return 0;
        }
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

def solve():
    n, t = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    bst = -2
    for i in range(n):
        if i + a[i] <= t and (bst == -2 or b[bst] < b[i]):
            bst = i
    print(bst + 1)
 
 
t = int(input())
for _ in range(t):
    solve()

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

t = int(input())
 
for testCase in range(t):
    n = int(input())
    a = list(map(int, input().split(' ')))
    a.sort()
    print(max(a[0] * a[1], a[-1] * a[-2]))

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        cout << ((n + 1) * n) + n + 2 << "\n";
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>

using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        if (n == 1) {
            cout << "1\n";
            continue;
        }
        if (n % 2) {
            cout << "-1\n";
        } else {
            for (int i = 0; i < n; ++i) {
                if (i % 2) {
                    cout << i << " ";
                } else {
                    cout << n - i << " ";
                }
            }
            cout << "\n";
        }
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>

using namespace std;

void solve(int n, string & s) {
    if (n % 2 == 1) {
        cout << -1 << endl;
        return;
    }
    vector<int> cnt(26);
    for (int i = 0; i < n; ++i) {
        ++cnt[s[i] - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
        if (cnt[i] * 2 > n) {
            cout << -1 << endl;
            return;
        }
    }
    int pairs = 0;
    vector<int> cnt_pairs(26);
    for (int i = 0; i * 2 < n; ++i) {
        if (s[i] == s[n - i - 1]) {
           ++pairs;
           ++cnt_pairs[s[i] - 'a'];
        }
    }
    for (int i = 0; i < 26; ++i) {
        if (cnt_pairs[i] * 2 > pairs) {
            cout << cnt_pairs[i] << endl;
            return;
        }
    }
    cout << (pairs + 1) / 2 << endl;
}

int32_t main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        solve(n, s);
    }
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include<bits/stdc++.h>

using namespace std;

struct Value {
    int64_t value = 0;
    int vertex = 0;
};

vector<vector<int>> nei;
vector<vector<int>> depth_vertex;
vector<int> depth;
vector<int> parent;

void dfs(int v, int p = -1, int cnt = 0) {
    depth_vertex[cnt].push_back(v);
    depth[v] = cnt;
    parent[v] = p;
    for (int u : nei[v]) {
        if (u == p) continue;
        dfs(u, v, cnt + 1);
    }
}

void solve() {
    int n, root = 1;
    int64_t k_wei, cost;
    cin >> n >> k_wei >> cost;

    nei.clear();
    nei.resize(n + 1);
    depth_vertex.clear();
    depth_vertex.resize(n + 1);
    depth.clear();
    depth.resize(n + 1);
    parent.clear();
    parent.resize(n + 1);

    for (int _ = 0; _ < n - 1; ++_) {
        int u, v;
        cin >> u >> v;
        nei[u].push_back(v);
        nei[v].push_back(u);
    }

    dfs(root);

    vector<pair<Value, Value>> down(n + 1);

    for (int tin = n; tin >= 0; --tin) {
        for (int v : depth_vertex[tin]) {
            for (int u : nei[v]) {
                if (u == parent[v]) continue;
                if (down[u].first.value + 1 > down[v].first.value) {
                    down[v].first.value = down[u].first.value + 1;
                    down[v].first.vertex = u;
                }
            }
            for (int u : nei[v]) {
                if (u == parent[v] || u == down[v].first.vertex) continue;
                if (down[u].first.value + 1 > down[v].second.value) {
                    down[v].second.value = down[u].first.value + 1;
                }
            }
        }
    }

    vector<int64_t> up(n + 1, 0);

    for (int tin = 1; tin <= n; ++tin) {
        for (int v : depth_vertex[tin]) {
            int p = parent[v];
            up[v] = up[p] + 1;
            if (down[p].first.vertex == v) {
                up[v] = max(up[v], down[p].second.value + 1);
            } else {
                up[v] = max(up[v], down[p].first.value + 1);
            }
        }
    }

    int64_t ans = -1'000'000'000'000'000'002;

    for (int v = 1; v <= n; ++v) {
        ans = max(ans, k_wei * max(up[v], down[v].first.value) - cost * int64_t(depth[v]));
    }

    cout << ans << endl;

}

int main()
{
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAX_VAL = 1e6;

int cnt[MAX_VAL + 1];

int32_t main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            ++cnt[a[i]];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += (cnt[a[i]] - 1) * (cnt[a[i]] - 2);
            for (int b = 2; a[i] * b * b <= MAX_VAL; ++b) {
                ans += cnt[a[i] * b] * cnt[a[i] * b * b];
            }
        }
        cout << ans << "\n";
        for (int i = 0; i < n; ++i) {
            --cnt[a[i]];
        }
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int K = 1e6;
const int MAX_VAL = 1e9;

int32_t main() {
    int t;
    scanf("%d", &t);
    for (int _ = 0; _ < t; ++_) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        map<int, int> cnt;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            ++cnt[a[i]];
        }
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += (ll)(cnt[a[i]] - 1) * (cnt[a[i]] - 2);
        }
        for (auto el : cnt) {
            int num = el.first;
            int val = el.second;
            if (num > K) {
                for (int b = 2; b * num <= MAX_VAL; ++b) {
                    if (num % b == 0 && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
                        ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
                    }
                }
            } else {
                for (int b = 2; b * b <= num; ++b) {
                    if (num % b == 0) {
                        if ((ll)num * b <= (ll)MAX_VAL && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
                            ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
                        }
                        if (b * b != num) {
                            if ((ll)num * num / b <= (ll)MAX_VAL && cnt.find(b) != cnt.end() && cnt.find(num / b * num) != cnt.end()) {
                                ans += (ll)(cnt[b]) * (cnt[num / b * num]) * val;
                            }
                        }
                    }
                }
                if (num > 1 && (ll)num * num <= (ll)MAX_VAL && cnt.find(1) != cnt.end() && cnt.find(num * num) != cnt.end()) {
                    ans += (ll)(cnt[1]) * (cnt[num * num]) * val;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача