103 - Stacking Boxes

jk4837 · Post by **jk4837** » Sat Aug 11, 2007 5:55 pm

I got a WA in #103, but I believe the answer is right.
There have a sample I/O I have tried.

Sample Input

8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9

Sample Output

4
7 2 5 6

But my answer is:
4
7 2 5 8
Is it right and can be accepted?

Here is my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
main()
{    int i,j,t,m,a[32][12]={0},k,n,tmp,s[32]={0},b[32]={0},e[32]={0},p=0;
 
while(scanf("%d %d",&k,&n)==2) 
{    for(i=1;i<=k;i++) 
     {    b[i]=i; 
          for(j=1;j<=n;j++)
          {   scanf("%d",&a[i][j]); 
     }    } 
     for(t=1;t<=k;t++)
     {   for(i=n;i>1;i--)
         {   for(j=1;j<i;j++) 
             {   if(a[t][j]>a[t][j+1]) 
                 {   tmp=a[t][j+1];
                     a[t][j+1]=a[t][j]; 
                     a[t][j]=tmp; 
         }   }   }   
         s[t]=a[t][1]; 
     }
     for(i=k;i>1;i--)
     {   for(j=1;j<i;j++) 
         {   if(s[j]>=s[j+1]) 
             {   tmp=s[j+1];
                 s[j+1]=s[j]; 
                 s[j]=tmp;
                 tmp=b[j+1];
                 b[j+1]=b[j]; 
                 b[j]=tmp;  
     }    }   }    
     for(j=1;j<k;j++)       
     {    if(s[j]==s[j+1]) 
          {    t=1;
               while(a[b[j]][t]==a[b[j+1]][t]) 
                   t++;
               if(a[b[j]][t]>a[b[j+1]][t])             
               {    tmp=s[j+1];
                    s[j+1]=s[j]; 
                    s[j]=tmp;
                    tmp=b[j+1];
                    b[j+1]=b[j]; 
                    b[j]=tmp; 
     }    }    } 
     t=1;
     e[t]=b[1]; 
     m=1; 
     for(i=1;i<k;i++)
     {    for(j=1;j<=n;j++) 
          {  if(a[b[m]][j]>=a[b[i+1]][j])
              {   p=1; 
                  break; 
              } 
          } 
          if(p==0)
          {   t++;
              e[t]=b[i+1];
              m=i+1; 
          } 
          p=0; 
     } 
     printf("%d\n",t);
     for(i=1;i<=t;i++)
         printf("%d ",e[i]);
     printf("\n"); 
}   /* while */ 
}   /* main */

Jan · Post by **Jan** » Sat Aug 11, 2007 9:08 pm

Search the board first. Dont open a new thread if there is one already.

quinine · Post by **quinine** » Sat Nov 03, 2007 7:53 pm

Hi all,

My code produces the correct output for all the test input I could find on this board, but I still get WA. I would be glad for any help. Thanks!

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int n; // no. of dimensions n

struct Box {
    int dims[10]; // dimensions
    int sublen, inputno; // subsequence length, 'name ' of the box
    Box *pre; // predecessor for longest subsequence
};

int comp(const void* a, const void* b) { // for qsort
    int res = *(int*)b - *(int*)a;
    return res;
}

int fits(const void *a, const void* b) { // tests whether one box fits another
    int i, isfit;
    bool issmaller = true, isbigger = false;
    for(i=0;i<n;i++) {
        if ((*(Box*)a).dims[i] <= (*(Box*)b).dims[i]) { issmaller=false; break; }
    }
    if (!issmaller && i==0) {
        isbigger = true;
        for(i=0;i<n;i++) {
            if ((*(Box*)a).dims[i] >= (*(Box*)b).dims[i]) { isbigger=false; break; }
        }
    }
    if (issmaller) isfit = -2; // b is smaller than a
    else if (isbigger) isfit = 2; // b is larger
    else isfit = -1; // neither fit the other
    return isfit;
}

int main () {
    int k, maxlen; // no. of boxes k
    Box boxes[31], *boxptr, tmpbox;
 
    while (scanf("%d %d", &k, &n) != EOF) {
        // set vars to default values
        maxlen = 0; // must be < 1 so sequence is still generated when sublen = 1
        boxptr = NULL;
        for (int i=0; i<31; i++) {
            boxes[i].pre = NULL;
            boxes[i].sublen = 1;
        }
        
        // read box data
        for (int i=0;i<k;i++) {
            for (int j=0;j<n;j++) {
                scanf("%d", &boxes[i].dims[j]);
            }
            boxes[i].inputno = i+1;
            qsort(boxes[i].dims, n, sizeof(int), comp);
        }
        
        // bubblesort the boxes (just in case qsort is giving problems)
        for (int i=0; i<k; i++) {
            for (int j=k-1; j>i; j--) {
                if (fits(&boxes[j], &boxes[j-1]) < 0) {
                    tmpbox = boxes[j];
                    boxes[j] = boxes[j-1];
                    boxes[j-1] = tmpbox;
                }
            }
        }
        
        // longest subsequence
        for(int i=0; i<k-1; i++) {
            for (int j=i+1; j<k; j++) {
                if (fits(&boxes[i], &boxes[j]) == -2) {
                    boxes[j].sublen = boxes[i].sublen + 1;
                    boxes[j].pre = &boxes[i];
                }
            }
        }
        for (int i=0; i<k; i++) {
            if (maxlen < boxes[i].sublen) {
                maxlen = boxes[i].sublen;
                boxptr = &boxes[i];
            }
        }

        printf("%d\n", maxlen);
        while (boxptr != NULL) {
            printf("%d ", (*boxptr).inputno);
            boxptr = (*boxptr).pre;
        }
        printf("\n");
    }
    return 0;
}

Leeon · Post by **Leeon** » Thu Sep 04, 2008 4:15 pm

Hi, I'm still getting WA and I'm really desperate, where the problem should be. Could anyone check my Input against Output?

<Input>

Code: Select all

1 1
1
5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
10 10
01 05 02 06 07 02 06 03 02 04
23 15 65 12 68 75 12 36 82 62
45 32 48 98 71 12 35 85 25 32
78 95 25 63 21 57 85 47 89 63
41 25 89 63 21 45 87 98 91 37
83 84 63 51 93 64 82 71 96 38
99 87 35 19 64 28 34 65 81 36
85 42 64 25 36 34 12 36 64 18
39 45 54 16 45 18 12 31 48 25
12 13 02 06 08 09 09 04 03 01
5 1
2
3
6
7
1
1 1
2
15 9
01 02 03 04 05 06 07 08 09
02 03 04 05 06 07 08 09 10
03 04 05 06 07 08 09 10 11
04 05 06 07 08 09 10 11 12
05 06 07 08 09 10 11 12 13
06 07 08 09 10 11 12 13 14
07 08 09 10 11 12 13 14 15
08 09 10 11 12 13 14 15 16
09 10 11 12 13 14 15 16 17
10 11 12 13 14 15 16 17 18
11 12 13 14 15 16 17 18 19
12 13 14 15 16 17 18 19 20
13 14 15 16 17 18 19 20 21
14 15 16 17 18 19 20 21 22
15 16 17 18 19 20 21 22 23
3 3
3 1 1
1 2 1
1 1 1
30 10
001000 002000 003000 004000 005000 006000 007000 008000 009000 010000
002000 003000 004000 005000 006000 007000 008000 009000 010000 011000
003000 004000 005000 006000 007000 008000 009000 010000 011000 012000
004000 005000 006000 007000 008000 009000 010000 011000 012000 013000
005000 006000 007000 008000 009000 010000 011000 012000 013000 014000
006000 007000 008000 009000 010000 011000 012000 013000 014000 015000
007000 008000 009000 010000 011000 012000 013000 014000 015000 016000
008000 009000 010000 011000 012000 013000 014000 015000 016000 017000
009000 010000 011000 012000 013000 014000 015000 016000 017000 018000
010000 011000 012000 013000 888888 015000 016000 017000 018000 019000
011000 012000 013000 014000 015000 016000 017000 018000 019000 020000
012000 013000 014000 015000 016000 017000 018000 019000 020000 021000
013000 014000 015000 016000 017000 018000 019000 020000 021000 022000
014000 015000 016000 017000 018000 019000 020000 021000 022000 023000
015000 016000 017000 018000 019000 020000 021000 022000 023000 024000
016000 017000 018000 019000 020000 021000 022000 023000 024000 025000
017000 018000 019000 020000 021000 022000 023000 024000 025000 026000
018000 019000 888888 021000 022000 023000 024000 025000 026000 027000
019000 020000 021000 022000 023000 024000 025000 026000 027000 028000
020000 021000 022000 023000 024000 025000 026000 027000 028000 029000
021000 022000 023000 024000 025000 026000 027000 028000 029000 030000
022000 023000 024000 025000 026000 027000 028000 029000 030000 031000
023000 024000 025000 026000 027000 028000 029000 030000 031000 032000
024000 025000 026000 027000 028000 029000 030000 031000 032000 033000
025000 026000 027000 028000 029000 030000 031000 032000 033000 034000
026000 027000 028000 029000 030000 031000 032000 033000 034000 035000
027000 028000 029000 030000 031000 032000 033000 034000 035000 036000
028000 029000 030000 031000 032000 033000 034000 035000 036000 037000
029000 030000 031000 032000 033000 034000 035000 036000 037000 038000
030000 031000 032000 033000 034000 035000 036000 037000 038000 039000
10 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
6 1
6
8
10
4
5
4
30 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
200 201 202 203 204 205 206 207 208 209 
100 101 102 103 104 105 106 107 108 109 
300 301 302 303 304 305 306 307 308 309 
200 201 202 203 204 205 206 207 208 209 
100 101 102 103 104 105 106 107 108 109 
300 301 302 303 304 305 306 307 308 309 
400 401 402 403 404 405 406 407 408 409 
500 501 502 503 504 505 506 507 508 509 
411 412 413 414 415 416 417 418 419 420 
521 522 523 524 525 526 527 528 529 530
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
30 10
30 31 32 33 34 35 36 37 38 39
29 30 31 32 33 34 35 36 37 38
28 29 30 31 32 33 34 35 36 37
27 28 29 30 31 32 33 34 35 36
26 27 28 29 30 31 32 33 34 35
25 26 27 28 29 30 31 32 33 34
24 25 26 27 28 29 30 31 32 33
23 24 25 26 27 28 29 30 31 32
22 23 24 25 26 27 28 29 30 31
21 22 23 24 25 26 27 28 29 30
20 21 22 23 24 25 26 27 28 29
19 20 21 22 23 24 25 26 27 28
18 19 20 21 22 23 24 25 26 27
17 18 19 20 21 22 23 24 25 26
16 17 18 19 20 21 22 23 24 25
15 16 17 18 19 20 21 22 23 24
14 15 16 17 18 19 20 21 22 23
13 14 15 16 17 18 19 20 21 22
12 13 14 15 16 17 18 19 20 21
11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
9 10 11 12 13 14 15 16 17 18
8 9 10 11 12 13 14 15 16 17
7 8 9 10 11 12 13 14 15 16
6 7 8 9 10 11 12 13 14 15
5 6 7 8 9 10 11 12 13 14
4 5 6 7 8 9 10 11 12 13
3 4 5 6 7 8 9 10 11 12
2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10
10 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
17 4
859 397 577 913
757 501 912 171
836 991 761 899
647 446 709 426
295 211 586 775
750 619 733 153
192 999 205 89
264 552 958 328
309 705 412 596
94 569 98 520
529 849 162 453
299 3 766 227
748 539 511 820
778 562 725 523
497 200 103 880
903 737 701 423
813 788 691 857
8 3
1 10 1
8 8 8
4 6 6
7 5 7
5 2 1
1 2 1
6 2 4
5 5 3
3 3
1 5 10
1 4 18
2 6 11 
5 2
41 595
291 836
350 602
483 548
537 624
30 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
400 401 402 403 404 405 406 407 408 409
500 501 502 503 504 505 506 507 508 509
411 412 413 414 415 416 417 418 419 420
521 522 523 524 525 526 527 528 529 530
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
2 1
1
1
25 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
24
5 3
1 2 3
2 3 4
3 4 5
4 5 6
6 7 8
3 3
1 1 1
1 2 2
1 3 3

Code: Select all

1
1
5
3 1 2 4 5
4
7 2 5 6
3
1 9 4
5
5 1 2 3 4
1
1
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
3
28
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 29 30
1
1
5
4 5 1 2 3
13
1 2 3 4 5 21 12 11 13 17 19 18 20
30
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1
1
6
10 9 4 14 17 3
5
6 8 3 4 2
2
1 3
3
1 3 5
13
1 2 3 4 5 21 12 11 13 17 19 18 20
1
1
24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
5
1 2 3 4 5
1
1

My last submission WA was 6631462.
Thanks!

tryit1 · Post by **tryit1** » Mon Sep 08, 2008 3:20 pm

do we have an algorithm better than n^2 ?

i put box x inside box y and update the best y

Sedefcho · Post by **Sedefcho** » Sun Jan 18, 2009 5:24 pm

This is in case somebody needs test data.

Here is the correct output for the input posted above by Leeon. I hope the input
posted by Leeon is not the real Test Input used by the Online Judge. In that case
this posting would be a complete spoiler and should be deleted.

INPUT

Code: Select all

1 1
1
5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
10 10
01 05 02 06 07 02 06 03 02 04
23 15 65 12 68 75 12 36 82 62
45 32 48 98 71 12 35 85 25 32
78 95 25 63 21 57 85 47 89 63
41 25 89 63 21 45 87 98 91 37
83 84 63 51 93 64 82 71 96 38
99 87 35 19 64 28 34 65 81 36
85 42 64 25 36 34 12 36 64 18
39 45 54 16 45 18 12 31 48 25
12 13 02 06 08 09 09 04 03 01
5 1
2
3
6
7
1
1 1
2
15 9
01 02 03 04 05 06 07 08 09
02 03 04 05 06 07 08 09 10
03 04 05 06 07 08 09 10 11
04 05 06 07 08 09 10 11 12
05 06 07 08 09 10 11 12 13
06 07 08 09 10 11 12 13 14
07 08 09 10 11 12 13 14 15
08 09 10 11 12 13 14 15 16
09 10 11 12 13 14 15 16 17
10 11 12 13 14 15 16 17 18
11 12 13 14 15 16 17 18 19
12 13 14 15 16 17 18 19 20
13 14 15 16 17 18 19 20 21
14 15 16 17 18 19 20 21 22
15 16 17 18 19 20 21 22 23
3 3
3 1 1
1 2 1
1 1 1
30 10
001000 002000 003000 004000 005000 006000 007000 008000 009000 010000
002000 003000 004000 005000 006000 007000 008000 009000 010000 011000
003000 004000 005000 006000 007000 008000 009000 010000 011000 012000
004000 005000 006000 007000 008000 009000 010000 011000 012000 013000
005000 006000 007000 008000 009000 010000 011000 012000 013000 014000
006000 007000 008000 009000 010000 011000 012000 013000 014000 015000
007000 008000 009000 010000 011000 012000 013000 014000 015000 016000
008000 009000 010000 011000 012000 013000 014000 015000 016000 017000
009000 010000 011000 012000 013000 014000 015000 016000 017000 018000
010000 011000 012000 013000 888888 015000 016000 017000 018000 019000
011000 012000 013000 014000 015000 016000 017000 018000 019000 020000
012000 013000 014000 015000 016000 017000 018000 019000 020000 021000
013000 014000 015000 016000 017000 018000 019000 020000 021000 022000
014000 015000 016000 017000 018000 019000 020000 021000 022000 023000
015000 016000 017000 018000 019000 020000 021000 022000 023000 024000
016000 017000 018000 019000 020000 021000 022000 023000 024000 025000
017000 018000 019000 020000 021000 022000 023000 024000 025000 026000
018000 019000 888888 021000 022000 023000 024000 025000 026000 027000
019000 020000 021000 022000 023000 024000 025000 026000 027000 028000
020000 021000 022000 023000 024000 025000 026000 027000 028000 029000
021000 022000 023000 024000 025000 026000 027000 028000 029000 030000
022000 023000 024000 025000 026000 027000 028000 029000 030000 031000
023000 024000 025000 026000 027000 028000 029000 030000 031000 032000
024000 025000 026000 027000 028000 029000 030000 031000 032000 033000
025000 026000 027000 028000 029000 030000 031000 032000 033000 034000
026000 027000 028000 029000 030000 031000 032000 033000 034000 035000
027000 028000 029000 030000 031000 032000 033000 034000 035000 036000
028000 029000 030000 031000 032000 033000 034000 035000 036000 037000
029000 030000 031000 032000 033000 034000 035000 036000 037000 038000
030000 031000 032000 033000 034000 035000 036000 037000 038000 039000
10 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
6 1
6
8
10
4
5
4
30 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
400 401 402 403 404 405 406 407 408 409
500 501 502 503 504 505 506 507 508 509
411 412 413 414 415 416 417 418 419 420
521 522 523 524 525 526 527 528 529 530
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
30 10
30 31 32 33 34 35 36 37 38 39
29 30 31 32 33 34 35 36 37 38
28 29 30 31 32 33 34 35 36 37
27 28 29 30 31 32 33 34 35 36
26 27 28 29 30 31 32 33 34 35
25 26 27 28 29 30 31 32 33 34
24 25 26 27 28 29 30 31 32 33
23 24 25 26 27 28 29 30 31 32
22 23 24 25 26 27 28 29 30 31
21 22 23 24 25 26 27 28 29 30
20 21 22 23 24 25 26 27 28 29
19 20 21 22 23 24 25 26 27 28
18 19 20 21 22 23 24 25 26 27
17 18 19 20 21 22 23 24 25 26
16 17 18 19 20 21 22 23 24 25
15 16 17 18 19 20 21 22 23 24
14 15 16 17 18 19 20 21 22 23
13 14 15 16 17 18 19 20 21 22
12 13 14 15 16 17 18 19 20 21
11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
9 10 11 12 13 14 15 16 17 18
8 9 10 11 12 13 14 15 16 17
7 8 9 10 11 12 13 14 15 16
6 7 8 9 10 11 12 13 14 15
5 6 7 8 9 10 11 12 13 14
4 5 6 7 8 9 10 11 12 13
3 4 5 6 7 8 9 10 11 12
2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10
10 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
17 4
859 397 577 913
757 501 912 171
836 991 761 899
647 446 709 426
295 211 586 775
750 619 733 153
192 999 205 89
264 552 958 328
309 705 412 596
94 569 98 520
529 849 162 453
299 3 766 227
748 539 511 820
778 562 725 523
497 200 103 880
903 737 701 423
813 788 691 857
8 3
1 10 1
8 8 8
4 6 6
7 5 7
5 2 1
1 2 1
6 2 4
5 5 3
3 3
1 5 10
1 4 18
2 6 11
5 2
41 595
291 836
350 602
483 548
537 624
30 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
400 401 402 403 404 405 406 407 408 409
500 501 502 503 504 505 506 507 508 509
411 412 413 414 415 416 417 418 419 420
521 522 523 524 525 526 527 528 529 530
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
2 1
1
1
25 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
24
5 3
1 2 3
2 3 4
3 4 5
4 5 6
6 7 8
3 3
1 1 1
1 2 2
1 3 3

OUTPUT

Code: Select all

1
1
5
3 1 2 4 5
4
7 2 5 6
2
10 2
5
5 1 2 3 4
1
1
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
3
28
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 29 30
1
1
5
6 5 1 2 3
13
28 7 8 9 10 26 15 14 16 17 19 18 20
30
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1
1
6
10 9 4 14 17 3
5
6 8 3 4 2
2
1 3
3
1 3 5
13
28 7 8 9 10 26 15 14 16 17 19 18 20
1
1
24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
5
1 2 3 4 5
1
1

Good luck to everyone who is still working on this old (and nice) problem.

shivampatel · Post by **shivampatel** » Tue Mar 10, 2009 6:16 pm

Out of the two outputs posted above, I could find Leeon's output matching mine.

For the 4th trace:
Leeon's following output seems correct
3
1 9 4

while the output in the second post is:
2
10 2

Even my program showed 3 boxes for this input. I don't know whether both my and Leeon's output are wrong or Sedefcho's output is incorrect.

Can someone comment ?

allenlam · Post by **allenlam** » Wed Jun 24, 2009 10:07 am

For case 4, my output is
3
1 2 4

It can be confirmed easily by manual checking.

I think 1 9 4 is also correct

Here is my version of output:

Code: Select all

1
1
5
3 1 2 4 5
4
7 2 5 6
3
1 2 4
5
5 1 2 3 4
1
1
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
1
28
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 29 30
1
1
5
4 5 1 2 3
13
1 2 3 4 5 21 12 11 13 17 19 18 20
30
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1
1
6
10 9 4 13 17 3
5
6 8 3 4 2
2
1 3
3
1 3 5
13
1 2 3 4 5 21 12 11 13 17 19 18 20
1
1
24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
5
1 2 3 4 5
1
1

Any comment?

willmetalufg · Post by **willmetalufg** » Tue Jun 08, 2010 4:14 pm

I'm trying to submmit this problem to the judge but I'm getting PE.
I'd like to know if there's any blank line or espaces that should be avoided in order to get AC.

willmetalufg · Post by **willmetalufg** » Tue Jun 08, 2010 4:15 pm

Ops.. the problem title is Stacking Boxes, sorry for that.

Nesszors · Post by **Nesszors** » Sat Feb 19, 2011 9:36 pm

I'm getting WA using the same algorithm described above. Here's my code:

import java.io.*;
import java.util.*;

public class Stack_Box
{
public static class box implements Comparable<box>
{
ArrayList<Integer> d= new ArrayList<Integer>();
Integer[] dim;
int index=0;
public box(String a, int i)
{
Scanner scan= new Scanner(a);
while(scan.hasNext())
d.add(new Integer(scan.next()));
dim=(Integer[])d.toArray(new Integer[0]);
Arrays.sort(dim);
index=i+1;
}
public int compareTo(box a)
{
if(contains(this,a))
return 1;
if(contains(a,this))
return -1;
return 0;
}
}
public static boolean contains(box one, box two)
{
for(int j=0; j<one.dim.length; j++)
if(one.dim[j]<=two.dim[j])
return false;

return true;
}
public static void main(String[] args)
{
try{
Scanner scan= new Scanner(System.in);
FileWriter fstream = new FileWriter("out.txt");
PrintWriter out = new PrintWriter(fstream);
while(scan.hasNextLine())
{
String s=scan.nextLine();
Scanner sc= new Scanner(s);
int k= Integer.parseInt(sc.next());
int n= Integer.parseInt(sc.next());
box[] b= new box[k];
for(int i=0; i<k; i++)
b= new box(scan.nextLine(), i);
Arrays.sort(b);
int[][] dp= new int[k][2];
int max=0;
int index=0;
for(int i=0; i<k; i++)
{
for(int j=0; j<i; j++)
{
if(contains(b,b[j]))
{
if(dp[j][0]+1>dp[0])
{
dp[0]=Math.max(dp[0],dp[j][0]+1);
dp[1]= j;
if(dp[0]>max)
{
max= dp[0];
index=i;
}
}
}

}
}
Stack<box> p= new Stack<box>();
System.out.println(max+1);
do
{
p.push(b[index]);
index= dp[index][1];
if(dp[index][0]==0 && p.size()>1)
p.push(b[index]);
}while(dp[index][0]>0);
String a="";
while(p.size()>0)
{
a+=p.pop().index+" ";
}
a=a.trim();
System.out.println(a);
}
}
catch (IOException e)
{e.printStackTrace();}
}

}

grover002 · Post by **grover002** » Tue May 17, 2011 4:21 am

I'm getting WA using the same algorithm described above. Here's my code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
bool comparer(pair < vector < int >,int > a,pair < vector < int >,int > b)
{
int i = 0;
for(;i < a.first.size();i++)
{
if(a.first < b.first) return true;
if(a.first > b.first) return false;
}
return true;
}
bool mayor(pair < vector < int >,int > a,pair < vector < int >,int > b)
{
// a > b
int i = 0;
for(;i < a.first.size();i++)
if(a.first <= b.first) return false;
return true;
}

int main()
{
vector < pair < vector <int>,int > > A;
int k,n,i,j,aux;
while(scanf("%d %d",&n,&k) != EOF){
for(i = 0;i < n;i++)
{
vector < int > B;
for(j = 0;j < k;j++){
scanf("%d",&aux);
B.push_back(aux);
}
sort(B.begin(),B.end());
A.push_back(make_pair(B,i + 1));
}
sort(A.begin(),A.end(),comparer);
int Q[n];
memset(Q,0,sizeof Q);
int may = 0;
for(i = 0;i < n;i++)
{
int maxi = 0;
for(j = 0;j < i;j++){
if(mayor(A,A[j]))
if(Q[j] > maxi) maxi = Q[j];
}
Q = maxi + 1;
may = max(may,Q);
}
int cont = 1;
printf("%d\n",may);
for(i = 0;i < n;i++)
{
if(Q == cont){
if(cont == may)
printf("%d\n",A[i].second);
else
printf("%d ",A[i].second);
cont++;
}
}
A.clear();
}
return 0;
}
plz help me!

zobayer · Post by **zobayer** » Sat Jun 18, 2011 11:48 am

Can you use code tags? your code is hardly readable...

You are not following the problem properly. For example, try these inputs:

Code: Select all

22 3
44 71 27
37 91 79
96 10 74
52 35 19
40 98 85
67 79 43
93 29 13
37 87 17
75 24 74
36 31 11
89 80 84
75 31 39
20 88 87
14 89 70
25 30 93
28 20 72
11 30 78
87 36 50
54 72 21
20 28 57
68 50 25
80 45 58
5 2
35 45
72 49
74 75
65 84
96 44
29 1
54
13
74
42
93
72
65
37
20
97
13
77
43
93
17
44
38
54
48
98
63
40
85
81
92
62
72
96
58
26 6
65 41 49 98 87 92
13 26 17 30 75 65
72 36 59 28 63 69
56 11 47 95 77 84
81 98 69 31 87 60
27 14 52 68 32 68
29 97 92 13 48 95
19 25 53 38 79 14
84 38 62 58 33 17
32 83 76 48 81 23
33 79 96 52 56 28
10 79 55 18 15 91
39 69 97 98 48 14
52 23 79 18 39 72
43 68 88 93 15 55
10 89 44 81 50 58
12 74 39 22 25 63
65 39 94 59 63 16
44 28 89 72 52 80
76 53 80 42 77 35
91 33 78 14 77 20
22 14 99 98 35 55
12 30 26 83 12 75
83 45 64 23 66 85
46 10 88 27 19 58
83 73 51 89 15 93
15 6
82 64 50 42 36 40
35 39 58 63 47 29
57 77 49 37 67 73
59 13 62 88 29 57
10 99 50 30 17 93
80 55 74 79 14 45
46 40 55 98 91 13
72 87 27 88 98 89
33 32 12 30 86 45
45 51 88 77 92 20
50 12 42 88 35 87
62 24 69 71 77 51
21 15 58 48 71 31
65 86 36 26 46 93
97 64 27 49 16 58
29 5
23 30 83 49 59
20 43 93 75 61
33 72 97 74 13
46 26 43 75 38
82 30 76 15 88
15 82 46 11 77
59 98 62 58 52
27 76 65 23 73
51 29 83 59 15
81 72 41 32 58
66 10 37 98 49
72 71 43 59 18
19 60 68 95 50
70 26 84 56 45
81 37 45 56 42
82 96 96 49 71
81 94 78 69 69
78 15 55 87 89
19 35 43 37 42
46 98 22 12 99
99 30 90 60 18
44 56 16 94 95
59 57 25 64 74
99 18 85 77 35
38 99 83 58 25
86 52 41 60 63
50 35 60 10 25
18 69 45 14 86
50 12 58 94 10
27 2
39 26
63 17
64 46
75 13
26 25
21 45
15 22
41 41
98 92
27 81
37 65
39 25
53 50
72 55
12 42
66 65
10 96
90 90
93 77
24 70
64 49
87 79
33 99
59 11
49 43
43 31
76 85
27 5
35 20 10 91 64
77 51 94 40 72
81 32 58 39 36
18 95 49 79 77
87 62 61 95 85
48 87 56 64 47
53 98 32 20 24
39 47 95 59 33
40 30 95 90 68
69 81 90 39 95
43 75 56 19 23
27 24 99 86 80
10 20 29 84 57
57 98 98 99 18
48 17 94 66 20
85 34 47 41 20
66 40 15 59 71
83 40 25 40 36
58 88 96 74 98
94 85 65 50 54
93 79 43 62 17
42 82 38 57 76
53 17 73 98 12
40 92 48 86 61
18 21 89 73 39
72 72 39 96 33
31 58 51 90 65
16 1
36
58
18
15
37
70
72
25
88
52
73
39
26
38
56
17
9 9
80 94 76 27 45 67 60 87 46
94 87 22 65 51 72 58 41 68
86 30 13 64 45 41 66 37 63
32 50 94 82 93 80 43 95 32
11 27 16 86 92 39 36 12 17
87 14 10 46 88 79 21 61 51
37 74 41 71 41 96 46 95 81
94 88 28 81 46 49 26 65 45
83 72 37 95 26 84 56 94 35

Correct output:

Code: Select all

6
10 4 19 9 2 5
3
1 2 4
25
2 15 9 8 17 22 4 13 16 19 1 29 26 21 7 6 3 12 24 23 25 14 28 10 20
4
17 14 10 5
3
13 15 8
5
19 4 15 26 16
11
7 5 1 26 25 3 14 27 22 18 9
4
13 25 9 19
16
4 16 3 8 13 1 5 14 12 10 15 2 6 7 11 9
2
6 9

Your output:

Code: Select all

6
3 14 13 9 2 5
3
1 5 4
25
11 15 9 8 17 22 4 13 16 19 18 29 26 21 7 27 3 12 24 23 25 14 28 10 20
4
12 4 26 5
3
5 7 8
5
29 3 22 26 16
11
17 4 20 10 23 3 14 27 19 18 9
4
13 21 14 19
16
4 16 3 8 13 1 5 14 12 10 15 2 6 7 11 9
2
6 2

SyFy · Post by **SyFy** » Sun Jul 01, 2012 6:10 pm

this test helped me:

input:

Code: Select all

2 2
10 15
5 15

output:

Code: Select all

1
1

or

Code: Select all

1
2

mahade hasan · Post by **mahade hasan** » Sun Sep 30, 2012 9:29 pm

stuck at Tle plz help me........

Code: Select all

#include<stdio.h>
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;

int main()
{
   long Box[35][35],I,K,L,M,N,Count,R,C,Start,Arry[35];
   while(scanf("%ld %ld",&R,&C)==2)
   {
      for(I=0;I<R;I++)
      {
         for(K=0;K<C;K++)
         scanf("%ld",&Box[I][K]);
         sort(Box[I],Box[I]+C);
      }
      Count=0;
      stack<int >Stack,TK;
      for(I=0;I<R;I++)
      {
         int Status[35]={0};
         Status[I]=1;
         Stack.push(I);
         while(!Stack.empty())
         {
            N=Stack.top();
            Start=0;
            for(K=0;K<R;K++)
            if(Status[K]==0||Status[K]!=N+1)
            {
               L=0;
               for(M=0;M<C;M++)
               if(Box[N][M]>=Box[K][M]){L=1;break;}
               
               if(L==0){Stack.push(K);Status[K]=N+1;++Start;break;}
            }
            if(Start==0)
            {
               if(TK.size()<Stack.size()) TK=Stack;
               Stack.pop();
            }
         }
      }
      printf("%ld\n",TK.size());
      K=0;
      while(!TK.empty())
      {
         Arry[++K]=TK.top()+1;
         TK.pop();
      }
      for(;K>0;K--)
      printf("%ld ",Arry[K]);
      printf("\n");
   }
   return 0;
}

[/color]

OJ Board

103 - Stacking Boxes

#103 WA

103 - Stacking Boxes

Re: 103 WA

Re: 103 Funny Judge Problem

Re: 103 WA

Re: 103 - Stacking Boxes

Re: 103 - Stacking Boxes

103 - Matching boxes.

Re: 103 - Matching boxes.

Re: 103 problem ...

Re: 103 problem - Stacking Boxes

Re: 103 problem ...

Re: 103 problem ...

Re: 103 problem ...