Databases
StackOverflow2013
Postsdbo
POAlgorithm to make numbers from match sticks
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm to make numbers from match sticks
    primarykey
    data
    text
    <p>I made a program to solve <a href="http://acm.uva.es/archive/nuevoportal/data/problem.php?p=4292" rel="nofollow">this problem</a> from the ACM. </p> <blockquote> <p>Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:</p> <p>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.</p> <p>Input</p> <p>On the first line one positive number: the number of testcases, at most 100. After that per testcase:</p> <p>One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have. Output</p> <p>Per testcase:</p> <p>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</p> <p>4 3 6 7 15 Sample Output</p> <p>7 7 6 111 8 711 108 7111111</p> </blockquote> <p>The problem is that it's way too slow to solve it for 100 matchsticks. The search tree is too big to bruteforce it.</p> <p>Here are the results for the first 10:</p> <p>2: 1 1</p> <p>3: 7 7</p> <p>4: 4 11</p> <p>5: 2 71</p> <p>6: 6 111</p> <p>7: 8 711</p> <p>8: 10 1111</p> <p>9: 18 7111</p> <p>10: 22 11111</p> <p>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:</p> <pre><code> #include &lt;iostream&gt; #include &lt;string&gt; 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]) &lt; 0) mi[used] = curr; if (mycmp(curr, ma[used]) &gt; 0) ma[used] = curr; //recurse further, don't start numbers with a zero for (int a = i ? '0' : '1'; a &lt;= '9'; a++) { int next = used + match[a-'0']; if (next &lt;= MAX) { curr[i] = a; curr[i+1] = '\0'; fill(i + 1, next); } } } int main() { //initialise for (int i = 0; i &lt;= MAX; i++) { mi[i] = string(MAX, '9'); ma[i] = "0"; } //precalculate the values fill(0, 0); int n; cin &gt;&gt; n; //print those that were asked while (n--) { int num; cin &gt;&gt; num; cout &lt;&lt; mi[num] &lt;&lt; " " &lt;&lt; ma[num] &lt;&lt; endl; } return 0; } </code></pre> <p><strong>EDIT</strong> : 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!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USiCodez
    1. USJasper
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgorithm to make numbers from match sticks
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAlgorithm to make numbers from match sticks
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POAlgorithm to make numbers from match sticks
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThat's the problem with recursion. While I am not very sure if it applies to your problem but have you heard of "dynamic programming?" Most of the programming competition questions actually require a dynamic programming solution.
      singulars
      1. POAlgorithm to make numbers from match sticks
      1. USJaywalker
    2. COThe result can be obtained in linear complexity. See my answer.
      singulars
      1. POAlgorithm to make numbers from match sticks
      1. USBenoît
    3. COThis question is now useless because the offsite link is now dead. This just goes to show why you shouldn't link to offsite questions without summarising them in the post.
      singulars
      1. POAlgorithm to make numbers from match sticks
      1. USRobin Green
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload