Разбор задачи «Честный делёж арбуза»

1. Идея

Нужно понять, можно ли представить число w в виде суммы двух положительных чётных чисел.

Самое важное здесь — чётность:

• сумма двух чётных чисел всегда чётная;
• значит, если w нечётное, ответ сразу NO.

Но одной чётности недостаточно. Например, w = 2 — число чётное, но разделить его на две положительные чётные части нельзя: единственный разрез по целым положительным массам — это 1 + 1, а эти числа нечётные.

Значит, арбуз можно разделить тогда и только тогда, когда w чётное и больше 2.

2. Наблюдения

Наблюдение 1

Если обе части должны быть чётными, то их сумма тоже должна быть чётной.

Следовательно:

• если w нечётное, ответ NO.

Наблюдение 2

Нужно, чтобы обе части были положительными.

Минимальные положительные чётные числа — это 2 и 2.

Их сумма равна 4.

Значит:

• если w < 4, подходящего разбиения быть не может.

Наблюдение 3

Если w чётное и w > 2, то разбиение всегда существует.

Например, можно взять:

• первую часть 2,
• вторую часть w - 2.

Тогда:

• 2 — положительное чётное число;
• w - 2 тоже чётное;
• при w > 2 число w - 2 положительно.

Значит, для любого чётного w, большего 2, ответ YES.

3. Алгоритм

1. Считать число w.
2. Проверить условие:
   • если w % 2 == 0 и w > 2, вывести YES;
   • иначе вывести NO.

4. Почему это работает

Докажем в обе стороны.

Если программа выводит YES

Это происходит, когда w чётное и w > 2.

Тогда можно выбрать части 2 и w - 2.

• 2 — положительное чётное число;
• w - 2 — тоже чётное, потому что разность двух чётных чисел чётна;
• w - 2 > 0, так как w > 2.

Значит, арбуз действительно можно разделить правильно.

Если арбуз можно разделить правильно

Пусть он разделён на две положительные чётные части a и b.

Тогда:

• a и b чётные;
• значит, w = a + b — чётное число;
• так как a >= 2 и b >= 2, получаем w >= 4, то есть w > 2.

Следовательно, если корректное разбиение существует, то w обязательно чётное и больше 2.

Итак, условие w % 2 == 0 and w > 2 является и необходимым, и достаточным.

5. Сложность

Алгоритм делает всего несколько простых проверок.

• Время: O(1)
• Память: O(1)

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    int w;
    cin >> w;

    if (w % 2 == 0 && w > 2) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

w = int(input())

if w % 2 == 0 and w > 2:
    print("YES")
else:
    print("NO")