#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k, x = -1;
        cin >> n >> k;
        for (int i = 0; i <= n; i++) {
            if (i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k) {
                x = i;
            }
        }
        if (x == -1)
            cout << "NO\n";
        else {
            cout << "YES\n";
            for (int i = 0; i < n; i++) {
                if (i < x)
                    cout << 1 << ' ';
                else
                    cout << -1 << ' ';
            }
            cout << '\n';
        }
    }

    return 0;
}

for tt in range(int(input())):
    n, k = map(int, input().split())
    x = -1

    for i in range(0, n + 1):
        if i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k:
            x = i

    if x == -1:
        print("NO")
    else:
        print("YES")
        for i in range(0, n):
            if i < x:
                print("1 ", end = '')
            else:
                print("-1 ", end = '')
        print("")

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        vector <int> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            p[i]--;
        }

        int bad = 0;
        for (int i=0; i<n; i++) {
            if (p[i] % k != i % k) {
                bad++;
            }
        }

        if(bad == 0)
            cout << 0 << '\n';
        else if(bad == 2)
            cout << 1 << '\n';
        else
            cout << -1 << '\n';
    }

    return 0;
}

for tt in range(int(input())):
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    for i in range(0, n):
        p[i] -= 1

    bad = 0
    for i in range(0, n):
        if p[i] % k != i % k:
            bad += 1

    if bad == 0:
        print(0)
    elif bad == 2:
        print(1)
    else:
        print(-1)

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        map <int,int> a;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            for (int j = 2; j * j <= x; j++) {
                while (x % j == 0) {
                    x /= j;
                    a[j]++;
                }
            }
            if (x != 1) {
                a[x]++;
            }
        }

        int res = 0, rem = 0;

        for (pair <int, int> p : a) {
            int num = p.first;
            int cnt = p.second;
            res += cnt / 2;
            rem += cnt % 2;
        }

        res += rem / 3;
        cout << res << '\n';
    }

    return 0;
}

def is_prime(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

def is_strongly_composite(x):
    m = []
    i = 2
    while i * i <= x:
        while x % i == 0:
            x = x // i
            m.append(i)
        i += 1
    if not x == 1:
        m.append(i)
    return (len(m) >= 3 or (len(m) == 2 and m[0] == m[1]))

for tt in range(int(input())):
    n = int(input())
    lst = list(map(int, input().split()))
    a = {}
    for x in lst:
        i = 2
        while i * i <= x:
            while x % i == 0:
                x = x // i
                if i in a:
                    a[i] += 1
                else:
                    a[i] = 1
            i += 1
        if x != 1:
            if x in a:
                a[x] += 1
            else:
                a[x] = 1

    res, rem = 0, 0

    for num in a:
        cnt = a[num]
        res += cnt // 2
        rem += cnt % 2

    res += rem // 3
    print(res)

Изначально была более сложная версия этой задачи. Сможете ее решить?

Вам даны $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). Вы можете выполнить следующую операцию с массивом $$$a$$$ любое количество раз:

1. выбрать два индекса $$$i$$$ и $$$j$$$ ($$$i < j$$$);

2. удалить элементы $$$a_i$$$ и $$$a_j$$$ из $$$a$$$;

3. вставить элемент $$$a_i \cdot a_j$$$ в $$$a$$$.

После выполнения одной такой операции длина $$$a$$$ уменьшается на единицу.

Назовем массив $$$a$$$ хорошим, если он содержит только сильно составные числа.

Какое минимальное количество операций необходимо выполнить, чтобы сделать массив $$$a$$$ хорошим.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        vector <int> x(k), c(k);
        for (int i = 0; i < k; i++)
            cin >> x[i];
        for (int i = 0; i < k; i++)
            cin >> c[i];

        if (c[0] < 3 || c[0] > x[0]) {
            cout << "NO\n";
            continue;
        }

        string s;

        char cur = 'a';
        for (int i = 0; i < c[0] - 3; i++)
            s.push_back('a');

        for (int i = c[0] - 3; i < x[0]; i++) {
            s.push_back(cur);
            cur++;
            if (cur == 'd') cur = 'a';
        }

        bool good = true;
        for (int j = 1; j < k; j++) {
            int dx = x[j] - x[j - 1];
            int dc = c[j] - c[j - 1];
            if (dc > dx) {
                good = false;
                break;
            }

            for (int i = 0; i < dc; i++)
                s.push_back('c' + j);
            for (int i = dc; i < dx; i++) {
                s.push_back(cur);
                cur++;
                if (cur == 'd') cur = 'a';
            }
        }

        if (good)
            cout << "YES" << endl << s << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

for tt in range(int(input())):
    n, k = map(int, input().split())
    x = list(map(int, input().split()))
    c = list(map(int, input().split()))

    if c[0] < 3 or c[0] > x[0]:
        print("NO")
        continue

    s = ""
    cur = 'a'

    for i in range(0, c[0] - 3):
        s += "a"

    for i in range(c[0] - 3, x[0]):
        s += cur
        cur = chr(ord(cur) + 1)
        if cur == 'd':
            cur = 'a'

    good = True
    for j in range(1, k):
        dx = x[j] - x[j - 1]
        dc = c[j] - c[j - 1]
        if dc > dx:
            good = False
            break

        for i in range(0, dc):
            s += chr(ord('c') + j)
        for i in range(dc, dx):
            s += cur
            cur = chr(ord(cur) + 1)
            if cur == 'd':
                cur = 'a'

    if good:
        print("YES")
        print(s)
    else:
        print("NO")

Изначально была упрощенная версия этой задачи с $$$k = 1$$$, но она совпала с другой задачей.

А как в этой задаче работает чекер?

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, l, r;
    cin >> n >> l >> r;
    vector < vector <int> > g(n);
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int res=0, size;
    vector <int> used(n);

    function <void(int)> dfs = [&] (int v) {
        used[v] = true;
        size++;
        for (int to : g[v]) {
            if (!used[to])
                dfs(to);
        }
    };

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            size = 0;
            dfs(i);
            if (size <= l + r - 1) {
                res ^= size / l;
            }
        }
    }

    if (res)
        cout << "Alice\n";
    else
        cout << "Bob\n";

    return 0;
}

from sys import setrecursionlimit
import threading

def main():
    n, l, r = map(int, input().split())

    g = [[] for i in range(0, n)]
    for i in range(0, n):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    res = 0
    used = [False for i in range(0, n)]

    def dfs(v):
        used[v] = True
        size = 1
        for to in g[v]:
            if not used[to]:
                size += dfs(to)
        return size

    for i in range(0, n):
        if not used[i]:
            size = dfs(i)
            if size <= l + r - 1:
                res ^= size // l

    if res:
        print("Alice")
    else:
        print("Bob")

setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, s, t;
    cin >> n >> s >> t;
    s--, t--;

    vector < vector <int> > g(n);
    vector <int> previous(n, -1);
    vector <int> inPath(n);
    vector <int> res(n);

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    function <void (int, int)> dfs = [&] (int v, int p) {
        for (int to : g[v]) {
            if (to == p) continue;
            previous[to] = v;
            dfs(to, v);
        }
    };

    function <void (int, int, int)> dfs2 = [&] (int v, int p, int k) {
        res[v] = k * (int)g[v].size();
        for (int to : g[v]) {
            if (to == p) continue;
            dfs2(to, v, k);
        }
    };

    dfs(s, -1);

    int ptr = t;
    inPath[t] = true;

    while (ptr != s) {
        res[previous[ptr]] = res[ptr] + 2;
        ptr = previous[ptr];
        inPath[ptr] = true;
    }

    for (int v = 0; v < n; v++) {
        if (inPath[v]) {
            res[v] = res[v] / 2 * (int)g[v].size();
            for (int to : g[v]) {
                if (!inPath[to]) {
                    dfs2(to, v, res[v] / (int)g[v].size());
                }
            }
        }
    }

    res[t]++;

    for (int i : res)
        cout << i << ' ';
    cout<<'\n';

    return 0;
}

from sys import setrecursionlimit
import threading

def main():
    n, s, t = map(int, input().split())
    s -= 1
    t -= 1

    g = [[] for i in range(0, n)]
    previous = [-1 for i in range(0, n)]
    inPath = [False for i in range(0, n)]
    res = [0 for i in range(0, n)]

    for i in range(0, n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    def dfs(v, p):
        for to in g[v]:
            if to == p:
                continue
            previous[to] = v
            dfs(to, v)

    def dfs2(v, p, k):
        res[v] = k * len(g[v])
        for to in g[v]:
            if to == p:
                continue
            dfs2(to, v, k)

    dfs(s, -1)

    ptr = t
    inPath[t] = True

    while ptr != s:
        res[previous[ptr]] = res[ptr] + 2
        ptr = previous[ptr]
        inPath[ptr] = True

    for v in range(0, n):
        if inPath[v]:
            res[v] = res[v] // 2 * len(g[v])
            for to in g[v]:
                if not inPath[to]:
                    dfs2(to, v, res[v] // len(g[v]))

    res[t] += 1

    for i in res:
        print(i, end = ' ')
    print("")

setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()