610A. Pasha and Stick

CombinatorialsMathematics

Pasha has a wooden stick of some positive integer length $n$. He wants to perform exactly three cuts to get four parts of the stick. Each part must have some positive integer length and the sum of these lengths will obviously be $n$.

Pasha likes rectangles but hates squares, so he wonders, how many ways are there to split a stick into four parts so that it’s possible to form a rectangle using these parts, but is impossible to form a square.

Your task is to help Pasha and count the number of such ways. Two ways to cut the stick are considered distinct if there exists some integer x, such that the number of parts of length $x$ in the first way differ from the number of parts of length $x$ in the second way.

Read the question with I/O specifications at codeforces.com.

Hints

Hint 1

$n$ is equal to the perimeter of the rectangle.

Solution

The goal is to obtain a rectangular frame by joining four pieces of wood, obtained by cutting a wood of length $n$ three times. Hence, the question is to find the different lengths possible in constructing a rectangle of perimeter $n$.

Therefore, n must be an even number.

Since distinct rectangles are defined as cases when there is a difference in length and breadth irrespective of order, both (1, 1, 2, 2) and (2, 2, 1, 1) configurations are the same.

$l_{1}$ and $l_{2}$ can take values from $1$ to $n/2 - 1$ to satisfy the earlier equation. Since they are not distinct, there are floor((n/2)/2) ways of choosing (l_{1}, l_{2}). As the question states squares must not be considered, we need to remove the case where $l_{1} = l_{2}$, which happens when $n/2$ is divisible by 2 i.e. $n/2$ is even.

Hence, we can consider generalise the count of cases to $(n/2 - 1)/2$, with answer 0 if n is odd. This solution runs in constant time.

Code

#include<iostream>
using namespace std;

int main(void) {
  long long int n;
  cin >> n;
  if (n%2) cout << 0;
  else cout << (n/2 -1)/2;
  return 0;
}

Written by Nandakishore