Énoncé
Xiaomei possède un tableau de longueur $n$ contenant des entiers non négatifs ${a_1, a_2, \ldots, a_n}$. Elle souhaite construire un entier non négatif $c$ dont le nombre de bits binaires ne dépasse pas celui du maximum du tableau (le bit 0 compte comme 1).
Elle peut répéter l'opération suivante pour maximiser la somme totale :
- Choisir un indice $i$, remplacer $a_i$ par $a_i \lor c$ (OU binaire)
- Remplacer simultanément $c$ par $a_i \land c$ (ET binaire)
Objectif : trouver la somme maximale possible et le plus petit $c$ initial permettant d'atteindre cette somme.
Analyse
L'opération transfère les bits 1 de $c$ vers les éléments du tableau. Chaque bit 1 de $c$ peut être distribué exactement une fois. Pour maximiser la somme finale, il faut distribuer tous les bits 1 possibles aux éléments qui en ont besoin.
Implémentation Python
import sys
MAX_BITS = 30
FULL_MASK = (1 << MAX_BITS) - 1
def bit_length(x):
return 1 if x == 0 else x.bit_length()
def solve():
data = sys.stdin.read().strip().split()
it = iter(data)
T = int(next(it))
results = []
for _ in range(T):
n = int(next(it))
values = [int(next(it)) for _ in range(n)]
total = sum(values)
max_val = max(values)
bits_needed = bit_length(max_val)
current_mask = (1 << bits_needed) - 1
common_bits = FULL_MASK
for val in values:
common_bits &= val
common_bits &= current_mask
missing_bits = current_mask ^ common_bits
total += missing_bits
results.append(f"{total} {missing_bits}")
print("\n".join(results))
if __name__ == "__main__":
solve()
Implémentation C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 505;
const int MAX_BITS = 30;
const int FULL_MASK = (1 << MAX_BITS) - 1;
int arr[MAX_N];
int countBits(int x) {
return x == 0 ? 1 : (int)floor(log2(x)) + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
long long sum = 0;
int maxVal = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
sum += arr[i];
maxVal = max(maxVal, arr[i]);
}
int bits = countBits(maxVal);
int mask = (1 << bits) - 1;
int common = FULL_MASK;
for (int i = 0; i < n; i++) {
common &= arr[i];
}
common &= mask;
int missing = mask ^ common;
sum += missing;
cout << sum << " " << missing << "\n";
}
return 0;
}
Problème 2: Chemin optimal avec artefacts magiques
Énoncé
Dans un royaume fnatastique avec $n$ villes et $m$ routes bidirectionnelles, chaque ville contient un artefact magique. Les artefacts ont une énergie (positive = "mauvais", négative = "bon"). Les mauvais artefacts ajoutent leur énergie au temps de trajet (obligatoire), les bons peuvent réduire le temps (optionnel, mais limité à $k$ utilisations).
Temps réel = temps base de route + énergie de l'artefact de destination
Calculer le temps minimum pour aller de la ville 1 à la ville $n$.
Analyse
C'est un problème de graphe en couches où chaque couche représente le nombre d'artefacts bons utilisés. Au lieu de construier explicitement toutes les couches, nous utilisons une approche itérative avec Dijkstra.
Implémentation Python
import sys
import heapq
INFINITY = 10**18
def dijkstra(adj, energy, dist):
heap = [(dist[i], i) for i in range(1, len(dist)) if dist[i] < INFINITY]
heapq.heapify(heap)
visited = [False] * len(dist)
while heap:
d, u = heapq.heappop(heap)
if visited[u]:
continue
visited[u] = True
for v, w in adj[u]:
new_dist = d + w + max(0, energy[v])
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(heap, (new_dist, v))
def main():
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
m = int(next(it))
k = int(next(it))
artifact = [0] * (n + 1)
for i in range(1, n + 1):
artifact[i] = int(next(it))
adj = [[] for _ in range(n + 1)]
for _ in range(m):
u = int(next(it))
v = int(next(it))
w = int(next(it))
adj[u].append((v, w))
adj[v].append((u, w))
current = [INFINITY] * (n + 1)
current[1] = 0
dijkstra(adj, artifact, current)
answer = current[n]
for _ in range(k):
next_layer = [INFINITY] * (n + 1)
for u in range(1, n + 1):
if current[u] == INFINITY:
continue
for v, w in adj[u]:
if artifact[v] < 0:
new_dist = current[u] + w + artifact[v]
if new_dist < next_layer[v]:
next_layer[v] = new_dist
dijkstra(adj, artifact, next_layer)
answer = min(answer, next_layer[n])
current = next_layer
if answer >= INFINITY // 2:
print("NO")
else:
print(answer)
if __name__ == "__main__":
main()
Implémentation C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1005;
const int MAX_M = 4005;
const int INF = 1e9;
struct Edge {
int to, weight, next;
} edges[MAX_M];
int head[MAX_N], edgeCount = 0;
int artifact[MAX_N];
int n, m, maxUses;
void addEdge(int u, int v, int w) {
edges[++edgeCount] = {v, w, head[u]};
head[u] = edgeCount;
}
void dijkstra(int startDist[], int layer) {
vector<int> dist(startDist, startDist + n + 1);
vector<bool> visited(n + 1, false);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
for (int i = 1; i <= n; i++) {
if (dist[i] < INF) {
pq.push({dist[i], i});
}
}
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (visited[u]) continue;
visited[u] = true;
for (int e = head[u]; e; e = edges[e].next) {
int v = edges[e].to;
int newDist = d + edges[e].weight + max(0, artifact[v]);
if (newDist < dist[v]) {
dist[v] = newDist;
pq.push({newDist, v});
}
}
}
for (int i = 1; i <= n; i++) {
startDist[i] = dist[i];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> maxUses;
for (int i = 1; i <= n; i++) {
cin >> artifact[i];
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
addEdge(v, u, w);
}
int currentLayer = 0, nextLayer = 1;
vector<array<int, MAX_N>> dist(2);
for (auto &d : dist) {
fill(d.begin(), d.end(), INF);
}
dist[currentLayer][1] = 0;
dijkstra(dist[currentLayer].data(), currentLayer);
int answer = dist[currentLayer][n];
for (int use = 0; use < maxUses; use++) {
fill(dist[nextLayer].begin(), dist[nextLayer].end(), INF);
for (int u = 1; u <= n; u++) {
if (dist[currentLayer][u] == INF) continue;
for (int e = head[u]; e; e = edges[e].next) {
int v = edges[e].to;
if (artifact[v] >= 0) continue;
int newDist = dist[currentLayer][u] + edges[e].weight + artifact[v];
if (newDist < dist[nextLayer][v]) {
dist[nextLayer][v] = newDist;
}
}
}
dijkstra(dist[nextLayer].data(), nextLayer);
answer = min(answer, dist[nextLayer][n]);
swap(currentLayer, nextLayer);
}
if (answer >= INF / 2) {
cout << "NO\n";
} else {
cout << answer << "\n";
}
return 0;
}
Problème 3: Dénombrement de triplets ordonnés
Énoncé
Compter le nombre de triplets $(i, j, k)$ tels que $1 \leq i < j < k \leq n$ et $a_i > a_k > a_j$ dans un tableau de $n$ entiers.
Analyse
Au lieu de compter directement les triplets $a_i > a_k > a_j$, nous utilisons une approche par inclusion-exclusion. Nous comptons d'abord tous les triplets où $a_i$ est le maximum, puis soustrayons ceux où $a_j > a_k$.
Implémentation Python
import sys
import bisect
class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = [0] * (size + 1)
def update(self, index, delta):
while index <= self.size:
self.tree[index] += delta
index += index & -index
def query(self, index):
result = 0
while index > 0:
result += self.tree[index]
index -= index & -index
return result
def solve():
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
array = [0] * (n + 1)
for i in range(1, n + 1):
array[i] = int(next(it))
# Compression des valeurs
unique_vals = sorted(set(array[1:]))
compressed = [bisect.bisect_left(unique_vals, val) + 1 for val in array]
fenwick_right = FenwickTree(len(unique_vals))
right_smaller_equal = [0] * (n + 1)
result = 0
# Comptage de droite à gauche
for i in range(n, 0, -1):
smaller = fenwick_right.query(compressed[i] - 1)
right_smaller_equal[i] = fenwick_right.query(compressed[i])
result += smaller * (smaller - 1) // 2
fenwick_right.update(compressed[i], 1)
# Comptage de gauche à droite
fenwick_left = FenwickTree(len(unique_vals))
for i in range(1, n + 1):
larger_on_left = i - 1 - fenwick_left.query(compressed[i])
result -= larger_on_left * right_smaller_equal[i]
fenwick_left.update(compressed[i], 1)
print(result)
if __name__ == "__main__":
solve()
Implémentation C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
class BIT {
private:
int size;
vector<int> tree;
public:
BIT(int n) : size(n), tree(n + 1, 0) {}
void add(int index, int value) {
while (index <= size) {
tree[index] += value;
index += index & -index;
}
}
int sum(int index) {
int result = 0;
while (index > 0) {
result += tree[index];
index -= index & -index;
}
return result;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
// Compression
vector<int> sortedVals(arr.begin() + 1, arr.end());
sort(sortedVals.begin(), sortedVals.end());
sortedVals.erase(unique(sortedVals.begin(), sortedVals.end()), sortedVals.end());
vector<int> compressed(n + 1);
for (int i = 1; i <= n; i++) {
compressed[i] = lower_bound(sortedVals.begin(), sortedVals.end(), arr[i]) - sortedVals.begin() + 1;
}
BIT rightTree(sortedVals.size());
vector<int> rightSmallerEqual(n + 1);
long long answer = 0;
// Parcours de droite à gauche
for (int i = n; i >= 1; i--) {
int smaller = rightTree.sum(compressed[i] - 1);
rightSmallerEqual[i] = rightTree.sum(compressed[i]);
answer += 1LL * smaller * (smaller - 1) / 2;
rightTree.add(compressed[i], 1);
}
// Parcours de gauche à droite
BIT leftTree(sortedVals.size());
for (int i = 1; i <= n; i++) {
int largerOnLeft = i - 1 - leftTree.sum(compressed[i]);
answer -= 1LL * largerOnLeft * rightSmallerEqual[i];
leftTree.add(compressed[i], 1);
}
cout << answer << "\n";
return 0;
}