Одинокий король
Одинокий король
Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из n его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) - возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои n ходов.
Входные данные
В первой строке задано общее число ходов короля n (0 ≤ n ≤ 1000). В последующих n строках заданы направления перемещения короля: строка под номером i + 1 задаёт направление перемещения короля на i-ом ходу.
Выходные данные
Выведите единственное число - номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение "Ok" (без кавычек), а во второй - манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами (x1
, y1
) и (x2
, y2
) определяется по формуле: d = |x2
- x1
| + |y2
- y1
|.
5 1 2 4 7 4
4
5 1 2 4 6 4
Ok 2