Épreuves de qualification NOIP - 10 sessions d'entraînement
Jour 1
Problème 1
Énoncé :
Étant donné \(n\) nombres \(a_1,a_2,a_3 \dots a_n\), vous pouvez en sélectionner certains. Combien de façons permettent d'obtenir une moyenne égale à \(A\) pour les nombres sélectionnés ?
Solution
D'après la formule de la moyenne : (sélection de \(m\) nombres, stockés dans un tableau \(b\))
[\bar{x}=\frac{\sum_{i=1}^m b_i}{m} ]Nous énumérons les multiples de \(A\), à savoir \(k*A\), et précalculons le nombre de façons de sélectionner \(k\) nombres dont la somme vaut \(k*A\).
Il s'agit clairement d'un problème de programmation dynamique simple.
Code
#include<bits/stdc++.h>
using namespace std;
int n, A;
int valeurs[103];
int valeursEntree[103];
int resultat;
int sommes[103];
int dp[2503][51];
void initialiser(){
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = sommes[i]; j >= valeursEntree[i]; j--){
for(int k = i; k >= 1; k--){
dp[j][k] += dp[j - valeursEntree[i]][k - 1];
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> A;
sommes[0] = 0;
for(int i = 1; i <= n; i++){
cin >> valeursEntree[i];
sommes[i] = valeursEntree[i] + sommes[i - 1];
}
initialiser();
for(int i = A; i <= n * A; i += A){
resultat += dp[i][i / A];
}
cout << resultat;
return 0;
}
Problème 2
Énoncé :
On vous donne un graphe non orienté dont les arêtes ont des poids. Le coût de parcours d'une arête est \(\min(\text{poids minimum des arêtes déjà traversées}, \text{poids de cette arête})\). Trouvez le coût minimum pour aller de \(1\) à \(n\).
Solution
Intuitivement, on remarque qu'il faut d'abord emprunter les arêtes de petit poids. Nous pouvons donc d'abord appliquer l'algorithme de Floyd pour calculer les plus courts chemins entre toutes les paires de sommets. Puis, en commençant par les arêtes de plus grand poids et en les considérannt comme le poids minimum actuel, nous mettons à jour le coût minimum pour aller de \(1\) à \(n\).
\(Q:\) Pourquoi énumérer à partir de la plus grande arête ?
\(R:\) Car lors de l'énumération, nous固定ons l'arête actuelle comme le poids minimum, donc les arêtes précédentes doivent être plus grandes.
Code
#include<bits/stdc++.h>
using namespace std;
const int MAX_ARETES = 125001;
const int MAX_SOMMETS = 502;
int n, m;
struct Arete{
int u, v, poids;
};
Arete listeAretes[MAX_ARETES];
int matriceDist[MAX_SOMMETS][MAX_SOMMETS];
bool comparaison(Arete a, Arete b){
return a.poids > b.poids;
}
int coutMin[MAX_SOMMETS];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
memset(matriceDist, 0x3f, sizeof matriceDist);
for(int i = 1; i <= m; i++){
cin >> listeAretes[i].u >> listeAretes[i].v >> listeAretes[i].poids;
matriceDist[listeAretes[i].u][listeAretes[i].v] = 1;
matriceDist[listeAretes[i].v][listeAretes[i].u] = 1;
}
for(int i = 1; i <= n; i++) matriceDist[i][i] = 0;
// Floyd-Warshall
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
matriceDist[i][j] = min(matriceDist[i][j], matriceDist[i][k] + matriceDist[k][j]);
}
}
}
memset(coutMin, 0x3f, sizeof coutMin);
sort(listeAretes + 1, listeAretes + 1 + m, comparaison);
coutMin[1] = 0;
for(int i = 1; i <= m; i++){
int x = listeAretes[i].u;
int y = listeAretes[i].v;
int w = listeAretes[i].poids;
if(coutMin[x] > coutMin[y]) swap(x, y);
for(int j = 1; j <= n; j++){
coutMin[j] = min(coutMin[j], coutMin[x] + (matriceDist[y][j] + 1) * w);
}
}
cout << coutMin[n];
return 0;
}
Jour 2
Problème 1
Énoncé :
Soit un tableau \(a\) où \(a_1=1, a_2=2, a_3=3 \dots a_n=n\). La valeur du tableau est définie comme \((a_1 \otimes 1)+(a_2 \otimes 2)+(a_3 \otimes 3)+\dots+(a_n \otimes n)\). Vous pouvez effectuer \(k\) échanges. Quelle est la valeur maximale possible du tableau ?
Solution
Comme il s'agit de l'opération \(\otimes\) (XOR), nous devons maximiser les différences binaires entre \(a_i\) et \(i\). Une approche gloutonne montre que le couplage optimal se fait entre \(x\) et \(2^m - x - 1\).
Code
#include<bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
int T;
u64 n, k;
u64 reponse;
u64 puissance[1003] = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824};
void resoudre(u64 gauche, u64 droite){
if(gauche == droite || droite < gauche || k == 0) return;
for(int i = 31; i >= 1; i--){
if(puissance[i] <= droite){
u64 p = min((puissance[i] - 1), (droite - puissance[i] + 1));
p = min(p, k);
reponse += (p * 2 * (puissance[i + 1] - 1));
k -= p;
resoudre(gauche, puissance[i] - 1 - min((puissance[i] - 1), (droite - puissance[i] + 1)));
return;
}
}
}
void traiter(){
reponse = 0;
cin >> n >> k;
resoudre(1, n);
cout << reponse << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while(T--) traiter();
return 0;
}
Problème 2
Énoncé :
Soit un tableau \(a\). Vous pouvez incrémenter ou décrémenter \(a_i\) de \(1\) avec un coût de \(1\). De plus, s'il existe \(a_i = a_j + 1\), le coût augmente de \(1\).
Solution
Une approche évidente consiste à traiter simultanément les éléments de même valeur. Nous énumérons de \(min_a\) à \(max_a\) et transférons tous les \(a_i\) vers \(a_j\) avec une différence de \(1\).
Code
#include<bits/stdc++.h>
using namespace src;
int n;
int val;
int reponse;
int frequence[100003];
int maximum;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> val;
frequence[val]++;
maximum = max(maximum, val);
}
for(int i = 1; i <= maximum; i++){
int transfert = min(frequence[i - 1], frequence[i]);
reponse += transfert;
frequence[i - 1] -= transfert;
frequence[i] -= transfert;
}
cout << reponse;
return 0;
}
Jour 3
Problème 1
Énoncé :
On vous donne un graphe orienté pondéré. Chaque sommet a une contrainte temporelle : on ne peut y entrer que dans l'intervalle \([b+kl, e+kl]\) où \(k \in \mathbb{N}\). Trouvez le plus court chemin de \(1\) à \(n\).
Solution
Il s'agit d'un problème de plus court chemin à source unique avec des contraintes temporelles.
Code
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 20;
const int M = 1e6 + 20;
const i64 INF = 1e18;
int n, m;
struct Constraint{
int debut, fin, periode;
};
struct Arc{
int extremite;
int poids;
};
int u, v2, w;
vector<Arc> adj[N];
void initialisation(){
cin >> n >> m;
for(int i = 2; i < n; i++){
cin >> adj[i].begin().debut >> adj[i].begin().fin >> adj[i].begin().periode;
}
for(int i = 1; i <= m; i++){
cin >> u >> v2 >> w;
adj[u].push_back({v2, w});
}
}
bool visite[N];
i64 distance[N];
using Paire = pair<int, int>;
priority_queue<Paire, vector<Paire>, greater<Paire>> file;
int calculerDelai(int sommet, int temps){
if(sommet == 1 || sommet == n) return 0;
int reste = temps % periode[sommet];
if(reste >= debut[sommet] && reste <= fin[sommet]) return 0;
else{
if(reste < debut[sommet]) return debut[sommet] - reste;
if(reste > fin[sommet]) return periode[sommet] + debut[sommet] - reste;
}
}
void dijkstra(){
for(int i = 1; i <= n; i++){
distance[i] = INF;
visite[i] = false;
}
distance[1] = 0;
file.push({0, 1});
while(!file.empty()){
int x = file.top().second;
file.pop();
if(visite[x]) continue;
visite[x] = true;
for(auto &arc : adj[x]){
int y = arc.extremite;
int w = arc.poids;
i64 nouveauDistance = distance[x] + w + calculerDelai(y, distance[x] + w);
if(distance[y] > nouveauDistance){
distance[y] = nouveauDistance;
file.push({distance[y], y});
}
}
}
}
int main(){
freopen("entree.txt", "r", stdin);
freopen("sortie.txt", "w", stdout);
initialisation();
dijkstra();
cout << distance[n];
return 0;
}
Problème 2
Énoncé :
Il y a \(2*n\) nombres, chacun étant inférieur ou égal à \(n\). Trouvez un intervalle qui peut être divisé en deux ensembles de somme égale.
Solution :
Pour chaque nombre, nous attribuons un poids de \(1\) ou \(-1\), ce qui permet de contrôler la somme前缀 dans l'intervalle \([-n+1, n]\). D'après le principe des tiroirs (pigeonhole), il existe nécessairement une solution.
Code :
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int n;
i64 valeur[4000004];
int difference;
int k;
int historique[4000004];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
n *= 2;
memset(historique, 0, sizeof historique);
for(int i = 1; i <= n; i++){
cin >> k;
if(difference > 0){
difference -= k;
}
else{
difference += k;
historique[i] = 1;
}
if(difference == 0 || valeur[difference + n]){
cout << valeur[difference + n] + 1 << " " << i << "\n";
for(int j = valeur[difference + n] + 1; j <= i; j++) cout << historique[j];
return 0;
}
valeur[difference + n] = i;
}
return 0;
}
Jour 4
Problème 1
Énoncé :
On vous donne un tableau \(a\). Vous pouvez choisir librement \(a_i\) et \(a_j\) et ajouter \(|a_i - a_j|\) au tableau (si ce nombre existe déjà, on ne l'ajoute pas). Combien de nombres peut-on obtenir au maximum ?
Solution :
On remarque facilement qu'après arrangement croissant, le tableau final prend la forme :
\(a_1\), \(2*a_1\), \(3*a_1\), \(4*a_1\) \(\dots\)
On peut observer que \(a_1\) correspond au PGCD (plus grand commun diviseur) du tableau original.
Code
#include<bits/stdc++.h>
using namespace std;
const int TAILLE = 5e5 + 20;
int pgcd(int x, int y){
if(!y) return x;
return pgcd(y, x % y);
}
int nombreTests;
int n;
int tableau[TAILLE];
void resoudre(){
cin >> n;
int maximum = -1;
for(int i = 1; i <= n; i++){
cin >> tableau[i];
maximum = max(maximum, tableau[i]);
}
if(n == 1){
cout << "1\n";
return;
}
int GCD = pgcd(tableau[1], tableau[2]);
for(int i = 2; i < n; i++){
GCD = pgcd(GCD, tableau[i + 1]);
}
cout << (maximum / GCD) << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> nombreTests;
while(nombreTests--) resoudre();
return 0;
}
Épreuves de qualification CSP - 7 sessions
Jour 1
Problème 1
Énoncé :
Il y a \(n\) personnes, chacune ayant une valeur \(a\). On donne les personnes connues de chaque individu. Pour la \(i\)-ème personne, si elle connaît \(m\) personnes dont \(k\) ont une valeur supérieure à la sienne. Si \(k \ge \frac{m}{2}\), cette personne abandonne. Combien de personnes abandonneront ?
Solution
Une approche force brute suffit.
Code
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int n;
int c, a, b;
int valeurs[20000004];
int x;
int somme;
int reponse;
int marqueur[20000004];
int compteur;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> valeurs[i];
for(int i = 1; i <= n; i++){
cin >> c >> a >> b;
somme = 0;
compteur = 0;
x = b;
for(int j = 1; j <= c; j++){
if(marqueur[x] != i && x != i){
marqueur[x] = i;
compteur++;
}
else{
x = (x * a + b) % n + 1;
continue;
}
somme += (valeurs[x] > valeurs[i]);
x = (x * a + b) % n + 1;
}
reponse += (somme * 2 >= compteur && (somme != 0));
}
cout << reponse;
return 0;
}
Problème 2
Énoncé :
On vous donne un nombre. En ajoutant des chiffres à la fin, quel est le plus petit nombre premier obtainable ?
Solution :
Puisque parmi 1000 nombres générés, il y a nécessairement un nombre premier, nous pouvons utilisser la force brute.
Code :
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int q;
const int LIMITE = 100000000;
int premiers[10000005];
bool estCompose[100000003];
int total;
ll resultat[1000003];
void genererPremiers(int n){
memset(estCompose, true, sizeof estCompose);
estCompose[1] = false;
for(int i = 2; i <= n; i++){
if(estCompose[i]){
premiers[++total] = i;
}
for(int j = 1; j <= total && premiers[j] * i <= n; j++){
estCompose[premiers[j] * i] = false;
if(i % premiers[j] == 0) break;
}
}
}
inline bool verifierPremier(ll x){
if(x <= LIMITE) return estCompose[x];
for(int i = 2; i * i <= x; i++){
if(x % i == 0) return false;
}
return true;
}
void traiter(int x){
if(verifierPremier(x)){
resultat[x] = x;
return;
}
for(int i = 1; i <= 9; i += 2){
ll y = x * 10 + i;
if(verifierPremier(y)){
resultat[x] = y;
return;
}
}
for(int i = 0; i <= 9; i++){
for(int j = 1; j <= 9; j += 2){
ll z = x * 100 + i * 10 + j;
if(verifierPremier(z)){
resultat[x] = z;
return;
}
}
}
for(int i = 0; i <= 9; i++){
for(int j = 0; j <= 9; j++){
for(int k = 1; k <= 9; k += 2){
ll p = x * 1000 + i * 100 + j * 10 + k;
if(verifierPremier(p)){
resultat[x] = p;
return;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
genererPremiers(LIMITE);
for(int i = 1; i <= 1000000; i++){
traiter(i);
}
cin >> q;
while(q--){
int x;
cin >> x;
cout << resultat[x] << "\n";
}
return 0;
}
Problème 3
Énoncé :
Il y a un tableau \(a\) avec \(a_1=1, a_2=2 \dots a_n=n\). Il y a \(n\) personnes, chacune correspondant à une valeur du tableau \(a\). Il y a \(m\) exigences. Chaque exigence donne \(p\) et \(x\) : parmi les personnes d'index supérieur à \(p\), exactement \(x\) personnes ont une valeur \(a\) supérieure à celle de la \(p\)-ième personne.
Solution
On peut remaruqer que pour une exigence, les nombres valides forment un intervalle. L'approche gloutonne consiste à toujours choisir le plus grand possible.
Code
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 5e5 + 10;
int T;
int n, m;
struct Noeud{
int gauche, droite, somme;
};
struct Requete{
int p, x;
};
Noeud segment[4 * N];
Requete requetes[N];
int contrainte[N];
void construire(int gauche, int droite, int indice){
segment[indice].gauche = gauche;
segment[indice].droite = droite;
if(gauche == droite){
segment[indice].somme = 1;
return;
}
int milieu = gauche + droite >> 1;
construire(gauche, milieu, indice << 1);
construire(milieu + 1, droite, indice << 1 | 1);
segment[indice].somme = segment[indice << 1].somme + segment[indice << 1 | 1].somme;
}
int requete(int k, int indice){
if(segment[indice].gauche == segment[indice].droite) return segment[indice].gauche;
if(k > segment[indice << 1].somme)
return requete(k - segment[indice << 1].somme, indice << 1 | 1);
else
return requete(k, indice << 1);
}
void supprimer(int k, int indice){
if(segment[indice].gauche == segment[indice].droite){
segment[indice].somme = 0;
return;
}
int milieu = segment[indice].gauche + segment[indice].droite >> 1;
if(k <= milieu) supprimer(k, indice << 1);
else supprimer(k, indice << 1 | 1);
segment[indice].somme = segment[indice << 1].somme + segment[indice << 1 | 1].somme;
}
int reponse[N];
int main(){
ios::sync_with_stdio(false);
cin >> T;
while(T--){
cin >> n >> m;
construire(1, n, 1);
bool impossible = false;
for(int i = 1; i <= n; i++) contrainte[i] = -1;
for(int i = 1; i <= m; i++){
cin >> requetes[i].p >> requetes[i].x;
contrainte[requetes[i].p] = requetes[i].x;
if(n - requetes[i].p - requetes[i].x + 1 <= 0){
impossible = true;
}
}
if(impossible){
cout << "-1\n";
continue;
}
for(int i = 1; i <= n; i++){
if(contrainte[i] == -1){
if(n - i + 1 <= 0){
impossible = true;
break;
}
reponse[i] = requete(n - i + 1, 1);
}
else{
if(n - i - contrainte[i] + 1 <= 0){
impossible = true;
break;
}
reponse[i] = requete(n - i - contrainte[i] + 1, 1);
}
supprimer(reponse[i], 1);
}
if(impossible){
cout << "-1\n";
continue;
}
for(int i = 1; i <= n; i++) cout << reponse[i] << " ";
cout << "\n";
}
return 0;
}
Jour 2
Problème 2
Énoncé :
On vous donne \(n\) nombres. Vous devez les diviser en \(3\) ensembles tels que le maximum du premier ensemble soit inférieur ou égal à la taille du deuxième ensemble, le maximum du deuxième ensemble soit inférieur ou égal à la taille du troisième ensemble, et le maximum du troisième ensemble soit inférieur ou égal à la taille du premier ensemble.
Solution :
Approche gloutonne, mais il faut considérer tous les cas.
Code :
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int T;
int n;
int couleur[N];
struct Element{
int id, valeur;
};
Element tab[N];
bool comparaison(Element x, Element y){
return x.valeur > y.valeur;
}
int main(){
ios::sync_with_stdio(false);
cin >> T;
while(T--){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> tab[i].valeur;
tab[i].id = i;
}
sort(tab + 1, tab + 1 + n, comparaison);
bool trouve = false;
for(int i = 1; i <= n - 2; i++){
int gauche = n - tab[1].valeur + 1;
int droite = n;
if(gauche - i <= 1) continue;
if(tab[gauche].valeur <= (gauche - 1 - (i + 1) + 1) && (tab[i + 1].valeur <= i)){
trouve = true;
cout << "YES\n";
for(int j = 1; j <= i; j++) couleur[tab[j].id] = 1;
for(int j = i + 1; j <= gauche - 1; j++) couleur[tab[j].id] = 3;
for(int j = gauche; j <= droite; j++) couleur[tab[j].id] = 2;
for(int j = 1; j <= n; j++) cout << couleur[j] << " ";
cout << "\n";
break;
}
gauche = i + 1;
droite = gauche + tab[1].valeur - 1;
if(droite >= n || gauche >= n) continue;
if(tab[droite + 1].valeur <= i && tab[gauche].valeur <= (n - (droite + 1) + 1)){
trouve = true;
cout << "YES\n";
for(int j = 1; j <= i; j++) couleur[tab[j].id] = 1;
for(int j = gauche; j <= droite; j++) couleur[tab[j].id] = 2;
for(int j = droite + 1; j <= n; j++) couleur[tab[j].id] = 3;
for(int j = 1; j <= n; j++) cout << couleur[j] << " ";
cout << "\n";
break;
}
}
if(!trouve) cout << "NO\n";
}
return 0;
}
Problème 4
Énoncé :
Il y a un arbre à \(n\) sommets, chaque sommet ayant un poids. Il y a \(q\) requêtes, chacune donnant un \(x\). La question est de savoir s'il existe deux sommets \(u\) et \(v\) en relation ancestor-descendant tels que la somme des poids sur le chemin soit égale à \(x\).
Solution :
Utilisation de bitset.
Code :
#include<bits/stdc++.h>
using namespace std;
int n, q;
int parent;
vector<int> adj[1000003];
int poids[2000004];
bitset<100050> requetes, ensemble[41];
int demande[1000004];
bool estRacine[1000003];
struct Vertex{
int fils, maxFils, ancetre;
};
Vertex information[1000004];
void dfs1(int sommet, int pere){
information[sommet].ancetre = pere;
information[sommet].maxFils = 0;
information[sommet].fils = 1;
for(auto y : adj[sommet]){
if(y != pere){
dfs1(y, sommet);
information[sommet].fils += information[y].fils;
if(information[y].fils > information[information[sommet].maxFils].fils){
information[sommet].maxFils = y;
information[information[sommet].maxFils].fils = information[y].fils;
}
}
}
}
void dfs2(int sommet, int profondeur){
ensemble[profondeur].set(0, 1);
ensemble[profondeur] <<= poids[sommet];
requetes ^= (requetes & ensemble[profondeur]);
for(auto y : adj[sommet]){
if(y != information[sommet].ancetre && y != information[sommet].maxFils){
ensemble[profondeur + 1] = ensemble[profondeur];
dfs2(y, profondeur + 1);
}
}
if(information[sommet].maxFils) dfs2(information[sommet].maxFils, profondeur);
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> q;
int racine;
for(int i = 1; i <= n; i++){
cin >> parent;
estRacine[i] = true;
if(parent == 0) racine = i;
else adj[parent].push_back(i);
}
for(int i = 1; i <= n; i++) cin >> poids[i];
for(int i = 1; i <= q; i++){
cin >> demande[i];
requetes.set(demande[i], 1);
}
dfs1(racine, 0);
dfs2(racine, 0);
for(int i = 1; i <= q; i++){
if(requetes[demande[i]] == 1) cout << "NO\n";
else cout << "YES\n";
}
return 0;
}
Jour 3
Problème 1
Problème théorique
Code
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 a, m;
int K;
const int MOD = 1e9 + 7;
i64 reponse;
int mapping[10];
int sequence[4] = {0, 1, 4, 2};
void transformer(int x){
if(x == 1 || x == 2 || x == 4 || m == 0){
a = x;
return;
}
reponse = (reponse + x) % MOD;
if(x % 2 == 0){
--m;
transformer(x / 2);
}
else{
--m;
transformer(3 * x + 1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> m;
transformer(a);
int cycles = m / 3;
reponse = (reponse + (cycles * 7) % MOD) % MOD;
m %= 3;
mapping[1] = 1;
mapping[4] = 2;
mapping[2] = 3;
if(m){
int x = mapping[a];
while(m){
reponse = (reponse + sequence[x]) % MOD;
if(x == 3) x = 1;
x++;
m--;
}
}
cout << reponse;
return 0;
}