Thread: Need help debugging my code

A brute force algorithm could be used, but i would like to see a nice description of your own once you find one.

Google's Translator is far better than Babelfish, so you know.

site will redirect stdinput and output, so your program should read from stdinput and output to stdoutput

Note that you should specify the size of your buffer - 1 to scanf because it will read the number of chars you specify. You need space for the NULL char too.
Instead of writing from a file, read chunks from stdin instead, just as if inputting info from a user.
I believe this is what it's all about.

So should I start the program with something like:

No

Is there a way to know the length of the input?

No, and no need.
When you read a number of blocks and it is zero - exit your main loop

So in pseudocode it will be something like

Code:

while(read number)
{
   if(number == 0) break;
   for(i=0;i<number;i++)
   {
      read line;
      split it in block sizes;
   }
   order blocks;
   count piramid hight and ouput it;
}

Thanks! Now I finally scored something =P I got 20/100 points, now I beleive the problem is only whithin my algorithm.

In case anyone wants to know:

Code:

#include <stdio.h>

struct caixas
{
    unsigned int x[5000];
    unsigned int y[5000];
    unsigned int area[5000];  
};

int main (int argc, char *argv[])
{
    struct caixas caixa;
    int start = 1, num, i, n, maiorArea, velhoY = 0;
    int velhoX = 0, teste = 1, numeroBlocos, num2, nn;

    while (true)
    {
          if (start)
          {              
              if (scanf("&#37;d", &num) == EOF || !num)
                 return 0;
                 
              num2 = num;
              velhoX = velhoY = 0;
              start = 0;
          } else {

              numeroBlocos = 0;
              
              for (i = 0; i < num2; i++)
              {
                  scanf("%d %d", &caixa.x[i], &caixa.y[i]);
                  caixa.area[i] = caixa.x[i] * caixa.y[i]; 
              }

              while (num--)
              {                  
                  maiorArea = 0;

                  for (n = 0; n < num2; n++)
                  {
                      if (caixa.area[n] > maiorArea)
                      {
                          maiorArea = caixa.area[n];
                          nn = n;
                      }
                  }

                  caixa.area[nn] = 0;
                  
                  if ((!velhoX && !velhoY) || (caixa.x[nn] <= velhoX && caixa.y[nn] <= velhoY) || (caixa.x[nn] <= velhoY && caixa.y[nn] <= velhoX))
                  {
                      velhoX = caixa.x[nn];
                      velhoY = caixa.y[nn];
                      numeroBlocos++;
                  }
              }

              printf("Teste %d\n%d\n\n", teste++, numeroBlocos);
          
              start = 1;
          }
    }
    return 0;
}

I got one more question now though...

Since I altered the program to read from stdin I can not test it here... How do I make the input?

Just put the input set in a text file (like boxes.txt) and execute your program on the command line like this:

boxes < boxes.txt

Ok now here's a description of how I solved the problem:

Code:

1) Read in N (the number of boxes)
2) Read in each box's length and width into an array (I used an array of structs)
   If a box's length is less than its width, swap the two values
   (this is needed to make sorting easier)
4) Sort (in increasing order) the array of boxes by their largest dimension, if two boxes have
   the same largest dimension, sort by the sum of their dimensions
5) See the following pseudo-code:

   // stacks[n] = the number of boxes in the stack with box n at the bottom
   // This is initialized to all 1's since each box is initially in its own stack
   stacks = integer array of size N
   globalMax = 1
   for j in 1 to N-1
      localMax = stacks[j]
      for k in 0 to j-1
         if box[k] fits on top of box[j]
            localMax = max(localMax, stacks[k] + stacks[j]);
      stacks[j] = localMax
      globalMax = max(globalMax, localMax)

6) The answer is now in globalMax

Here's a basic skeleton of my program:

int main(void) {
   // declare variables

   while (1) {
      // read in N
      if (N == 0) break;

      // create an array big enough to hold N boxes (optionally you could just use
      // a statically allocated array large enough to hold the max value for N)

      // read in boxes

      // sort boxes

      // do algorithm

      // print result
   }
}

The algorithmic part operates in O(N^2) (approximately N^2 / 2). The sort, assuming you use a decent sorting algorithm, should take O(n log n). Is this the optimal solution? Probably not. But it works, and yes I submitted it and it gets all 100 points.