Zabavno dejstvo iz sveta matematike
1/998001 nam da urejeno zaporedje od 000 do 999. 1/998001 = 0.000001002003004...

Zabavno dejstvo iz sveta računalništva
Leta 1936 so Rusi naredili računalnik na vodo. (Vir: http://gizmodo.com/5879106/the-russian-computer-that-ran-on-water)

Škatle

Moderatorji: hinkopihpih, Matic Conradi

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Škatle

OdgovorNapisal/-a lukazlatecan » Ne Jul 02, 2017 10:15 pm

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 [math]. Škatlo x lahko vstavimo v škatlo y, če velja [math] za vse 1≤i≤D.

Kot rotacijo škatle bomo upoštevali poljubno permutacijo njenih dimenzij. Na primer, z rotacijami 4-dimenzionalne škatle (x1,x2,x3,x4) lahko dobimo [math], [math], [math] 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 [math] v posameznih dimenzijah.

Omejitve vhodnih podatkov
  • 1≤N≤100
  • 1≤D≤10
  • 1≤[math]≤1000

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

Primeri
Vhod

Koda: Izberi vse

5 1
4
3
7
3
2

Izhod

Koda: Izberi vse

4

Vhod

Koda: Izberi vse

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

Izhod

Koda: Izberi vse

3
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler

Vrni se na “1. Kolo”

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 3 gosti