Dans le domaine de la programmation compétitive, la résolution efficace des problèmes nécessite souvent des approches algorithmiques ingénieuses. Cet article examine un problème spécifique qui, bien que semblant complexe à première vue, peut être résolu par des techniques de programmation dynamique bien conçues.
Énoncé du problème
On nous donne deux entiers, n et m, représentant respectivement le nombre d'opérations disponibles et la quantité cible de bananes que nous souhaitons atteindre.
Ensuite, nous recevons n opérations, chacune caractérisée par trois entiers : t_i, x_i et y_i. Soit k notre quantité actuelle de bananes.
- Si t_i = 1, nous pouvons choisir un nombre a_i dans l'intervalle [0, y_i], puis appliquer l'opération ⌈k + x_i⌉ à k, exactement a_i fois.
- Si t_i = 2, nous pouvons choisir un nombre a_i dans l'intervalle [0, y_i], puis appliquer l'opération ⌈k × x_i⌉ à k, exactement a_i fois.
Notre objectif est de déterminer, pour chaque i dans l'intervalle [1, m], le nombre minimal d'opérations nécessaires pour atteindre exactement i bananes. Si c'est impossible, nous devons retourner -1.
Notons que x_i peut être un nombre décimal. Dans l'entrée, x_i est fourni sous la forme x_i' = x_i × 10^5.
Contraintes :
- 1 ≤ n ≤ 200
- 2 ≤ m ≤ 10^5
- 1 ≤ t_i ≤ 2
- 1 ≤ y_i ≤ m
- Pour les opérations de type 1 : 1 ≤ x_i' ≤ 10^5 × m
- Pour les opérations de type 2 : 10^5 < x_i' ≤ 10^5 × m
Approche de résolution
Méthode 1 : Programmation dynamique classique
Une première approche consiste à modéliser ce problème comme un problème de sac à dos multiple. Nous définissons deux tableaux :
- dp[i] : le nombre minimal d'opérations nécessaires pour obtenir i bananes
- cnt[i] : le nombre minimal d'étapes nécessaires pour obtenir i bananes avec l'opération actuelle
L'algorithme fonctionne en itérant sur chaque opération et en mettant à jour dynamiquement les tableaux dp et cnt selon les règles spécifiées.
Complexité temporelle : O(n × m)
Méthode 2 : Optimisation basée sur une propriété spécifique
Une observation importante permet d'optimiser la solution : pour une opération donnée, il n'existe au plus qu'un seul nombre j tel que j transformé par une étape donnée aboutit à i.
Pour les opérations de type 1, cela est évident. Pour les opérations de type 2, nous pouvons le démontrer par l'absurde : s'il existait deux nombres distincts j₁ et j₂ (j₁ < j₂ < i) qui, après transformation, aboutissent tous deux à i, nous obtiendrions une contradiction en raison des propriétés de la multiplication et de la fonction d'arrondi supérieur.
Cette propriété nous permet d'adopter une approche plus efficace : pour chaque valeur atteignable, nous appliquons l'opération de manière répétée jusqu'à ce que nous atteignions une valeur déjà vue ou dépassions m.
Complexité temporelle : toujours O(n × m) en pratique, mais avec une constante plus favorable
Points d'attention
- L'arrondi supérieur doit être implémenté avec précision, en évitant les erreurs de flottants
- Les entiers standard (int) risquent de déborder, il faut utiliser des entiers 64 bits
Implémentation
Méthode 1 : Programmation dynaimque classique
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
using LL = long long;
const int MAXM = 100005;
const LL INF = LLONG_MAX;
LL dp[MAXM], etapes[MAXM];
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
dp[i] = INF;
}
for(int i = 1; i <= n; ++i) {
double opt, x1, y;
cin >> opt >> x1 >> y;
double x = x1 / 100000.0;
for(int j = 0; j <= m; ++j) {
if(dp[j] == INF) etapes[j] = INF;
else etapes[j] = 0;
}
for(int j = 0; j <= m; ++j) {
if(dp[j] == INF) continue;
LL nouvelle_valeur;
if(opt == 1) {
nouvelle_valeur = (LL)ceil(j + x);
} else {
nouvelle_valeur = (LL)ceil(j * x1 / 100000);
}
if(nouvelle_valeur <= m && etapes[j] + 1 <= y) {
if(etapes[j] + 1 < etapes[nouvelle_valeur]) {
dp[nouvelle_valeur] = i;
etapes[nouvelle_valeur] = etapes[j] + 1;
}
}
}
}
for(int i = 1; i <= m; ++i) {
if(dp[i] == INF) cout << "-1 ";
else cout << dp[i] << " ";
}
return 0;
}
</climits></cmath></vector></iostream>
Méthode 2 : Approche optimisée
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const int DIV = 100000;
// Fonction d'arrondi supérieur efficace
inline LL arrondi_sup(LL x, LL y) {
return (x + y - 1) / y;
}
int main() {
int T, M;
cin >> T >> M;
// Tableaux pour suivre les valeurs atteignables et les réponses
vector<bool> atteignable(M + 1, false);
atteignable[0] = true;
vector<int> reponse(M + 1, -1);
reponse[0] = 0;
for (int etape = 1; etape <= T; ++etape) {
auto nouvel_atteignable = atteignable;
int type;
LL x, y;
cin >> type >> x >> y;
// Définir l'opération en fonction du type
auto appliquer_operation = [&] (LL &courant) {
if (type == 1) {
courant = courant + arrondi_sup(x, DIV);
} else {
courant = arrondi_sup(courant * x, DIV);
}
};
// Parcourir toutes les valeurs atteignables
for (int k = 0; k <= M; ++k) {
if (atteignable[k]) {
LL courant = k;
appliquer_operation(courant);
// Appliquer l'opération de manière répétée
for (int a = 1; a <= y;) {
if (courant > M) break;
if (atteignable[courant]) break;
nouvel_atteignable[courant] = true;
reponse[courant] = etape;
++a;
appliquer_operation(courant);
}
}
}
atteignable = nouvel_atteignable;
}
// Afficher les résultats
for (int i = 1; i <= M; ++i)
cout << reponse[i] << " ";
cout << endl;
}
</int></bool></vector></iostream>