Internet Problem Solving Contest

IPSC 2000

Solution to Problem A – K-In-A-Row

This task was probably the most simple. The easy data set could be easily solved just by viewing the input file and processing it manually. For the hard data set it wasn't so easy anymore, so the best idea was to write a program.

The idea of the sample algorithm is really simple - we will pass through all horizontal, vertical and diagonal lines one after the other. For each line, we remember, how many signs and of which type were on the previous squares. Now, if we encounter a sign of the same type, we increment the counter, if we encounter a sign of the opposite type, we set the counter to 1 and now check for this type of signs and if we encounter an empty square, we set the counter to 0.

If at any moment the counter reaches K, it means, that there are K same signs in a row ending at the current position and thus the player, whose sign it is, has won this game. If this doesn't happen, it means that nobody has won.

The sample solution is written in Pascal and it is a bit optimized to use only 64 kb memory (it rotates the input to fit into a 300x200 array), so it can be compiled also in Borland Pascal.