Rezultati

Up. imeNalogaJezikRezultatČas oddaje
jam-2017 Škatle Java 100/100OK 20. apr '17 @ 19:32

Test Točke Porabljen spomin Porabljen čas Status
#1 6/6 37,277 MiB 0,000 s OK
#2 6/6 40,328 MiB 0,000 s OK
#3 6/6 38,016 MiB 0,000 s OK
#4 6/6 35,332 MiB 0,000 s OK
#5 6/6 34,844 MiB 0,000 s OK
#6 7/7 37,379 MiB 0,000 s OK
#7 7/7 42,168 MiB 0,000 s OK
#8 7/7 37,316 MiB 0,000 s OK
#9 7/7 36,531 MiB 0,000 s OK
#10 7/7 41,148 MiB 0,000 s OK
#11 7/7 40,395 MiB 0,000 s OK
#12 7/7 47,078 MiB 0,087 s OK
#13 7/7 45,383 MiB 0,057 s OK
#14 7/7 48,457 MiB 0,089 s OK
#15 7/7 46,199 MiB 0,091 s OK

Ocenjevani program (Skatle.java):
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Skatle {

    private static int n;
    private static int d;
    private static Skatla[] skatle;
    private static int[] pase;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        d = sc.nextInt();

        skatle = new Skatla[n];
        pase = new int[n];

        for (int i = 0; i < n; i++)
            pase[i] = -1;

        for (int i = 0; i < n; i++) {
            Integer[] dimenzije = new Integer[d];
            for (int j = 0; j < d; j++)
                dimenzije[j] = sc.nextInt();
            Skatla skatla = new Skatla(dimenzije);
            skatle[i] = skatla;
        }

        // sortiranje skatel
        Arrays.sort(skatle, new comparator2());

        int max = 1;
        for (int i = 0; i < n; i++) {
            int temp = rek(i);
            if (temp > max)
                max = temp;
        }

        System.out.println(max);
    }

    private static int rek(int index) {
        if (pase[index] > -1)
            return pase[index];

        Skatla stara = skatle[index];
        int maxGlobina = 0;

        for (int i = index + 1; i < n; i++) {
            Skatla nova = skatle[i];
            if (paseNot(stara, nova)) {
                int globina = rek(i);
                if (globina > maxGlobina)
                    maxGlobina = globina;
            }
        }

        pase[index] = maxGlobina + 1;
        return maxGlobina + 1;
    }

    private static boolean paseNot(Skatla stara, Skatla nova) {
        for (int i = 0; i < d; i++) {
            if (stara.dimenzije[i] <= nova.dimenzije[i])
                return false;
        }
        return true;
    }

    static class Skatla {
        public Integer[] dimenzije;

        public Skatla(Integer[] dimenzije) {
            this.dimenzije = dimenzije;
            Arrays.sort(this.dimenzije, new comparator());
        }

        @Override
        public String toString() {
            return "dimenzije=" + Arrays.toString(dimenzije);
        }
    }

    static class comparator implements Comparator<Integer> {
        @Override
        public int compare(Integer a, Integer b) {
            if (a > b)
                return -1;
            if (a.equals(b))
                return 0;
            return 1;
        }
    }

    static class comparator2 implements Comparator<Skatla> {
        @Override
        public int compare(Skatla a, Skatla b) {
            for(int i = 0; i < d; i++) {
                if(a.dimenzije[i] > b.dimenzije[i])
                    return  -1;
                if(a.dimenzije[i] < b.dimenzije[i])
                    return  1;
            }
            return 0;
        }
    }
}