Pakolás
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2011 > Második forduló > 11-13. évfolyam
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2011 > Második forduló > 11-13. évfolyam
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.be | pakol.ki |
10 1 2 4 6 7 5 3 2 5 3 |
2 |