KTH Challenge 2015 Warm-up


2015-04-21 23:00 CEST

KTH Challenge 2015 Warm-up


2015-04-26 11:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -882 days 14:04:38

Time elapsed


Time remaining


Problem I
Count von Walken's Fence

Photo by Lascher

The old Count von Walken ponders along the fence of his backyard. The fence has a repeating pattern with poles in the ground at equal distances. Since von Walken has nothing better to do, he counts the number of steps he takes between each pole.

The distance between two consecutive poles turns out not to be an integer multiple of the length of his steps because sometimes he takes two steps between the poles, and sometimes he takes three steps.

\includegraphics[width=1\textwidth ]{figure}
Figure 1: A picture of sample case 2

Von Walken knows that his steps are always 1 meter long, so he starts thinking of what the distance between the poles may be. “It must be more than 2 meters, since I occasionally can fit 3 steps between the poles, but it must be less than 3 meters, since I sometimes only fit 2 steps in between.”


Given a list of step counts and a distance $D$, determine whether it is possible that the distance between two poles is $D$ meters. The poles can be considered to have width $0$, and each step is strictly between two poles.

To avoid problems with floating point numbers, the result is guaranteed to be the same even if any pole is moved up to $10^{-7}$ meters.


The input consists of a line containing the real number $D$ and an integer $N$, followed by a line with the space-separated list of integer step counts, $c_1, c_2, \ldots , c_ N$. It holds that $2 \leq c_ i, D \leq 3$ and that $0 \leq N \leq 10\, 000$.


The program should print “possible” if $D$ meters is a possible distance between the poles, and “impossible” otherwise.

Sample Input 1 Sample Output 1
2.505 4
2 2 3 2
Sample Input 2 Sample Output 2
2.1 4
2 2 3 2