Problema 1: Corrida no Supermercado

Analisando o gerador de dados do problema, fica evidente que a quantidade de itens disponíveis é sempre suficiente para suprir a demenda. Como a restrição de movimento permite apenas o transporte de itens da direita para a esquerda, a solução se resume a calcular, para cada intervalo entre as posições adjacentes, quantos itens precisam ser movidos através dele. A soma dessas contribuições resulta na resposta final.

O código processa os dados garantindo que o saldo de itens não se torne negativo (trocando a oferta e a demanda de posição, se necessário) e, em seguida, acumula o esforço de transporte necessário entre as posições.

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN = 1e7 + 5;
int supply[MAXN], demand[MAXN], total_items;
unsigned int current_seed;
unsigned int pseudo_rand() {
    current_seed = current_seed * 1103515245 + 12345;
    return (current_seed << 16) | ((current_seed >> 16) & 0xFFFF);
}
int main() {
    scanf("%d%d", &total_items, &current_seed);
    int balance = 0;
    for (int i = total_items; i >= 1; i--) {
        supply[i] = pseudo_rand() % 1000;
        demand[i] = pseudo_rand() % 1000;
        if (balance + (supply[i] - demand[i]) < 0) swap(supply[i], demand[i]);
        balance += (supply[i] - demand[i]);
    }
    ll carry_over = 0, total_effort = 0;
    for (int i = 1; i <= total_items; i++) {
        int diff = supply[i] - demand[i];
        total_effort += carry_over;
        if (diff > 0) carry_over = max(0LL, carry_over - diff);
        else carry_over -= diff;
    }
    printf("%lld", total_effort);
    return 0;
}

Problema 2: Cobertura de Intervalos

Definimos minOps[i] como o número mínimo de operações para cobrir todos os intervalos que terminam em ou antes de i, e ways[i] como a quantidade de esquemas correspondentes. Para cada posição inicial, se o ponto final mais próximo puder ser coberto, todos os intervalos a partir daquele ponto também poderão. Registramos isso como minRight[i].

Para a transição de estado, assumindo que o último ponto de término foi i, determinamos o próximo ponto de término. A posição i+1 é sempre alcançável, e o limite do intervalo transitável diminui para minRight[i+1], pois exceder isso deixaria pelo menos um intervalo descoberto. Iterativamente, atualizamos o limite alcançável tomando o mínimo entre o limite atual e minRight[j].

A resposta é determinada examinando as posições entre o máximo l e o máximo r de todos os intervalos, pois posições além desses limites não afetam a cobertura.

#include <cstdio>
#include <algorithm>
using namespace std;
int total_intervals, minRight[1030], minOps[1030], ways[1030], max_r, max_l;
const int MOD = 1e9 + 7;
int main() {
    scanf("%d", &total_intervals);
    for (int i = 0; i <= 1024; i++) minRight[i] = minOps[i] = 1025;
    for (int i = 1; i <= total_intervals; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        minRight[l] = min(minRight[l], r);
        max_r = max(max_r, r);
        max_l = max(max_l, l);
    }
    ways[0] = 1; minOps[0] = 0;
    for (int i = 0; i <= max_r; i++) {
        int current_limit = minRight[i + 1];
        for (int j = i + 1; j <= current_limit; j++) {
            if (minOps[j] > minOps[i] + 1) {
                minOps[j] = minOps[i] + 1;
                ways[j] = ways[i];
            } else if (minOps[j] == minOps[i] + 1) {
                ways[j] = (ways[i] + ways[j]) % MOD;
            }
            current_limit = min(current_limit, minRight[j]);
        }
    }
    int best_ops = 2000, best_ways = 0;
    for (int i = max_l; i <= max_r; i++) {
        if (best_ops > minOps[i]) {
            best_ops = minOps[i];
            best_ways = ways[i];
        } else if (best_ops == minOps[i]) {
            best_ways = (best_ways + ways[i]) % MOD;
        }
    }
    printf("%d\n%d", best_ops, best_ways);
    return 0;
}

Problema 3: Coleção de Esferas

Primeiro, aplicamos uma abordagem de mochila 0/1 para cada grupo de esferas, determinando quais somas podem ser formadas e armazenando-as. Para garantir que o maior valor esteja na frente ao multiplicar pelos coeficientes, ordenamos os valores de forma crescente se o coeficiente for positivo, e decrescente caso contrário.

O número total de combinações é o produto das contagens de cada grupo. Se for menor que k, imprimimos a mensagem de falha. Para encontrar a k-ésima maior combinação, realizamos uma busca binária na diferença em relação ao valor máximo possível. Usamos uma busca em profundidade (DFS) para contar combinações com valor maior ou igual a um determinado limite inferior.

Para otimizar a etapa da mochila, utilizamos std::bitset, reduzindo significativamante a constante de tempo.

#include <cstdio>
#include <bitset>
#include <algorithm>
#define ll long long
using namespace std;
int m, target_k, n, weights[10004];
ll coeffs[10], possible_vals[10][100005], val_counts[10], total_sum, valid_combinations;
bitset<100005> is_reachable;
void compute_knapsack(int idx) {
    is_reachable.reset();
    is_reachable[0] = 1;
    for (int i = 1; i <= n; i++) is_reachable |= (is_reachable << weights[i]);
    val_counts[idx] = 0;
    if (coeffs[idx] > 0) {
        for (int i = total_sum; i >= 0; i--)
            if (is_reachable[i]) possible_vals[idx][++val_counts[idx]] = i;
    } else {
        for (int i = 0; i <= total_sum; i++)
            if (is_reachable[i]) possible_vals[idx][++val_counts[idx]] = i;
    }
}
bool count_combinations(int idx, ll remaining_budget) {
    if (idx > 7) {
        if (remaining_budget >= 0) valid_combinations++;
        return valid_combinations >= target_k;
    }
    for (int i = 1; i <= val_counts[idx]; i++) {
        ll diff = (possible_vals[idx][1] - possible_vals[idx][i]) * coeffs[idx];
        if (diff <= remaining_budget) {
            if (count_combinations(idx + 1, remaining_budget - diff)) return true;
        } else break;
    }
    return false;
}
int main() {
    scanf("%d%d", &m, &target_k);
    for (int i = 1; i <= 7; i++) scanf("%lld", &coeffs[i]);
    for (int i = 1; i <= 7; i++) {
        scanf("%d", &n);
        total_sum = 0;
        for (int j = 1; j <= n; j++) {
            scanf("%d", &weights[j]);
            total_sum = min(1ll * m, total_sum + weights[j]);
        }
        compute_knapsack(i);
    }
    ll combinations = 1;
    for (int i = 1; i <= 7; i++) {
        combinations *= val_counts[i];
        if (combinations > target_k) break;
    }
    if (combinations < target_k) {
        printf("Stop dreaming xm!");
        return 0;
    }
    ll max_value = 0;
    for (int i = 1; i <= 7; i++) max_value += possible_vals[i][1] * coeffs[i];
    if (target_k == 1) {
        printf("%lld", max_value);
        return 0;
    }
    ll low = 0, high = max_value;
    while (low < high) {
        ll mid = (low + high) >> 1;
        valid_combinations = 0;
        if (count_combinations(1, mid)) high = mid;
        else low = mid + 1;
    }
    printf("%lld", max_value - low);
    return 0;
}

Problema 4: Jogo de Esferas

Este problema exige uma programação dinâmica de intervalo. Se o dragão consumir elementos livremente no meio, o array será dividido, quebrando a restrição de que o jogador só pode peegar nas extremidades.

Para contornar isso, o dragão pode optar por não consumir imediatamente, adiando suas ações como "tokens de captura". Quando o dragão decide agir, ele pode usar um token para consumir uma esfera de qualquer extremidade. Isso preserva a integridade do intervalo contínuo.

Definimos estados de memoização: memo_player[l][r][tokens] representa a pontuação máxima do jogador no intervalo [l, r] com tokens acumulados, quando é a vez do jogador. memo_dragon[l][r][tokens] é a pontuação do jogador quando é a vez do dragão. O jogador maximiza a pontuação, enquanto o dragão a minimiza. A transição ocorre chamando recursivamente as funções com os limites atualizados e os tokens ajustados.

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll memo_player[501][501][255], memo_dragon[501][501][255], values[505];
int array_size;
ll calculate_dragon(int left, int right, int tokens);
ll calculate_player(int left, int right, int tokens);
ll calculate_dragon(int left, int right, int tokens) {
    if (left > right || tokens == right - left + 1) return 0;
    if (memo_dragon[left][right][tokens]) return memo_dragon[left][right][tokens] - 1;
    ll result = calculate_player(left, right, tokens);
    if (tokens >= 1) {
        result = min(result, min(calculate_dragon(left + 1, right, tokens - 1),
                                calculate_dragon(left, right - 1, tokens - 1)));
    }
    memo_dragon[left][right][tokens] = result + 1;
    return result;
}
ll calculate_player(int left, int right, int tokens) {
    if (left > right) return 0;
    if (memo_player[left][right][tokens]) return memo_player[left][right][tokens] - 1;
    ll result = max(calculate_dragon(left + 1, right, tokens + 1) + values[left],
                   calculate_dragon(left, right - 1, tokens + 1) + values[right]);
    memo_player[left][right][tokens] = result + 1;
    return result;
}
int main() {
    scanf("%d", &array_size);
    for (int i = 1; i <= array_size; i++) scanf("%lld", &values[i]);
    calculate_player(1, array_size, 0);
    printf("%lld", memo_player[1][array_size][0] - 1);
    return 0;
}