Задача C. Взвешивание матрёшек ≡

Условие

У Тимофея есть набор матрёшек, пронумерованных последовательными числами от 1 до n. Вес каждой матрёшки равен её номеру и любую матрёшку с номером a можно спрятать в матрёшку с номером b, если a < b.

Сегодня Тимофею удалось разместить все n матрёшек на равноплечных весах, так, что весы находятся в равновесии, а на их чашах видны всего две матрёшки, по одной на каждой чаше. Проверьте, не схитрил ли он.

Формат входных данных

Первая строка входных данных содержит натуральное число n — количество матрёшек у мальчика и одновременно номер матрёшки, стоящей на левой чаше весов. Вторая строка содержит натуральное число m — номер матрёшки, стоящей на правой чаше весов.

Формат выходных данных

Выведите True или False — ответ на вопрос, возможно ли расставить все n матрёшек описанным образом.

Ограничения

1 ≤ m < n ≤ 10⁹

Пояснения к примерам

Смотри рисунок. В первом примере на левой чаше стоит матрёшка с номером 4, на правой — с номером 3.

Если в левую матрёшку спрятать матрёшку с номером 1, а в правую — с номером 2, то все четыре матрёшки окажутся на весах и весы будут находиться в равновесии.

Во втором примере на левой чаше стоит матрёшка с номером 5, на правой — с номером 4.

Из восьми способов расположения остальных матрёшек на двух чашах ни один не даёт требуемого равновесия:

1) 5 + 3 + 2 + 1 ≠ 4

2) 5 + 3 + 2 ≠ 4 + 1

3) 5 + 3 + 1 ≠ 4 + 2

4) 5 + 3 ≠ 4 + 2 + 1

5) 5 + 2 + 1 ≠ 4 + 3

6) 5 + 2 ≠ 4 + 3 + 1

7) 5 + 1 ≠ 4 + 3 + 2

8) 5 ≠ 4 + 3 + 2 + 1

Примеры тестов

4
3

True

5
4

False

Разбор

Проверка условий.

Всего n матрёшек будут весить n * (n + 1) // 2 (по формуле суммы членов арифметической прогрессии). Только если это число чётное, их можно распределить на 2 равные по весу части.

Одна из таких частей должна включать в себя только матрёшки от 1 до m включительно. Максимальный вес такого набора равен m * (m + 1) // 2. Если он больше или равен половины веса n матрёшек, то установить равновесие возможно (например, установив все первые m матрёшек на правую чашу, а остальные — на левую. Потом, пока не достигнуто равновесие, переносить матрёшки на левую чашу (начиная с m - 1) жадным алгоритмом). Данный подход всегда приведёт к нужному результату, поскольку мы сможем набрать любой вес от 1 до m * (m - 1) // 2.

Окончательно получается, что достаточно проверить всего два условия:

1) n * (n + 1) // 2 чётное;

2) Внутрь матрёшки m можно спрятать все матрёшки от 1 до m - 1 и их вес не меньше половины веса остальных матрёшек: 2 * m * (m + 1)  ≥  n * (n + 1)