21.6 แบบฝึกหัด

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, budget;
    cin >> n >> budget;
    vector<int> price(n);
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
    int best = -1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int total = price[i] + price[j] + price[k];
                if (total <= budget && total > best) {
                    best = total;
                }
            }
        }
    }
    cout << best << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> effect(n, 0);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int t = 0; t < k; t++) {
            int lamp;
            cin >> lamp;
            effect[i] |= 1 << (lamp - 1);
        }
    }
    int all_on = (1 << m) - 1;
    int best = -1;
    for (int mask = 0; mask < (1 << n); mask++) {
        int lamps = 0;
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                lamps ^= effect[i];
            }
        }
        if (lamps == all_on) {
            int presses = __builtin_popcount(mask);
            if (best == -1 || presses < best) {
                best = presses;
            }
        }
    }
    cout << best << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> dist(n + 1, vector<int>(n + 1));
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            cin >> dist[i][j];
        }
    }
    vector<int> order(n);
    for (int i = 0; i < n; i++) {
        order[i] = i + 1;
    }
    int best = INT_MAX;
    do {
        int total = dist[0][order[0]];
        for (int i = 0; i + 1 < n; i++) {
            total += dist[order[i]][order[i + 1]];
        }
        best = min(best, total);
    } while (next_permutation(order.begin(), order.end()));
    cout << best << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long volume;
    cin >> volume;
    long long sizes = 0;
    long long best = LLONG_MAX;
    for (long long a = 1; a * a * a <= volume; a++) {
        for (long long b = a; a * b * b <= volume; b++) {
            if (volume % (a * b) == 0) {
                long long c = volume / (a * b);
                sizes++;
                best = min(best, 2 * (a * b + b * c + c * a));
            }
        }
    }
    cout << sizes << ' ' << best << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n;
vector<string> board;
bool col_used[12], diag1_used[23], diag2_used[23];
int ways = 0;

void place(int row)
{
    if (row == n) {
        ways++;
        return;
    }
    for (int c = 0; c < n; c++) {
        int d1 = row + c, d2 = row - c + n - 1;
        if (board[row][c] == '#' || col_used[c] || diag1_used[d1] || diag2_used[d2]) {
            continue;
        }
        col_used[c] = diag1_used[d1] = diag2_used[d2] = true;
        place(row + 1);
        col_used[c] = diag1_used[d1] = diag2_used[d2] = false;
    }
}

int main()
{
    cin >> n;
    board.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> board[i];
    }
    place(0);
    cout << ways << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int grid[6][6];

bool can_put(int r, int c, int d)
{
    for (int k = 0; k < 6; k++) {
        if ((k != c && grid[r][k] == d) || (k != r && grid[k][c] == d)) {
            return false;
        }
    }
    int top = r / 2 * 2, left = c / 3 * 3;
    for (int i = top; i < top + 2; i++) {
        for (int j = left; j < left + 3; j++) {
            if ((i != r || j != c) && grid[i][j] == d) {
                return false;
            }
        }
    }
    return true;
}

bool solve(int pos)
{
    if (pos == 36) {
        return true;
    }
    int r = pos / 6, c = pos % 6;
    if (grid[r][c] != 0) {
        return solve(pos + 1);
    }
    for (int d = 1; d <= 6; d++) {
        if (can_put(r, c, d)) {
            grid[r][c] = d;
            if (solve(pos + 1)) {
                return true;
            }
            grid[r][c] = 0;
        }
    }
    return false;
}

int main()
{
    for (int r = 0; r < 6; r++) {
        for (int c = 0; c < 6; c++) {
            cin >> grid[r][c];
        }
    }
    bool ok = true;
    for (int r = 0; r < 6; r++) {
        for (int c = 0; c < 6; c++) {
            if (grid[r][c] != 0 && !can_put(r, c, grid[r][c])) {
                ok = false;
            }
        }
    }
    if (!ok || !solve(0)) {
        cout << "NO\n";
        return 0;
    }
    for (int r = 0; r < 6; r++) {
        for (int c = 0; c < 6; c++) {
            cout << grid[r][c] << (c < 5 ? ' ' : '\n');
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int cap[3];
int total;
bool visited[101][101];
bool a_possible[101];
int states = 0;

void dfs(int a, int b)
{
    visited[a][b] = true;
    states++;
    a_possible[a] = true;
    int water[3] = {a, b, total - a - b};
    for (int from = 0; from < 3; from++) {
        for (int to = 0; to < 3; to++) {
            if (from == to) {
                continue;
            }
            int amount = min(water[from], cap[to] - water[to]);
            int next[3] = {water[0], water[1], water[2]};
            next[from] -= amount;
            next[to] += amount;
            if (!visited[next[0]][next[1]]) {
                dfs(next[0], next[1]);
            }
        }
    }
}

int main()
{
    int a, b, c;
    cin >> cap[0] >> cap[1] >> cap[2];
    cin >> a >> b >> c;
    total = a + b + c;
    dfs(a, b);
    cout << states << '\n';
    bool first = true;
    for (int x = 0; x <= cap[0]; x++) {
        if (a_possible[x]) {
            cout << (first ? "" : " ") << x;
            first = false;
        }
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long target;
vector<long long> weight;
vector<bool> used;

bool fill_bag(int bags_done, int start, long long load)
{
    if (bags_done == k - 1) {
        return true;
    }
    if (load == target) {
        return fill_bag(bags_done + 1, 0, 0);
    }
    long long last_failed = -1;
    for (int i = start; i < n; i++) {
        if (used[i] || weight[i] == last_failed || load + weight[i] > target) {
            continue;
        }
        used[i] = true;
        if (fill_bag(bags_done, i + 1, load + weight[i])) {
            return true;
        }
        used[i] = false;
        last_failed = weight[i];
        if (load == 0) {
            break;
        }
    }
    return false;
}

int main()
{
    cin >> n >> k;
    weight.resize(n);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
        total += weight[i];
    }
    sort(weight.rbegin(), weight.rend());
    used.assign(n, false);
    target = total / k;
    bool ok = total % k == 0 && weight[0] <= target && fill_bag(0, 0, 0);
    cout << (ok ? "YES" : "NO") << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> cost;
vector<vector<int>> cheapest_first;
vector<bool> taken;
long long best = LLONG_MAX;

long long optimistic_rest(int teacher)
{
    long long sum = 0;
    for (int t = teacher; t < n; t++) {
        for (int duty : cheapest_first[t]) {
            if (!taken[duty]) {
                sum += cost[t][duty];
                break;
            }
        }
    }
    return sum;
}

void go(int teacher, long long total)
{
    if (teacher == n) {
        best = min(best, total);
        return;
    }
    if (total + optimistic_rest(teacher) >= best) {
        return;
    }
    for (int duty : cheapest_first[teacher]) {
        if (!taken[duty]) {
            taken[duty] = true;
            go(teacher + 1, total + cost[teacher][duty]);
            taken[duty] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    cost.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }
    cheapest_first.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cheapest_first[i][j] = j;
        }
        sort(cheapest_first[i].begin(), cheapest_first[i].end(), [&](int a, int b) {
            return cost[i][a] < cost[i][b];
        });
    }
    taken.assign(n, false);
    go(0, 0);
    cout << best << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

vector<long long> all_sums(const vector<long long>& items)
{
    int m = items.size();
    vector<long long> sums(1 << m);
    for (int mask = 0; mask < (1 << m); mask++) {
        long long total = 0;
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                total += items[i];
            }
        }
        sums[mask] = total;
    }
    return sums;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long budget;
    cin >> n >> budget;
    vector<long long> first_half, second_half;
    for (int i = 0; i < n; i++) {
        long long price;
        cin >> price;
        if (i < n / 2) {
            first_half.push_back(price);
        } else {
            second_half.push_back(price);
        }
    }
    vector<long long> left = all_sums(first_half);
    vector<long long> right = all_sums(second_half);
    sort(right.begin(), right.end());
    long long ways = 0;
    for (long long x : left) {
        if (x <= budget) {
            ways += upper_bound(right.begin(), right.end(), budget - x) - right.begin();
        }
    }
    cout << ways << '\n';
    return 0;
}