Симетрія (Розбір)

Фермер Джон розміщує корів строго по центру кожного поля і рекурсивно повторює процес для чотирьох рівних підполів:

1. Центральна клітинка існує тоді і тільки тоді, коли обидві сторони поля непарні.

2. Якщо хоча б одна із сторін парна, процес відразу зупиняється.

3. Якщо центральна клітинка існує, то:

   • в неї ставиться рівно одна корова;

   • поле ділиться на $4$ однакових прямокутника;

   • процес незалежно повторюється в кожному з них.

Нехай f(n, m) — кількість корів, розміщених на полі n \times m.

Якщо хоча б одне з чисел $n$ або $m$ парне, центральна клітинка не існує. Тому

Якщо обидва числа $n$ і $m$ непарні, тоді в центр ставимо одну корову і далі рекурсивно розставляємо корів у чотирьох полях розміром n / 2 \times m / 2:

Приклад

Обчислимо відповідь для заданого тесту.

Реалізація алгоритму

Функція f повертає кількість корів, які можна розмістити на полі розміром 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);
}

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо відповідь.

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

Java реалізація

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 реалізація

Функція f повертає кількість корів, які можна розмістити на полі розміром 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)

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо відповідь.

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