Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I/S. 7. (March 2016)

I/S. 7. We are given a \(\displaystyle 5\times 5\) grid. Each square either contains one candy or is empty. There are altogether \(\displaystyle 0\le K\le 22\) empty squares with \(\displaystyle K\) even, the rest of the squares contain candies. We know that the top left field \(\displaystyle (1;1)\) and the bottom right field \(\displaystyle (5;5)\) contain candies. Two kids would like to eat candies: one starts from \(\displaystyle (1;1)\) and the other from \(\displaystyle (5;5)\). First they eat the candies at their actual position, then they simultaneously take a step to one of the adjacent squares (``adjacent'' here means ``sharing an edge'') containing a candy. They eat those candies and take another step following the above rule, then repeat the process. Their goal is to collect all candies and meet, but they need to eat the last candy together. They should only meet in the very last step. You should determine the number of ways they can traverse the grid (they cannot visit any square twice since they only step on squares with candies).

Your program should read the value of \(\displaystyle K\) from the first line of the standard input. The following \(\displaystyle K\) lines contain the missing candy positions. The first and only line of the standard output should contain the number of possible grid traversals. If the grid cannot be traversed, a ``0'' should appear. Two traversals are different if there is at least one kid with a different step at some point.

Explanation. There are 4 missing candies in the middle row. The kids should meet in this row in the \(\displaystyle 5^\mathrm{th}\) column. It is easy to see that in this case their path is unique.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file is7.zip.

(10 pont)

Deadline expired on April 11, 2016.


Statistics:

13 students sent a solution.
10 points:Bálint Martin, Gáspár Attila, Gergely Patrik, Hornák Bence, Janzer Orsolya Lili, Kovács 246 Benedek, Nagy Ábel, Németh 123 Balázs, Noszály Áron, Olexó Gergely, Szakály Marcell.
9 points:Nagy Nándor.
3 points:1 student.

Problems in Information Technology of KöMaL, March 2016