ALG-koně
ALG-šachovnice je neobyčejná šachovnice. Na rozdíl od běžné šachovnice má N×N polí, kde N může být libovolné celé číslo větší než 1. Po ALG-šachovnici se pohybují ALG-koně. Pravidla pro pohyb ALG-koně jsou obdobná jako na běžné šachovnici, s malou změnou: S každým ALG-koněm K je spojena dvojice celých čísel K(1) a K(2) a jeden skok ALG-koně proběhne takto: Nejprve si vybere některý ze čtyř směrů rovnoběžných s okrajem šachovnice a přesune se o K(1) polí tímto směrem. Pak na místě změní směr o 90° nebo −90° a dále se posune o K(2) polí v novém směru. Nesmí ovšem opustit ALG-šachovnici. Například pro K(1)=1 a K(2)=2 by se ALG-kůň pohyboval stejně jako běžný šachový kůň (správnou šachovou terminologií jezdec). Stejně jako v šachové hře není podstatné, jestli na některých polích mezi počátečním a koncovým polem skoku stojí nějaká další figura. Abychom naši úlohu zjednodušili, budeme předpokládat, že pro ALG-koně nezáleží ani tom, zda na počátečním nebo koncovém poli skoku stojí další figura nebo figury. Na každém poli ALG-šachovnice tak může stát současně neomezený počet ALG-figur.Na začátku úlohy stojí v každém rohu ALG-šachovnice jeden ALG-kůň. Chtějí se setkat na jednom cílovém poli, aby na něm stáli všichni čtyři, a nezáleží jim na tom, které pole to bude. Záleží jim ale na tom, aby to bylo co nejdříve. Skákat začnou ve stejný okamžik a každou vteřinu může udělat každý ALG-kůň jeden skok. Jakmile některý ALG-kůň dorazí na cílové pole, přestane skákat. Je-li to výhodné, nemusí začít skákat vůbec. Jaký je nejmenší možný počet vteřin, který uplyne, než se všichni ALG-koně setkají na vhodném cílovém poli?
Vstup
Na vstupu je jeden řádek s devíti celými čísly. První z nich je číslo N a udává rozměr šachovnice, dále následují čtyři dvojice čísel. Každá dvojice představuje čísla K(1), K(2) jednoho ALG-koně. Pořadí ALG-koní na ALG-šachovnici je podstatné jen pro vstup dat a je následující podle rohů ALG-šachovnice, v nichž na začátku stojí: levý dolní roh, pravý dolní roh, pravý horní roh a levý horní roh. Číslo N je v rozmezí 2 až 700, čísla K(1) a K(2) každého ALG-koně jsou v rozmezí 1 až N. Čísla jsou na řádku oddělena jednou nebo více mezerami.Výstup
Na výstupu je jediný řádek s dvěma čísly. První udává minimální počet vteřin, který uplyne, než se všichni ALG-koně setkají na jediném poli. Druhé číslo udává počet různých polí na ALG-šachovnici, na nichž se mohou ALG-koně setkat po počtu vteřin udaných prvním číslem. Pokud na ALG-šachovnici neexistuje žádné pole, na němž se mohou všichni ALG-koně setkat, vystoupí pouze řádek s číslem −1.(Poznámka: Minimální počet vteřin zároveň udává počet skoků, které provede ALG-kůň, jenž na cílové pole dorazí jako poslední).
Příklad 1
Vstup:5 1 2 2 3 1 3 1 4Výstup:
4 3Jako ilustraci uvádíme pro každého ALG-koně a každé pole ALG-šachovnice minimální počet skoků, které tento ALG-kůň potřebuje, aby daného pole dosáhl při zadaných parametrech. Pole, která jsou pro ALG-koně nepřístupná, jsou vyznačena tečkou.
2 3 2 3 4 3 2 3 2 3 2 1 4 3 2 3 4 1 2 3 0 3 2 3 2 ----------------- 4 . . . 2 . . 1 . . . 1 . 3 . . . 3 . . 2 . . . 0 ----------------- 4 . 2 . 0 . 1 . 3 . 2 . . . 2 . 3 . 1 . 2 . 2 . 4 ------------------ 0 5 2 7 4 5 . . . 1 2 . . . 6 7 . . . 3 4 1 6 3 8
Příklad 2
Vstup:6 2 5 1 1 2 3 1 4Výstup:
5 2Jako ilustraci uvádíme pro každého ALG-koně a každé pole ALG-šachovnice minimální počet skoků, které tento ALG-kůň potřebuje, aby daného pole dosáhl při zadaných parametrech. Pole, která jsou pro ALG-koně nepřístupná, jsou vyznačena tečkou.
. . 1 . . . 2 . . . . . . . . . . . . . . . . 1 . . . . . . 0 . . . 2 . -------------------- 5 . 5 . 5 . . 4 . 4 . 4 5 . 3 . 3 . . 4 . 2 . 2 5 . 3 . 1 . . 4 . 2 . 0 -------------------- 9 2 5 4 7 0 2 7 6 3 4 7 5 6 1 8 3 4 4 3 8 1 6 5 7 4 3 6 7 2 2 7 4 5 2 9 -------------------- 0 5 2 7 4 9 5 8 3 6 1 4 2 3 . . 6 7 7 6 . . 3 2 4 1 6 3 8 5 9 4 7 2 5 2
Příklad 3
Vstup:6 1 2 1 4 1 3 1 5Výstup:
-1Jako ilustraci uvádíme pro každého ALG-koně a každé pole ALG-šachovnice minimální počet skoků, které tento ALG-kůň potřebuje, aby daného pole dosáhl při zadaných parametrech. Pole, která jsou pro ALG-koně nepřístupná, jsou vyznačena tečkou.
3 4 3 4 3 4 2 3 2 3 4 3 3 2 3 2 3 4 2 1 4 3 2 3 3 4 1 2 3 4 0 3 2 3 2 3 -------------------- 2 5 2 7 4 9 5 8 3 6 1 4 2 3 . . 6 7 7 6 . . 3 2 4 1 6 3 8 5 9 4 7 2 5 0 -------------------- . 4 . 2 . 0 3 . 1 . 3 . . 2 . 4 . 2 3 . 3 . 1 . . 2 . 2 . 4 3 . 3 . 3 . -------------------- 0 . 2 . 4 . . . . . . 1 2 . . . . . . . . . . 3 4 . . . . . . 1 . 3 . 5
Veřejná data
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.