Хитрий ніндзя

У великому палаці є зал, підлога якого є ґраткою розміром (2n - 1) \times (2n - 1) з квадратів, розташованих у (2n - 1) рядів (пронумерованих від $1$ до 2n - 1) та (2n - 1) стовпців (пронумерованих від $1$ до 2n - 1) — як показано на малюнку нижче для n = 4. Кожен квадрат, який лежить на перетині парного за номером ряду та парного за номером стовпця, зайнятий квадратною дерев'яною опорною колоною. Інші квадрати порожні. Таким чином, між стінами і дерев'яними колонами у залі утворюється $n$ коридорів зліва направо та $n$ коридорів ззаду наперед. На кінцях коридорів (у напрямку ззаду наперед) у стінах розташовані дверні прорізи із завісами. В інших випадках стіни суцільні.

Зал охороняють $k$ охоронців. Кожен охоронець стоїть на перетині коридору, розташованого ззаду наперед, та коридору, розташованого зліва направо. Кожен охоронець дивиться $4$ секунди наліво, $4$ секунди назад, $4$ секунди направо та $4$ секунди наперед, нескінченно повторюючи цей цикл. Напрями погляду охоронців не обов'язково синхронізовані: коли один дивиться наліво, інший може дивитися вперед.

Ніндзя має пройти через зал із передньої стіни до задньої, щоб охоронці його не помітили. Перед тим, як увійти до залу, ніндзя чекає у ряду $0$, тобто за однією із завіс у дверних отворах у передній стіні. Ніндзя може сам вибрати, за якою завісою чекати і скільки перед входом у зал. Вибирати він може й будь-які двері в задній стіні для виходу. Щоб пересунутися між двома сусідніми квадратами, ніндзя витрачає рівно $2$ секунди — під час руху ніндзя може бути помічений будь-яким охоронцем, який у цей момент дивиться у тому напрямку. Чи може ніндзя успішно пройти через зал? Охоронці можуть дивитися крізь інших охоронців, але не можуть дивитися крізь завіси.

На рисунку 1 показано, як ніндзя знаходить шлях для виходу. Спочатку ніндзя чекає. Через $8$ секунд охоронець у ряду $5$, стовпці $1$ повертається наліво, і ніндзя виходить з-за завіси. Через $10$ секунд ніндзя опиняється у ряду $1$, стовпці $1$. Через $12$ секунд ніндзя опиняється у ряду $2$, стовпці $1$. Ніндзя чекає, поки охоронець у ряду $3$, стовпці $5$ повернеться назад; тоді ніндзя починає рух і зникає за завісою у стовпці $3$ якраз перед тим, як охоронець у ряду $1$ повернеться в той напрямок.