Статья Автор: Лебедев Дмитрий

Регион_2025_2 день

Задание 5 Разность квадратов
Решение от Федора - 4 мин 30 секунд

#include <bits/stdc++.h>


using namespace std;


using ll = long long;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll d, l, r;
    cin >> d >> l >> r;
    ll a = 1;
    ll res = 0;
    while (a * a <= d) {
        if (d % a == 0) {
            ll b = d / a;
            if ((a + b) % 2 == 0) {
                 ll x = (a + b) / 2;
                 ll y = b - x;
                 res += int(x > y && y * y >= l && x * x <= r);
            }
        }
        a++;
    }
    cout << res;
    return 0;
}

Задача 7
Решение от Федора

#include <bits/stdc++.h>


using namespace std;


using ll = long long;


template<typename T>
ostream & operator <<(ostream &os, const vector<T> &a) {
    for (T el : a) {
        os << el << " ";
    }
    os << '\n';
    return os;
}


void func(vector<vector<char>> &dp, const vector<ll> &w, vector<ll> &sums, ll s) {
    dp.at(0).at(0) = '1';
    for (int i = 1; i < int(w.size()); i++) {
        for (int c = 0; c <= s; c++) {
            ll mass = w.at(i);
            dp.at(i).at(c) = dp.at(i - 1).at(c);
            if (c - mass >= 0 && dp.at(i - 1).at(c - mass) == '1') {
                dp.at(i).at(c) = '1';
            }
        }
    }
    for (int i = 1; i <= s; i++) {
        if (dp.at(int(w.size()) - 1).at(i) == '1') {
            sums.push_back(i);
        }
    }
}


void recreate(vector<vector<char>> &dp, const vector<ll> &w, ll s, vector<char> &used) {
    int pos = int(w.size()) - 1;
    while (s > 0) {
        if (dp.at(pos - 1).at(s) == '1') {
            pos--;
        } else {
            s = s - w.at(pos);
            used.at(pos) = '1';
            pos--;
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, s;
    cin >> n >> s;
    vector<vector<ll>> sums(n + 1);
    vector<vector<ll>> w(n + 1);
    vector<vector<vector<char>>> f(n + 1);
    vector<vector<char>> used(n + 1);
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        w.at(i).resize(k + 1, 0);
        f.at(i).resize(k + 1, vector<char>(s + 1, '0'));
        used.at(i).resize(k + 1, '0');
        for (int j = 1; j <= k; j++) {
            cin >> w.at(i).at(j);
        }
        func(f.at(i), w.at(i), sums.at(i), s);
    }
    vector<vector<char>> dp(n + 1, vector<char>(s + 1, 0));
    dp.at(0).at(0) = '1';
    for (int i = 1; i <= n; i++) {
        for (ll mass = 0; mass <= s; mass++) {
            for (ll el : sums.at(i)) {
                if (dp.at(i).at(mass) == '1') {
                    break;
                }
                if (mass - el >= 0 && dp.at(i - 1).at(mass - el) == '1') {
                    dp.at(i).at(mass) = '1';
                }
            }
        }
    }

    if (dp.at(n).at(s) == '1') {
        cout << "Yes\n";
        for (int i = n; i >= 1; i--) {
            for (ll el : sums.at(i)) {
                if (s - el >= 0 && dp.at(i - 1).at(s - el) == '1') {
                    recreate(f.at(i), w.at(i), el, used.at(i));
                    s = s - el;
                    break;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            for (int j = 1; j < int(used.at(i).size()); j++) {
                cnt += int(used.at(i).at(j) == '1');
            }
            cout << cnt << '\n';
            for (int j = 1; j < int(used.at(i).size()); j++) {
                if (used.at(i).at(j) == '1') {
                    cout << j << " ";
                }
            }
            cout << '\n';
        }
    } else {
        cout << "No";
    }
    return 0;
}


/*2 4
1
2
2
2 1*/

Чтобы оставить комментарий нужна авторизация

Печать