NézetNyomtat

Robot (Megoldás)
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2008 > Döntő > 11-13. osztály

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)