Fermer John inəkləri hər sahənin tam ortasına yerləşdirir və prosesi dörd bərabər alt sahə üçün rekursiv olaraq təkrar edir:

1. Mərkəzi hüceyrə yalnız sahənin hər iki tərəfi tək olan zaman mövcuddur.

2. Əgər ən azı bir tərəf cüt olsa, proses dərhal dayanır.

3. Əgər mərkəzi hüceyrə mövcuddursa, o zaman:

   • yalnız bir inək yerləşdirilir;

   • sahə $4$ eyni düzbucaqlıya bölünür;

   • proses hər birində müstəqil şəkildə təkrar edilir.

Qoy f(n, m) — n \times m sahədə yerləşdirilən inəklərin sayı olsun.

Əgər $n$ və ya $m$ ədədlərindən ən azı biri cüt ədəddirsə, mərkəzi hüceyrə mövcud deyildir. Buna görə

Əgər həm $n$, həm də $m$ tək ədəddirsə, mərkəzə bir inək qoyuruq və daha sonra rekursiv olaraq , n / 2 \times m / 2 ölçüsündə dörd sahədə inəkləri yerləşdiririk:

Nümunə

Verilmiş testi hesablayın.

Alqoritmin icrası

f funksiyası n \times m ölçüsündə sahəyə yerləşdirilə bilən inəklərin sayını qaytarır.

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

Programın əsas hissəsi. Daxil olan məlumatları oxuyun.

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

Hesablama aparır və cavabı çıxışa yazır.

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

Java icrası

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 icrası

f funksiyası n \times m ölçüsündə sahəyə yerləşdirilə bilən inəklərin sayını qaytarır.

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

Programın əsas hissəsi. Daxil olan məlumatları oxuyun.

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

Hesablama aparır və cavabı çıxışa yazır.

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