I made a program to solve this problem from the ACM.
Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:
This is identical to how numbers are displayed on an ordinary alarm clock. With a given number of matchsticks you can generate a wide range of numbers. We are wondering what the smallest and largest numbers are that can be created by using all your matchsticks.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have. Output
Per testcase:
One line with the smallest and largest numbers you can create, separated by a single space. Both numbers should be positive and contain no leading zeroes. Sample Input
4 3 6 7 15 Sample Output
7 7 6 111 8 711 108 7111111
The problem is that it's way too slow to solve it for 100 matchsticks. The search tree is too big to bruteforce it.
Here are the results for the 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 for the maximums is easy but I don't see a shortcut for the minimums. Can someone suggest a better way to solve this problem? Here is the code I used:
#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 : I ended up using the dynamic programming solution. I tried it with dp before but I was messing around with a two-dimensional state array. The solutions here are much better. Thanks!
In order to find the result :
Every digit should be chosen so that there exists a solution for remaining digits. Each digit requires between 2 and 7 matches. So you must choose the smallest Nth "top" digit that leaves the number of remaining matches between 2*(N-1) and 7*(N-1).
Do not forget that 0 has to be excluded from the search for the most significant digit of the result.
As a sidenote, one reason which makes this algorithm work is the fact that there is at least one corresponding digit for every value (of matches) between 2 and 7.
EDIT : example for 10 matches
10 matches --> 2 digits
Acceptable number of matches for top digit = between 3 and 7.
Smallest digit which requires between 3 and 7 matches -> 2 (which takes 5 matches), 0 being excluded.
Chosen first digit = 2
5 remaining matches -->
Acceptable number of matches for second (and in this case last) digit = exactly 5
Smallest digit which requires 5 matches -> 2
Chosen second digit = 2
Result = 22.
EDIT code for this 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;
for (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));
for (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 i = 2 ; i <= 100 ; ++i )
{
std::cout << i << " " << minNumberForMatches(i) << std::endl;
}
}