1. Erste Version: JAVA, [2] + Evgeni Pavlidis


/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.340
* @author ****
*/

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

public class Main {

private static class Box implements Comparable<Box> {
private int dimensions[];
private int index;

public Box(int boxIndex, int boxDimensions[]) {
this.index = boxIndex;
this.dimensions = boxDimensions;
}

public int compareTo(Box otherBox) {
assert this.dimensions.length == otherBox.dimensions.length :
"Compare boxes with the same number of dimensions !";
int rt = 0;
for (int i = 0; i < this.dimensions.length && rt == 0; i++) {
rt = this.dimensions[i] - otherBox.dimensions[i];
}
return rt;
}

public int getIndex() {
return index;
}

public boolean fitIn(Box otherBox) {
assert this.dimensions.length == otherBox.dimensions.length :
"Fit boxes with the same number of dimensions !";
boolean fit = true;
for (int i = 0; fit && i < this.dimensions.length; i++) {
fit = this.dimensions[i] < otherBox.dimensions[i];
}
return fit;
}
}

public static void main(String args[]) {

Scanner scanner = null;
PrintWriter out = null;
try {
scanner = new Scanner(System.in);
out = new PrintWriter(System.out);
while (scanner.hasNextInt()) {
Box boxes[] = new Box[scanner.nextInt()];
int numDimensions = scanner.nextInt();
for (int i = 0; i < boxes.length; i++) {
int boxDimensions[] = new int[numDimensions];
for (int j = 0; j < numDimensions; j++) {
boxDimensions[j] = scanner.nextInt();
}
Arrays.sort(boxDimensions);
boxes[i] = new Box(i, boxDimensions);
}
Arrays.sort(boxes);

int v[] = new int[boxes.length];
Arrays.fill(v, 1);
int vPred[] = new int[boxes.length];
Arrays.fill(vPred, -1);
int indexMax = 0;

for (int i = 1; i < boxes.length; i++) {
Box currBox = boxes[i];
for (int j = 0; j < i; j++) {
if (boxes[j].fitIn(currBox) && v[j] + 1 > v[i]) {
v[i] = v[j] + 1;
vPred[i] = j;
}
}
if (v[i] > v[indexMax]) {
indexMax = i;
}
}

out.println(v[indexMax]);
StringBuilder bf = new StringBuilder();
for (int currIdx = indexMax; currIdx >= 0; currIdx = vPred[currIdx]) {
bf.insert(0, ' ').insert(0, (boxes[currIdx].getIndex() + 1));
}
bf.deleteCharAt(bf.length()-1);
out.println(bf);

}
} catch (Throwable th) {
th.printStackTrace();
} finally {
if (scanner != null) {
scanner.close();
}
if (out != null) {
out.close();
}
}
}
}