Algorithme pour faire des nombres à partir de bâtons d'allumettes

Question

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 !

Answer 1

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <map>
using namespace std;

int main()
{
//  freopen("22.txt", "r", stdin);
    vector<char> count(10);
    map<int, char> Min_1;
    Min_1[0] = '8';
    Min_1[2] = '1';
    Min_1[3] = '7';
    Min_1[4] = '4';
    Min_1[5] = '2';
    count[0] = '6';
    count[1] = '2';
    count[2] = '5';
    count[3] = '5';
    count[4] = '4';
    count[5] = '5';
    count[6] = '6';
    count[7] = '3';
    count[8] = '7';
    count[9] = '6';
    int N = 99, P = 2;
    cin >> N;
    while(N --)
    {
        cin >> P;
        vector<char> min, max;
        int a = P, b = P;
        int total = (a + 6) / 7;
        int left = a % 7;
        bool first = true;
        char lastInsert = 0;
        while(a != 0)
        {
            if(total == 1)
            {
                if(left != 6)
                {
                    min.push_back(Min_1[left]);
                }else if(left == 6)
                {
                    if(!first)
                        min.push_back('0');
                    else
                        min.push_back('6');
                }
                break;
            }
            if(left == 0)
            {
                min.insert(min.end(), total, '8');
                break;
            }else{
                if(first && left <= 2)
                {
                    min.push_back('1');
                    lastInsert = 1;
                }else if(first && left < 6)
                {
                    min.push_back('2');
                    lastInsert = 2;
                }else if(first && left == 6)
                {
                    min.push_back('6');
                    lastInsert = 6;
                }else if(!first)
                {
                    min.push_back('0');
                    lastInsert = 0;
                } 
            }
            int temp = count[lastInsert] - '0';
            a -= temp;
            left = a % 7;
            total = (a + 6) / 7;
            first = false;
        }

        if(b % 2 == 1)
        {
            max.push_back('7');
            max.insert(max.end(), (b - 3) / 2, '1');
        }else{
            max.insert(max.end(), b / 2, '1');
        }
        string res_min = string(min.begin(), min.end());
        string res_max = string(max.begin(), max.end());
        cout << res_min << " " << res_max << endl;
        P ++;
    }
    return 0;
}

Voici ma réponse, je souhaite qu'elle soit utile