J'ai fait un programme pour résoudre ce problème de l'ACM.
Les bâtonnets d'allumettes sont des outils idéaux pour représenter les nombres. Une façon courante de représenter les dix chiffres décimaux avec des allumettes est la suivante :
C'est identique à la façon dont les chiffres sont affichés sur un réveil ordinaire. Avec un nombre donné d'allumettes, vous pouvez générer un large éventail de chiffres. Nous nous demandons quels sont les nombres les plus petits et les plus grands qui peuvent être créés en utilisant toutes vos allumettes.
Entrée
Sur la première ligne un nombre positif : le nombre de testcases, au maximum 100. Après cela, par cas de test :
Une ligne avec un nombre entier n (2 n 100) : le nombre d'allumettes que vous avez. Sortie
Par cas d'essai :
Une ligne avec le plus petit et le plus grand nombre que vous pouvez créer, séparés par un espace. Les deux nombres doivent être positifs et ne pas contenir de zéros en tête. Exemple de saisie
4 3 6 7 15 Exemple de sortie
7 7 6 111 8 711 108 7111111
Le problème est qu'il est beaucoup trop lent de le résoudre pour 100 allumettes. L'arbre de recherche est trop grand pour le forcer brutalement.
Voici les résultats des 10 premiers :
2 : 1 1
3 : 7 7
4 : 4 11
5 : 2 71
6 : 6 111
7 : 8 711
8 : 10 1111
9 : 18 7111
10 : 22 11111
Le schéma pour les maximums est facile mais je ne vois pas de raccourci pour les minimums. Quelqu'un peut-il suggérer une meilleure façon de résoudre ce problème ? Voici le code que j'ai utilisé :
#include <iostream>
#include <string>
using namespace std;
#define MAX 20 //should be 100
//match[i] contains number of matches needed to form i
int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string mi[MAX+1], ma[MAX+1];
char curr[MAX+1] = "";
//compare numbers saved as strings
int mycmp(string s1, string s2)
{
int n = (int)s1.length();
int m = (int)s2.length();
if (n != m)
return n - m;
else
return s1.compare(s2);
}
//i is the current digit, used are the number of matchsticks so far
void fill(int i, int used)
{
//check for smaller and bigger values
if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
if (mycmp(curr, ma[used]) > 0) ma[used] = curr;
//recurse further, don't start numbers with a zero
for (int a = i ? '0' : '1'; a <= '9'; a++) {
int next = used + match[a-'0'];
if (next <= MAX) {
curr[i] = a;
curr[i+1] = '\0';
fill(i + 1, next);
}
}
}
int main()
{
//initialise
for (int i = 0; i <= MAX; i++) {
mi[i] = string(MAX, '9');
ma[i] = "0";
}
//precalculate the values
fill(0, 0);
int n;
cin >> n;
//print those that were asked
while (n--) {
int num;
cin >> num;
cout << mi[num] << " " << ma[num] << endl;
}
return 0;
}EDIT : J'ai fini par utiliser la solution de la programmation dynamique. J'ai déjà essayé avec la programmation dynamique, mais je m'amusais avec un tableau d'états à deux dimensions. Les solutions proposées ici sont bien meilleures. Merci !
