Let us consider two disjoint cases:

1. N is a composite number. In this case, we wish to use the factorization of N:
   • If N can be written as a product of two different integers (N = A × B, 1 < A < B < N), it means that both A and B appear in the product 1 × 2 × … × (N-1). Therefore, N divides the product.
   • If N cannot be written as a product of two different integers, it means that N can be written as a product of two identical integers (remember that N is a composite number). Each of the two numbers is equal to sqrt(N).
     Because 1 < sqrt(N) < 2×sqrt(N) < N for any N greater than 4^[1], both square roots will appear somewhere in the product 1 × 2 × … × (N-1). Therefore, sqrt(N) × sqrt(N) = N divides the product.
   
   

   ^[1]: N = 4 is a particular case and should be dealt with independently.
   

2. N is a prime number. In this case, we make use of Lagrange's Theorem, which states that the residue classes (mod N) are a field. This means that every non-zero integer a has a unique multiplicative inverse a^-1.
   • For the most part, a ≠ a^-1. These means that we can match elements in pairs such that each pair has a product congruent to 1 (mod N).
   • However, there might be some elements a for which a ≡ a^-1 (mod N). This is equivalent to a² ≡ 1 (mod N). Because a polynomial of degree 2 has at most 2 roots in any field (again, Lagrange), we can be sure that the only values of a for which the previous equation holds are ±1. This means that ±1 (or 1 and N-1, if you wish) are their own multiplicative inverses. As a consequence, we cannot pair 1 with itself, and we cannot pair N-1 with itself. However, we can pair 1 with N-1, and get a multiplicative residue of N-1.
   Now we have (N-3)/2 pairs with products congruent to 1, and exacty one pair with the product congruent to N-1. The following expression will hold: 1 × 2 × … × (N-1) ≡ N-1 (mod N). Therefore, the answer in this case is N-1.

You can find more info on Wikipedia's article on Wilson's theorem.

The problem is reduced to determining whether or not N is a prime number. This can be solved in O(sqrt(N)) time complexity.

Python solution (Sergiu Puscas)

    1 import math
    2 n = input()
    3 
    4 print 2 if n == 4 else (0 if any(n % x == 0 for x in range(2, int(math.sqrt(n))+1)) else n-1)

Ruby solution (Croitoru Radu Bogdan)

    1 require 'prime'
    2 
    3 n = gets.chomp.to_i
    4 puts n==4? 2:(Prime.prime?(n)? n-1:0)

C++ solution (Gabriel Inelus)

    1 #include <iostream>
    2 int N, p;
    3 int main() {
    4     std::cin >> N;
    5     for(int i = 2; i * i <= N && !p; ++i)
    6         p |= (N % i == 0);
    7 
    8     if(N == 4) std::cout << 2;
    9     else if(p) std::cout << 0;
   10     else std::cout << N - 1;
   11 
   12     return 0;
   13 }

First, let's take a look at the limits: N ≤ 1000. This suggests the complexity O(N^2). The problem can be solved by DP and the solution should be pretty straight forward.

To make a good solution we'll solve a simpler problem at first. Let's assume D means just one step down. This particular problem can be solved by the folowing DP:

dp[dir][i][j] = the largest sum of a sequence that ends in position (i, j), considering that the snake is coming from direction dir (0 for left or 1 for right).

Returning to the initial problem, the DP seems simpler now: dp[dir][des][i][j] = the largest sum of a sequence that ends in position (i, j), considering that the snake is coming from direction dir (0 for left, 1 for right) and is descending or not (des = 0/1).

The following cases must be analyzed:

1. The snake goes down.
2. The snake continues to move to the left or to the right.
3. The snake stops descending and swaps the direction.

Time complexity: O(N^2).

C solution (Marius Gavrilescu)

    1 #include<stdio.h>
    2 #include<stdlib.h>
    3 #include<string.h>
    4 
    5 char s[205], f[3];
    6 unsigned char mem[128];
    7 
    8 int main(void){
    9     fgets(s, sizeof s, stdin);
   10     strtok(s, ",");
   11 
   12     for(int i = 0; s[i] ; i++)
   13         if((*f = s[i]) == '%')
   14             f[1] = s[++i], scanf(f, mem + atoi(strtok(NULL, ",")));
   15         else
   16             f[1] = 0, scanf(f);
   17 
   18     for(int i = 0 ; i < 128 ; i++)
   19         printf("%02X", mem[i]);
   20 }

Official solution (Adrian Soucup)

This problem uses the following idea: Because all polygons are regular, the type of the polygon can be detected using the ratio of the maximum Euclidian distance between the center of mass and the boundary and the minimum Euclidian distance between the center of mass and boundary of each figure.

This ratio is equal to 1/cos(pi/N), where N is the number of sides of the regular polygon. The algorithm is as follows:

• Find connected components;
• Compute the center of mass for each figure as: (x_c, y_c) = 1/tsum of (x_i,y_i), where (x_i,y_i) are all pixels (pixel coordinates) of a connected component;
• Compute the maximum and minimum distance between this point (x_c,y_c) and the boundary of the figure. Then, the ratio can be used to detect the type of the figure. A pixel is on the boundary when it has at least 1 neighbor with value of 0.

In case of lines this ratio will be > 2, for triangles this ratio will be 2, for squares sqrt2 and everything else will be considered a pentagon.

For maximizing precision, the algorithm uses the square of the Euclidian distance and the square of ratio and uses the middle of the interval as decision boundary. If r is the ratio then:

• r² > 15 → line
• r² ∈ (3, 15] → triangle
• r² ∈ (1.76, 3] → square
• r² ≤ 1.76 → pentagon

Complexity: O(W*H) where W is the width and H is the height of the image.

Alternative solution (Gabriel Robert Inelus)

In order to solve this problem, we can use a Convex Hull algorithm which has the capacity of treating colinear points. We use a fill algorithm to get the boundaries of each shape and to insert them into a vector of pairs (x, y) which represents the coordinates of the points. Then we use Andrew's Modification convex hull algorithm which will give us the convex hull of the geometric shape. We have to take care of the precision, because a straight line is not actually straight on its pixelated representation. Thus, we should consider any 3 points which create a triangle with the absolute value of the area less than EPS as 3 colinear points, and elimninate the middle one.

Note that we have to carefully choose EPS in order to correctly eliminate the almost colinear points. EPS ∈ [47,54] can be succesfully used, however I let the proof for this EPS as homework for the curious reader.

The solution can be easily obtained from the (correct) convex hull by counting the number of edges with more than 70 units. Some others edges may apear due to precision errors thus, we have to sort them by size and delete the small ones which are obvious precision errors.

The complexity is O(H*W) due to the fact that there are few boundary points on each shape.