2588. Симметрия

Фермер Джон обожает симметрию и в данный момент расставляет коров на своём поле, которое имеет вид прямоугольной таблицы размером n × m.

Чтобы сохранить симметрию, фермер Джон действует следующим образом. Сначала он размещает корову в центральной клетке поля. Если такой клетки не существует, он прекращает процесс. Затем он делит поле на четыре равных по размеру прямоугольных участка, разделённых строкой и столбцом, проходящими через центральную клетку с коровой. После этого он независимо повторяет ту же процедуру для каждого из получившихся участков.

Процесс деления продолжается для всё меньших и меньших полей до тех пор, пока у очередного поля существует центральная клетка и его можно разделить указанным способом.

Например, если n = 7 и m = 15, то фермер Джон сначала разместит корову в клетке с координатами (4, 8), после чего разобьёт поле на четыре участка размером 3 × 7. В каждом таком поле он разместит корову в клетке (2, 4) и затем разобьёт каждое из них на четыре участка размером 1 × 3. Данный процесс проиллюстрирован ниже (буквой C обозначены клетки с коровами):

Для такого поля потребуется всего 21 корова.

С другой стороны, если n = m = 5, фермер Джон разместит только одну корову, поскольку получающиеся поля размером 2 × 2 не имеют центральных клеток.

Помогите фермеру Джону определить, сколько всего коров ему потребуется разместить на поле.

Вход. Два целых числа n и m (1 ≤ n ≤ 10⁹, 1 ≤ m ≤ 10⁹).

Выход. Выведите общее количество коров, которые будут размещены на поле.

Пример входа	Пример выхода
7 15	21

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Фермер Джон размещает коров строго по центру каждого поля и рекурсивно повторяет процесс для четырёх равных подполей:

1. Центральная клетка существует тогда и только тогда, когда обе стороны поля нечётные.

2. Если хотя бы одна из сторон чётная, процесс сразу останавливается.

3. Если центральная клетка существует, то:

· в неё ставится ровно одна корова;

· поле делится на 4 одинаковых прямоугольника;

· процесс независимо повторяется в каждом из них.

Пусть f(n, m) – количество коров, размещаемых на поле n × m.

Если хотя бы одно из чисел n или m четное, центральной клетки не существует. Поэтому

f(n, m) = 0

Если оба числа n и m нечетные, то в центре ставим одну корову и далее рекурсивно расставляем коров в четырех полях размером n / 2 × m / 2:

f(n, m) = 1 + 4 * f(n / 2, m / 2)

Пример

Вычислим ответ для заданного теста.

f(7, 15) = 1 + 4 * f(3, 7) = 1 + 4 * 5 = 21

f(3, 7) = 1 + 4 * f(1, 3) = 1 + 4 * 1 = 5

f(1, 3) = 1 + 4 * f(0, 1) = 1 + 4 * 0 = 1

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

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