Code: Select all
MEANING OF SAMPLE OUTPUT #1
5 (5 BOXES)
3 (BOX#3 DIMENSION1=2 DIMENSION2=5 )
1 (BOX#1 DIMENSION1=3 DIMENSION2=7 )
2 (BOX#2 DIMENSION1=8 DIMENSION2=10 )
4 (BOX#4 DIMENSION1=9 DIMENSION2=11 )
5 (BOX#5 DIMENSION1=18 DIMENSION2=21 )
Code: Select all
# Program that solves the Stacking Boxes problem
# http://acm.uva.es/p/v1/103.html
boxes = [] # list of boxes
nBox = 0 # number of boxes
dim = 0 # dimensions of boxes
# sort boxes by their measurements using bubble sort
def sort_boxes():
for i in range(nBox-1):
for j in range(nBox-i-1):
for k in range(dim):
if boxes[j][k] < boxes[j+1][k]:
break
elif boxes[j][k] > boxes[j+1][k]:
boxes[j], boxes[j+1] = boxes[j+1], boxes[j]
break
file = open('input.txt')
while file:
line = file.readline() # read line from file
if line == "": # exit if end of file
break
vars = line.strip().split(' ') # get input data from file
nBox, dim = int(vars[0]), int(vars[1])
boxes = [] # list of boxes
for i in range(nBox):
vars = file.readline().strip().split(' ') # get input data from file
mes = [] # measurements of a box
for var in vars:
mes.append(int(var))
boxes.append(mes) # add box to boxes
for box in boxes: # sort boxes' measurements
box.sort()
oldBoxes = [] # save previous arrangement of boxes
for box in boxes:
oldBoxes.append(box)
sort_boxes() # sort boxes by their measurements
# Find the longest sring of boxes:
maxBoxes = [] # list that holds the longest nesting string
maxBoxes.append(boxes[0]) # make it the first box by default
for i in range(nBox-1): # find the longest string of boxes, try start with box[i]
tempBoxes = [] # temporary boxes that make a string
i1, i2 = i, i+1 # indices of boxes that will be compared
while (i2 < nBox):
nests = True
for j in range(dim): # check if box[i1] nests in box[i2]
if boxes[i1][j] > boxes[i2][j]:
nests = False
break
if nests: # if yes - modify tempBoxes and check if it longer then maxBoxes
if tempBoxes == []:
tempBoxes.append(boxes[i1])
tempBoxes.append(boxes[i2])
if len(tempBoxes)>len(maxBoxes):
maxBoxes = tempBoxes
i1, i2 = i2, i2+1 # modify indices accordingly
else: # if not - try next box
i2 += 1
print len(maxBoxes) # print output
for box in maxBoxes:
print oldBoxes.index(box)+1,
print
file.close()[
Code: Select all
# Program that solves the Stacking Boxes problem
# http://acm.uva.es/p/v1/103.html
boxes = []
nBox = 0
dim = 0
# sort boxes by their measurements using bubble sort
def sort_boxes():
for i in range(nBox-1):
for j in range(nBox-i-1):
for k in range(dim):
if boxes[j][k] < boxes[j+1][k]:
break
elif boxes[j][k] > boxes[j+1][k]:
boxes[j], boxes[j+1] = boxes[j+1], boxes[j]
break
file = open('input.txt')
while file:
line = file.readline()
if line == "":
break
vars = line.strip().split(' ')
nBox, dim = int(vars[0]), int(vars[1])
boxes = []
for i in range(nBox):
vars = file.readline().strip().split(' ')
mes = []
for var in vars:
mes.append(int(var))
boxes.append(mes)
for box in boxes:
box.sort()
oldBoxes = []
for box in boxes:
oldBoxes.append(box)
sort_boxes()
# Find the longest sring of boxes:
maxBoxes = []
maxBoxes.append(boxes[0])
for i in range(nBox-1):
tempBoxes = []
i1, i2 = i, i+1
while (i2 < nBox):
nests = True
for j in range(dim):
if boxes[i1][j] > boxes[i2][j]:
nests = False
break
if nests:
if tempBoxes == []:
tempBoxes.append(boxes[i1])
tempBoxes.append(boxes[i2])
if len(tempBoxes)>len(maxBoxes):
maxBoxes = tempBoxes
i1, i2 = i2, i2+1
else:
i2 += 1
print len(maxBoxes)
for box in maxBoxes:
print oldBoxes.index(box)+1,
print
file.close()
Code: Select all
# Find the longest sring of boxes:
maxBoxes = []
maxBoxes.append(boxes[0])
for i in range(nBox-1):
tempBoxes = []
posStack = []
i1, i2 = i, i+1
while (i2 < nBox ):
nests = True
for j in range(dim):
if boxes[i1][j] > boxes[i2][j]:
nests = False
break
if nests:
if tempBoxes == []:
tempBoxes.append(boxes[i1])
posStack.append(i1)
tempBoxes.append(boxes[i2])
posStack.append(i2)
if len(tempBoxes)>len(maxBoxes):
maxBoxes = tempBoxes
i1, i2 = i2, i2+1
else:
if i2 < nBox:
i2 += 1
if not (i2 < nBox):
if len(posStack) < 2:
continue
i2 = posStack.pop() + 1
tempBoxes.pop()
i1 = posStack[len(posStack)-1]
Code: Select all
#include<stdio.h>
struct X{
int arry[12];
};
int indx[33], b[33], n, d, length[33];
struct X a[33];
int comp(struct X s1, struct X s2)
{
int i;
for(i=0; i<d; i++)
if(s1.arry[i]>s2.arry[i])
return 1;
else if(s1.arry[i]<s2.arry[i])
return 0;
return 0;
}
int isin(struct X s1, struct X s2)
{
int i;
for(i=0; i<d; i++)
if(s1.arry[i]>=s2.arry[i])
return 0;
return 1;
}
void main()
{
freopen("in.txt", "r", stdin);
int i, k, j, l, bb, res, x, c;
struct X temp;
while(scanf("%d %d", &n, &d)==2)
{
for(i=0; i<n; i++)
{
indx[i]=i;
for(j=0; j<d; j++)
scanf("%d", &a[i].arry[j]);
for(k=0; k<d-1; k++)
for(l=k+1; l<d; l++)
if(a[i].arry[k]>a[i].arry[l])
a[i].arry[k]^=a[i].arry[l]^=a[i].arry[k]^=a[i].arry[l];
}
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(comp(a[i], a[j]))
{
indx[i]^=indx[j]^=indx[i]^=indx[j];
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
for(i=0; i<n; i++)
length[i]=1;
res=1;
x=0;
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(isin(a[i], a[j]))
if(length[i]+1>length[j])
{
length[j]=length[i]+1;
if(res<=length[j])
{
res=length[j];
x=j;
}
}
c=res;
bb=1;
b[0]=indx[x];
for(i=x-1; i>=0; i--)
if(length[i]==c-1)
{
b[bb++]=indx[i];
c--;
}
printf("%d\n", res);
for(i=bb-1; i>=0; i--)
printf("%d ", b[i]+1);
puts("");
}
}
This thread started with the same complaint by another. I had it too.Code: Select all
13
28 7 8 9 10 26 15 11 16 17 19 18 20
I cannot find any bag