NézetNyomtat

Konténer (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Mohó

Konténer

Egy raktárban egyetlen sorban egymás mellett van $N$ darab kocka alakú konténer. Minde­gyik konténer egy konténerhelyet foglal el a méretétől függetlenül. A raktár teljesen tele van és a raktárosnak helyet kell biztosítani újonnan érkező konténerek számára. Helyet csak úgy tud biztosítani, ha konténereket egymásra rak. A raktár biztonsági előírása szerint konténer csak nálánál nagyobb méretű konténerre rakható rá, de ennek betartásával akárhány konténer rakható egymásra. A raktáros dolgát nehezíti, hogy az átpakolást olyan robottal végezheti, amely bármely konténert fel tud venni, de csak balról jobbra haladva tud szállítani.

Feladat

Készíts programot (KONTENER.PAS, ...), amely kiszámítja, hogy legjobb esetben hány konténerhely szabadítható fel konténerek egymásra rakásával!

Bemenet

A KONTENER.BE szöveges állomány első sorában két egész szám van, a konténerek $N$ száma $(1\leq N\leq 10000)$ és a legnagyobb $K$ konténer méret $(1\leq K\leq 1000)$. A második sor pontosan $N$ egész számot tartalmaz egy-egy szóközzel elválasztva, a konténerek méretét balról jobbra haladó sorrendben.

Kimenet

A KONTENER.KI szöveges állomány első és egyetlen sorába a felszabadítható konténer­helyek maximálás számát kell írni!

Példa

KONTENER.BEKONTENER.KI
10 20
12 2 13 12 20 6 10 4 5 2
5

Tesztadatok