c++ - Algorithm to make numbers from match sticks -

i made program solve this problem acm.

matchsticks ideal tools represent numbers. common way represent ten decimal digits matchsticks following:

this identical how numbers displayed on ordinary alarm clock. given number of matchsticks can generate wide range of numbers. wondering smallest , largest numbers can created using matchsticks.

input

on first line 1 positive number: number of testcases, @ 100. after per testcase:

one line integer n (2 ≤ n ≤ 100): number of matchsticks have. output

per testcase:

one line smallest , largest numbers can create, separated single space. both numbers should positive , contain no leading zeroes. sample input

4 3 6 7 15 sample output

7 7 6 111 8 711 108 7111111

the problem it's way slow solve 100 matchsticks. search tree big bruteforce it.

here results first 10:

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

the pattern maximums easy don't see shortcut minimums. can suggest better way solve problem? here code used:

    #include <iostream>     #include <string>     using namespace std;      #define max 20 //should 100      //match[i] contains number of matches needed form     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 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 current digit, used number of matchsticks far     void fill(int i, int used)     {         //check smaller , 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 0         (int = ? '0' : '1'; <= '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          (int = 0; <= max; i++) {             mi[i] = string(max, '9');             ma[i] = "0";         }          //precalculate values         fill(0, 0);          int n;         cin >> n;          //print asked         while (n--) {             int num;             cin >> num;             cout << mi[num] << " " << ma[num] << endl;         }          return 0;     } 

edit : ended using dynamic programming solution. tried dp before messing around two-dimensional state array. solutions here better. thanks!

in order find result :

• first find minimal number of digits smallest number
• then proceed significant digit least significant one.

every digit should chosen there exists solution remaining digits. each digit requires between 2 , 7 matches. must choose smallest nth "top" digit leaves number of remaining matches between 2*(n-1) , 7*(n-1).

do not forget 0 has excluded search significant digit of result.

as sidenote, 1 reason makes algorithm work fact there @ least 1 corresponding digit every value (of matches) between 2 , 7.

edit : example 10 matches 10 matches --> 2 digits
acceptable number of matches top digit = between 3 , 7.
smallest digit requires between 3 , 7 matches -> 2 (which takes 5 matches), 0 being excluded.
chosen first digit = 2

5 remaining matches -->
acceptable number of matches second (and in case last) digit = 5
smallest digit requires 5 matches -> 2
chosen second digit = 2

result = 22.

edit code problem

#include <iostream> #include <vector>  std::vector<int> nbmatchesfordigit;  long long minnumberformatches(unsigned int nbmatches) {     int nbmaxmatchesforonedigit = 7;     int nbminmatchesforonedigit = 2;     int remainingmatches = nbmatches;     int nbdigits = 1 + nbmatches / nbmaxmatchesforonedigit;      long long result = 0;     (int iddigit = 0 ; iddigit < nbdigits ; ++iddigit )     {         int minmatchestouse = std::max(nbminmatchesforonedigit, remainingmatches - nbmaxmatchesforonedigit * (nbdigits - 1 - iddigit));         int maxmatchestouse = std::min(nbmaxmatchesforonedigit, remainingmatches - nbminmatchesforonedigit * (nbdigits - 1 - iddigit));         (int digit = iddigit > 0 ? 0 : 1 ; digit <= 9 ; ++digit )         {             if( nbmatchesfordigit[digit] >= minmatchestouse &&                  nbmatchesfordigit[digit] <= maxmatchestouse )             {                 result = result * 10 + digit;                 remainingmatches -= nbmatchesfordigit[digit];                 break;             }         }     }     return result; }  int main() {     nbmatchesfordigit.push_back(6);     nbmatchesfordigit.push_back(2);     nbmatchesfordigit.push_back(5);     nbmatchesfordigit.push_back(5);     nbmatchesfordigit.push_back(4);     nbmatchesfordigit.push_back(5);     nbmatchesfordigit.push_back(6);     nbmatchesfordigit.push_back(3);     nbmatchesfordigit.push_back(7);     nbmatchesfordigit.push_back(6);      for( int = 2 ; <= 100 ; ++i )     {         std::cout << << " " << minnumberformatches(i) << std::endl;     } }