Robot
Egy gyárban a munkagépek négyzetrácsos elrendezésben vannak. A
futószalagon érkező tárgyakat egy robotnak kell elszállítania a
rendeltetési helyére. A robot a (0,0) mezőről indul, a tárgyakat
érkezési sorrendjükben veheti le a futószalagról és egyszerre
legfeljebb 3 tárgyat szállíthat. Ha több tárgyat szállít, akkor azokat
tetszőleges sorrendben adhatja le a rendeltetési helyre. A robot a
munkagépek felett mozoghat, egy lépésben szomszédos mezőre léphet
egyet: balra, jobbra, felfelé, vagy lefelé. Egy lépése egy időegységet
igényel. Miután leadta az egy menetben szállított tárgyakat, vissza
kell térnie a kiindulási helyére, a (0,0) mezőre.
Feladat
Készíts programot, amely kiszámítja, hogy
legkevesebb mennyi idő alatt tudja a robot elszállítani az összes
tárgyat, és meg is ad egy szállítási ütemezést!
Bemenet
A ROBOT.BE szöveges állomány első sorában a tárgyak N (1≤N≤10000) száma
van. A következő N sor mindegyikében két pozitív egész szám van; X és
Y (1≤X, Y≤1000) egy szóközzel elválasztva, egy tárgy rendeltetési
helyének koordinátái. Ugyanarra a helyre több tárgy is érkezhet.
Kimenet
A ROBOT.KI szöveges állomány első sorába azt a legkisebb M számot kell írni, amely alatt a robot az összes tárgyat el tudja szállítani a rendeltetési helyére. A második sorba egy számsorozatot kell írni (egy-egy szóközzel elválasztva), amely megadja, hogy a robot egy-egy menetben hány tárgyat szállít. Tehát a számsorozat minden eleme 1,2, vagy 3 lehet.
Példa
ROBOT.BE ROBOT.KI 6 54 1 2 3 3 3 2 4 7 8 3 5 7 9 2 |
|
Tesztadatok
robot.zip (készítette Fehér Gábor)