Programozás‎ > ‎Feladatok‎ > ‎

Üvegválogatás

Egy üzletben válogatás nélkül gyűjtötték össze az üres üvegeket N ládában. Mivel az üvegfajták száma is N, ezért az azonos fajtájú üvegeket egy-egy ládában el lehet tárolni. Ezért szét akarják válogatni az üvegeket, hogy minden ládában csak azonos fajtájú legyen, de úgy, hogy a lehető legkevesebb üveget kelljen átrakni más ládába.
 

Feladat

Készíts programot, amely kiszámítja, hogy legkevesebb hány darab üveget kell másik ládába átrakni, és megadja, hogy ehhez az egyes fajtákat melyik ládába kell gyűjteni!

Bemenet

A valogat.be szöveges állomány első sorában egy egész szám, a ládák N száma (1<=N<=8) van. A következő N sor mindegyike pontosan N nemnegatív egész számot tartalmaz egy-egy szóközzel elválasztva. Az I+1-edik sorban a J-edik szám az I-edik ládában lévő J-fajta üvegek száma. Minden szám értéke legfeljebb 5000. A ládákat és az üvegfajtákat is az 1,…,N számokkal azonosítjuk.

Kimenet

A valogat.ki szöveges állomány első sora egy egész számot tartalmazzon, a kívánt szétválogatáshoz szükséges átrakások minimális számát! A második sor pontosan N egész számot tartalmazzon (egy-egy szóközzel elválasztva): az I-edik szám annak az üvegfajtának a sorszáma legyen, amelyet az I-edik ládába rakunk!

Példa

Bemenet  Kimenet
3
15 30 8
55 80 10
50 60 12
182
3 2 1


Tesztadatok

Címkék

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

megoldás