Exercice 1 : Simulation Calendaire et Recherche Binaire

Ce problème impose de gérer la discontinuité historique du passage du calendrier julien au calendrier grégorien, ainsi que la représentation des années antérieures à 1582. La stratégie optimale repose sur une pré-calculation exhaustive jusqu'au 14 octobre 1582, suivie d'une recherche binaire sur les années pour les requêtes dépassant cette limite. Les années bissextiles respectent des règles conditionnelles strictes qui varient avant et après la réforme.

La complexité temporelle est de l'ordre de O(N_{const} + Q \log R). La détermination du mois et du jour s'effectue par soustraction itérative des jours restants après avoir isolé l'année cible.

#include <iostream>
#include <vector>
#include <algorithm>

struct CalDate { int day, month, year; };
std::vector<CalDate> ref_table;

inline bool isLeapJulian(int yr) { return ((-yr) % 4) == 1; }
inline bool isLeapGregorian(int yr) { 
    return (yr % 4 == 0 && yr % 100 != 0) || (yr % 400 == 0); 
}

void precompute() {
    int cur_day = 1, cur_month = 1, cur_year = -4713;
    // Phase 1 : jusqu'à l'an 1
    for (int idx = 0; idx < 1721424; ++idx) {
        ref_table.push_back({cur_day, cur_month, cur_year});
        int limit = (cur_month == 2) ? (isLeapJulian(cur_year) ? 29 : 28) : 
                   (cur_month == 4 || cur_month == 6 || cur_month == 9 || cur_month == 11) ? 30 : 31;
        if (++cur_day > limit) { cur_day = 1; cur_month++; }
        if (cur_month > 12) { cur_month = 1; cur_year++; }
    }
    // Phase 2 : de l'an 1 au 4 octobre 1582
    cur_year = 1; cur_month = 1; cur_day = 1;
    while (ref_table.size() < 2299160) {
        ref_table.push_back({cur_day, cur_month, cur_year});
        int limit = (cur_month == 2) ? (isLeapGregorian(cur_year) ? 29 : 28) : 
                   (cur_month == 4 || cur_month == 6 || cur_month == 9 || cur_month == 11) ? 30 : 31;
        if (++cur_day > limit) { cur_day = 1; cur_month++; }
        if (cur_month > 12) { cur_month = 1; cur_year++; }
    }
    // Phase 3 : saut au 15 octobre 1582 et suite
    cur_year = 1582; cur_month = 10; cur_day = 15;
    for (int i = 0; i < 6654; ++i) {
        ref_table.push_back({cur_day, cur_month, cur_year});
        int limit = (cur_month == 2) ? (isLeapGregorian(cur_year) ? 29 : 28) : 
                   (cur_month == 4 || cur_month == 6 || cur_month == 9 || cur_month == 11) ? 30 : 31;
        if (++cur_day > limit) { cur_day = 1; cur_month++; }
        if (cur_month > 12) { cur_month = 1; cur_year++; }
    }
}

void resolveQuery(long long target) {
    if (target < (long long)ref_table.size()) {
        auto res = ref_table[target];
        std::cout << res.day << ' ' << res.month << ' ';
        if (res.year < 0) std::cout << -res.year << " BC\n";
        else std::cout << res.year << '\n';
        return;
    }
    
    long long remaining = target - ref_table.size();
    int low = 1583, high = 2000000000, base_year = 1582;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        long long leaps = (mid/4 - mid/100 + mid/400) - (1582/4 - 1582/100 + 1582/400);
        long long days = (long long)(mid - base_year) * 365 + leaps;
        if (days >= remaining) { base_year = mid - 1; high = mid - 1; }
        else low = mid + 1;
    }
    
    // Recalcul précis du jour et mois pour l'année trouvée
    long long days_before = 0;
    int yr = base_year + 1;
    int leaps_calc = (yr/4 - yr/100 + yr/400) - (1582/4 - 1582/100 + 1582/400);
    days_before = (long long)(yr - 1 - base_year) * 365 + leaps_calc - (isLeapGregorian(yr) ? 366 : 365);
    long long offset_in_year = remaining - days_before;
    
    int m = 1, d = 1;
    int month_days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    if (isLeapGregorian(yr)) month_days[2] = 29;
    
    while (m <= 12) {
        if (offset_in_year <= month_days[m]) {
            d = offset_in_year;
            break;
        }
        offset_in_year -= month_days[m];
        m++;
    }
    std::cout << d << ' ' << m << ' ' << yr << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    precompute();
    int queries; std::cin >> queries;
    while (queries--) { long long x; std::cin >> x; resolveQuery(x); }
    return 0;
}

Exercice 2 : Dénombrement Combinatoire et Masques Binaires

L'objectif est de déterminer combien d'entiers peuvent être formés sous contrainte de bits spécifiques. Si une position binaire est exigée par au moins une règle mais qu'aucun des entiers fournis ne possède le bit 1 à cette position, cette position devient libre. Le nombre total de combinaisons valides s'exprime par 2^{bits\_libres}. Il est nécessaire de soustraire les n entiers déjà présents pour respecter l'unicité. Une attention particulière doit être portée aux dépassements de capacité sur 64 bits.

La complexité résultante est O(NK).

#include <iostream>
#include <vector>
#include <cstdint>

int main() {
    std::ios::sync_with_stdio(false);
    int n, m, c, k;
    if (!(std::cin >> n >> m >> c >> k)) return 0;
    
    std::vector<uint64_t> values(n);
    uint64_t bit_mask_present = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> values[i];
        bit_mask_present |= values[i];
    }
    
    uint64_t forbidden_bits = 0;
    for (int i = 0; i < m; ++i) {
        int pos_req, val;
        std::cin >> pos_req >> val;
        if (!((bit_mask_present >> pos_req) & 1)) {
            forbidden_bits |= (1ULL << pos_req);
        }
    }
    
    int free_bits = k;
    uint64_t temp = forbidden_bits;
    while (temp) {
        temp &= (temp - 1);
        free_bits--;
    }
    
    if (free_bits >= 64) {
        std::cout << "18446744073709551616\n";
    } else {
        uint64_t total_combinations = (1ULL << free_bits);
        uint64_t result = total_combinations - n;
        std::cout << result << '\n';
    }
    return 0;
}

Exercice 3 : Programmation Dynamique sur Graphe Acyclique

Le problème modélise un système d'appels récursifs avec des opérations de multiplication et d'addition. La résolutoin optimale s'appuie sur une inversion des dépendances pour construire un DAG. On calcule d'abord le produit suffixe des multiplicateurs pour chaque nœud. Ensuite, une propagation topologique détermine combien de fois chaque instruction d'addition est réellement exécutée, en pondérant par les coefficients multiplicateurs des ancêtres directs.

Cette approche atteint O(N + \sum C + Q) grâce au tri topologique et à la propagation linéaire des coefficients.

#include <iostream>
#include <vector>
#include <queue>

constexpr int MOD = 998244353;
constexpr int MAX_OP = 100005;

int n_ops, m_ops, q_calls;
long long initial_arr[MAX_OP];
int op_type[MAX_OP], target_pos[MAX_OP], mult_val[MAX_OP];
std::vector<int> adj[MAX_OP];
int indegree[MAX_OP];
long long suffix_mul[MAX_OP], exec_weight[MAX_OP], global_add[MAX_OP];
long long query_seq[MAX_OP];
bool visited[MAX_OP];

long long mul(long long a, long long b) { return a * b % MOD; }
long long add(long long a, long long b) { return (a + b) % MOD; }

void computeSuffixMul(int u) {
    visited[u] = true;
    suffix_mul[u] = (op_type[u] == 2) ? mult_val[u] : 1;
    for (int v : adj[u]) {
        if (!visited[v]) computeSuffixMul(v);
        suffix_mul[u] = mul(suffix_mul[u], suffix_mul[v]);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n_ops;
    for (int i = 1; i <= n_ops; ++i) std::cin >> initial_arr[i];
    
    std::cin >> m_ops;
    for (int i = 1; i <= m_ops; ++i) {
        std::cin >> op_type[i];
        if (op_type[i] == 1) std::cin >> target_pos[i] >> mult_val[i];
        else if (op_type[i] == 2) std::cin >> mult_val[i];
        else {
            int c; std::cin >> c;
            while (c--) {
                int child; std::cin >> child;
                adj[i].push_back(child);
                indegree[child]++;
            }
        }
    }
    
    for (int i = 1; i <= m_ops; ++i) if (!visited[i]) computeSuffixMul(i);
    
    std::cin >> q_calls;
    for (int i = 1; i <= q_calls; ++i) std::cin >> query_seq[i];
    
    exec_weight[query_seq[q_calls]] = 1;
    long long prefix_coeff = 1;
    for (int i = q_calls - 1; i >= 1; --i) {
        prefix_coeff = mul(prefix_coeff, suffix_mul[query_seq[i+1]]);
        exec_weight[query_seq[i]] = add(exec_weight[query_seq[i]], prefix_coeff);
    }
    
    std::queue<int> topo_q;
    for (int i = 1; i <= m_ops; ++i) if (indegree[i] == 0) topo_q.push(i);
    
    while (!topo_q.empty()) {
        int u = topo_q.front(); topo_q.pop();
        if (op_type[u] == 1) {
            global_add[target_pos[u]] = add(global_add[target_pos[u]], mul(exec_weight[u], mult_val[u]));
        }
        
        long long running_coeff = 1;
        for (int v : adj[u]) {
            exec_weight[v] = add(exec_weight[v], mul(exec_weight[u], running_coeff));
            running_coeff = mul(running_coeff, suffix_mul[v]);
            if (--indegree[v] == 0) topo_q.push(v);
        }
    }
    
    long long global_mult = prefix_coeff * suffix_mul[query_seq[1]] % MOD;
    for (int i = 1; i <= n_ops; ++i) {
        long long res = add(mul(initial_arr[i], global_mult), global_add[i]);
        std::cout << res << " \n"[i == n_ops];
    }
    return 0;
}

Exercice 4 : Simulation Monotone et Gestion de File

Ce problème modélise un jeu séquentiel où l'élément maximal absorbe le minimal. Si la valeur résultante reste supérieure au nouveau maximum, la consommation se poursuit. Si elle chute en dessous du minimum actuel, une condition de parité détermine si la chaîne de consommation peut s'inverser. L'optimisation repose sur l'observation que les valeurs générées forment une suite monotone décroissante, permettant l'utilisation de structures à deux pointeurs ou de deque pour éviter les opérasions logarithmiques.

La complexité est réduite à O(T \cdot N) grâce à la conservation de l'ordre relatif et à la fusion linéaire des séquences originales et générées.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

struct Element { int value, original_idx; };

void solveSingleInstance(int n, std::vector<int> arr) {
    std::deque<Element> generated;
    int left = 0, right = n - 1;
    int remaining = n;
    
    while (remaining > 2) {
        Element max_el, min_el;
        // Sélection du maximum
        if (!generated.empty() && generated.front().value > arr[right]) 
            max_el = generated.front(), generated.pop_front();
        else max_el = {arr[right], right + 1}, right--;
        
        // Sélection du minimum
        if (!generated.empty() && generated.back().value < arr[left])
            min_el = generated.back(), generated.pop_back();
        else min_el = {arr[left], left + 1}, left++;
        
        remaining -= 2;
        int diff = max_el.value - min_el.value;
        
        // Vérification du nouveau minimum potentiel
        Element next_min;
        if (!generated.empty() && generated.back().value < arr[left])
            next_min = generated.back();
        else next_min = {arr[left], left + 1};
        
        if (diff < next_min.value || (diff == next_min.value && max_el.original_idx < next_min.original_idx)) {
            // Entrée en phase de parité
            int steps = 0;
            while (remaining > 0) {
                Element mx, mn;
                if (!generated.empty() && generated.front().value > arr[right])
                    mx = generated.front(), generated.pop_front();
                else mx = {arr[right], right + 1}, right--;
                
                if (!generated.empty() && generated.back().value < arr[left])
                    mn = generated.back(), generated.pop_back();
                else mn = {arr[left], left + 1}, left++;
                
                remaining -= 2;
                int cur_diff = mx.value - mn.value;
                Element nxt;
                if (!generated.empty() && generated.back().value < arr[left]) nxt = generated.back();
                else nxt = {arr[left], left + 1};
                
                if (cur_diff > nxt.value || (cur_diff == nxt.value && mx.original_idx > nxt.original_idx)) {
                    if (steps % 2 == 1) remaining--;
                    break;
                }
                steps++;
                generated.push_front({cur_diff, mx.original_idx});
                remaining++;
            }
            std::cout << remaining << '\n';
            return;
        }
        generated.push_front({diff, max_el.original_idx});
        remaining++;
    }
    std::cout << 1 << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    int t; std::cin >> t;
    int n; std::cin >> n;
    std::vector<int> original(n), current(n);
    for (int i = 0; i < n; ++i) { std::cin >> current[i]; original[i] = current[i]; }
    
    solveSingleInstance(n, current);
    while (--t) {
        int updates; std::cin >> updates;
        current = original;
        while (updates--) { int idx, val; std::cin >> idx >> val; current[idx-1] = val; }
        solveSingleInstance(n, current);
    }
    return 0;
}