NézetNyomtat

Kamionok
Címkék > Feladat

Kamionok

Egy csomagküldő szolgálat központjában a beérkezés sorrendjében várakoznak a csomagok továbbításra. Minden csomagnak ismert a súlya, ezek a beérkezés sorrendjében: $s_1, \ldots , s_n$. A cégnek két kamionja van, mindegyik azonos K kapacitású, tehát midegyikre legfeljebb annyi csomag pakolható, hogy a csomagok összsúlya nem lehet K-nál nagyobb. Egyik csomag súlya sem nagyobb K-nál. A lehető legtöbb csomagot akarják továbbítani a két kamionnal. Tehát kiszámítandó az a legnagyobb m (1$\le m \le$n), hogy a sorban első m csomag mindegyike felpakolható a két kamion valamelyikére. Az ilyen pakolást nevezzük optimálisnak.

Feladat

Írj programot, amely kiszámít egy optimális pakolást!

Bemenet

A kamion.be szöveges állomány első sora két egész számot tartalmaz (egy szóközzel elválasztva), a kamion K ($1 \le K \le 500$) kapacitását és a csomagok n számát ($1 \le n \le 100$). A második sor pontosan n egész számot tartalmaz (egy-egy szóközzel elválasztva). A sorban i-edik szám az i-edik csomag súlya. Minden s csomagsúlyra teljesül, hogy $1 \le s\le K$.

Kimenet

A kamion.ki szöveges állomány első sora azt a legnagyobb m ($1 \le m \le n$) indexet tartalmazza, amelyre teljesül, hogy az első m csomag felpakolható a két kamionra, betartva a K súlykorlátot! A második és harmadik sor azoknak a csomagoknak a sorszámait tartalmazza, amelyeket az első, illetve a második kamionra pakolnak egy optimális pakolás során.

Példa

KAMION.BEKAMION.KI
100 7 3 12 45 64 56 23 42 4 1 2 3 4

Tesztadatok