Informatika gyűjtemény

Egy szinttel feljebb Pakolás

2004050607080910

NézetNyomtat

Pakolás

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 legfeljsebb 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\le N\le 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

pakol.bepakol.ki
10
1 2 4 6 7 5 3 2 5 3
2

Tesztadatok