Symmetry (Editorial)

Farmer John places cows strictly in the center of each field and recursively repeats the process for the four equal subfields:

1. A central cell exists if and only if both dimensions of the field are odd.

2. If at least one of the dimensions is even, the process stops immediately.

3. If a central cell exists, then:

   • exactly one cow is placed in it;

   • the field is divided into $4$ identical rectangles;

   • the process is independently repeated for each of them.

Let f(n, m) be the number of cows placed on a field of size n \times m.

If at least one of the numbers $n$ or $m$ is even, a central cell does not exist. Therefore

If both $n$ and $m$ are odd, place one cow in the center and then recursively place cows in the four subfields of size n / 2 \times m / 2:

Example

Compute the answer for the given test case.

Algorithm implementation

The function f returns the number of cows that can be placed on a field of size n \times m.

long long f(int n, int m)
{
  if (n % 2 == 0 || m % 2 == 0) return 0;
  return 1 + 4 * f(n / 2, m / 2);
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);

Compute and print the answer.

res = f(n, m);
printf("%lld\n", res);

Java implementation

import java.util.*;

public class Main
{
  static long f(int n, int m) 
  {
    if (n % 2 == 0 || m % 2 == 0) return 0;
    return 1 + 4 * f(n/2, m/2);
  }
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    long res = f(n, m);
    System.out.println(res);
  }
}

Python implementation

The function f returns the number of cows that can be placed on a field of size n \times m.

def f(n, m):
  if n % 2 == 0 or m % 2 == 0: return 0
  return 1 + 4 * f(n // 2, m // 2)

The main part of the program. Read the input data.

n, m = map(int,input().split())

Compute and print the answer.

res = f(n, m);
print(res)