Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2014
Self-Intersecting Path
self.c, self.cpp, Self.java
Karel wants to register his robot Karel for a robot contest. The aim of the contest is to escape
from a maze using a program consisting of N instructions. Each instruction is in the form:
"MOVE ai METERS FORWARD, THEN TURN 90TO THE RIGHT", where ai is a positive
integer. We can simply encode the whole program for the robot as the sequence of integers a1
a2 a3 . . . aN representing the lengths of particular steps.
For example, if the robot starts at coordinates [0, 0] facing north and the encoded program is
1 2 3 4 5, the robot would end up at coordinates [-2, 3] facing east. An important property of
any valid program is that the path the robot takes is not allowed to intersect itself at any point.
This sounds like a nice contest problem, doesn't it? We want to give you an idea what it is like
to organize a programming contest. Therefore, your task is to write a validator for the problem
described above. (You may read more about validators in the validate problem.)
Input Specification
The input contains several test cases. Each test case consists of two lines. The first line contains
a single integer N (1 N 106 ), the number of instructions that form the robot's program.
The second line contains N space-separated integers a1 a2 a3 . . . aN (1 ai 109), an encoded
program for the robot, as described above.
Output Specification
For each test case, print exactly one line. If the given program describes a path that does not
intersect itself, print "OK". Otherwise output a single integer M (0 M < N ), the maximum
number of instructions from the beginning of the program that describe a valid path. That
means the path described by the program consisting of instructions a1 a2 a3 . . . aM does not
intersect itself and M is maximal with this property.
Output for Sample Input
Sample Input
3
7
OK
3113226
5
3
211
6
214443