Škatle

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 256 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2017

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Prazne škatle zasedejo precej prostora, zato jih je smotrno zlagati eno v drugo. Pri tem je včasih treba katero od škatel tudi nekoliko zavrteti. Iz povsem estetskih razlogov ne želimo nikoli spraviti dveh škatel v tretjo eno poleg druge, ampak morajo biti škatle obvezno gnezdene – npr. prva v drugi in druga v tretji. Največ koliko škatel lahko vgnezdimo na tak način?

Naloga

Problem je še nekoliko težji, ker imamo opravka z D-dimenzionalnimi škatlami. Velikost takšne škatle predstavimo z D-terico števil x = (x_1, x_2, \ldots, x_D). Škatlo x lahko vstavimo v škatlo y, če velja x_i < y_i za vse 1 \leq i \leq D.

Kot rotacijo škatle bomo upoštevali poljubno permutacijo njenih dimenzij. Na primer, z rotacijami 4-dimenzionalne škatle (x_1, x_2, x_3, x_4) lahko dobimo (x_2, x_1, x_4, x_3), (x_1, x_2, x_4, x_3), (x_4, x_2, x_3, x_1) itd.

Napišite program, ki bo izračunal, kakšna je največja globina gnezdenja, ki jo lahko dosežemo z razpoložljivimi škatlami.

Vhodni podatki

V prvi vrstici se nahajata število škatel N in število dimenzij D. Sledi N vrstic, kjer vsaka opisuje eno škatlo. Opis škatle je sestavljen iz D števil, ki predstavljajo dolžine njenih stranic x_i v posameznih dimenzijah.

Omejitve vhodnih podatkov

  • 1 \leq N \leq 100
  • 1 \leq D \leq 10
  • 1 \leq x_i \leq 1000

Izhodni podatki

Izpišite eno samo število – največje število škatel, ki jih lahko vgnezdimo na opisan način.

Primeri

Vhod

5 1
4
3
7
3
2

Izhod

4

Vhod

4 3
7 10 12
9 6 6 
1 2 5
6 9 6

Izhod

3
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task