Programozás‎ > ‎Feladatok‎ > ‎

Pakolás (OKTV)

Egy raktárban egyetlen hosszú sorban ládák vannak. Minden láda kocka alakú, de méretük különböző lehet. A ládák egymásra rakásával akarnak helyet felszabadítani. A biztonsági előírás szerint több ládát is lehet egymásra rakni, de minden ládát csak nálánál nagyobbra lehet helyezni. Továbbá, az i-edik helyen levő ládát csak akkor lehet rárakni a j-edik helyen levő torony tetejére, ha az i-edik, és j-edik helyek között már nincs láda (j lehet akár kisebb, akár nagyobb, mint i). Minden ládát legfeljebb egyszer lehet mozgatni! 

Feladat

Készíts programot, amely kiszámítja, hogy legkevesebb hány toronyba lehet a ládákat összepakolni!

Bemenet

A pakol.be szöveges állomány első sorában a ládák N (2 <= N <= 30000) száma van. A második sor pontosan N pozitív egész számot tartalmaz egy-egy szóközzel elválasztva, a ládák méreteit. A második sorban lévő számok mindegyike 1 és 30000 közötti érték.

Kimenet

A pakol.ki szöveges állomány első és egyetlen sora egy egész számot tartalmazzon, azt a legkisebb M számot, hogy a bemenetben megadott ládasor összepakolható M számú toronyba!

Példa

Bemenet  Kimenet
10
1 2 4 6 7 5 3 2 5 3
2


Tesztadatok

Címkék

A feladat forrása: NTOITV 2011. 2. forduló, 11-13. évfolyam
Algoritmusok: 

megoldás