rRazmisljao sam malo o ovom zadatku , i nisam smislio nesto lepo..
Pa , eto , da pitam vas da li imate neku lepu ideju..Ja sam imao neke , ali nisu prosle..
http://acm.mipt.ru/judge/problems.pl?problem=035&CGISESSID=f6726ec447ce093b89a69d99f8699c6c
Mislim da slican (ili mozda cak isti) ima na USACOu.
Da ja ne bih previse pametovao, evo texta sa usacoa
This is a modification of the shortest path algorithm. If there was no king, then the shortest path algorithm can determine the distance that each knight must travel to get to each square. Thus, the cost of gathering in a particular square is simply the sum of the distance that each knight must travel, which is fairly simple to calculate.
In order to consider the king, consider a knight which 'picks-up' the king in some square and then travels to the gathering spot. This costs some number of extra moves than just traveling to the gathering spot. In particular, the king must move to the pick-up square, and the knight must travel to this square and then to the final gathering point. Consider the number of extra moves to be the `cost' for that knight to pick-up the king. It is simple to alter the shortest path algorithm to consider picking-up the king by augmenting the state with a boolean flag stating whether the knight has the king or not.
In this case, the cost for gathering at a particular location is the sum of the distance that each knight must travel to get to that square plus the minimum cost for a knight picking up the king on the way.
Thus, for each square, we keep two numbers, the sum of the distance that all the knights that we have seen thus far would have to travel to get to this square and the minimum cost for one of those knights picking up the king on the way (note that one way to 'pick-up' the king is to have the king travel all by itself to the gathering spot). Then, when we get a new knight, we run the shortest path algorithm and add the cost of getting that knight (without picking up the king) to each square to the cost of gathering at that location. Additionally, for each square, we check if the new knight can pick-up the king in fewer moves than any previous knight, and update that value if it can.
After all the knights have been processed, we determine the minimum over all squares of the cost to get to that square plus the additional cost for a knight to pick-up the king on its way to that square.
Nesto mi bas nije jasno. Kada su konji i kralj na istom polju onda ja u jednom potezu pomerim i kralja i konja (i dalje vaze nacini njihovih kretanja). A ako su dva konja i kralj? ili ako su samo k konja?
vazi da ako su kralj i konj na istom polju,
konj moze nositi kralja.
Ako ima vise konja na jednog kralja, samo jedan konj ga moze nositi..Znaci svi idu posebno...
hvala Slobo..To je taj zadatak.
Iskreno, saam se sebi cudim kako ga nisam uradio..
U stvari, imao sam ja ideju koja je veoma slicana, ali sam nesto nepotrebno iskomplikovao..
