J. Мы делили апельсин

Аня, Боря и Вова решили съесть апельсин.
Подскажите ребятам, как им его разделить. Напишите программу, которая выводит все возможные способы разделки апельсина.

Формат ввода

В единственной строке записано количество долек апельсина.

Формат вывода:

Таблица вариантов разделения апельсина.

Пример

Ввод

3

Вывод

А Б В
1 1 1

Ввод

5

Вывод

А Б В
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1

Решение

Задача знакомит нас с подходом к решению с помощью перебора. В программировании этот метод называется методом грубой силы (brute force).

Суть метода состоит в том, чтобы перебрать все возможные комбинации и в каждом случае проверять выполнилось ли условие. Если условие выполнилось, то сделать то или иное действие.

В нашем случае мы сначала построим самое примитивное решение, а потом постепенно его улучшим.

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

Этот алгоритм можно немного улучшить.
Мы знаем, что каждому ребенку (a, b, c) должна достаться как минимум одна долька. это означает что первому ребенку не может достаться долек больше чем общее количество за минусом двух долек, которые достанутся двум остальным детям.
Соответственно в первом цикле мы можем искать не в диапазоне от 1 до slices + 1, а в диапазоне от 1 до slices – 1
Далее легко заметить, что дольки которые достались первому ребенку не могут быть распределены между вторым и третьим, а значит их можно смело исключить из второго цикла. таким образом диапазон проверок второго ребенка сужается с диапазон от 1 до slices + 1, до диапазона от 1 до slices – a.
По аналогии можно понять, что третьему ребенку не может достаться долек больше, чем разница между максимумом и теми дольками, что уже на руках у первых двух детей. И значит, что диапазон сужается с от 1 до slices + 1 до от 1 до slices + 1 – a – b.
Результат показан в решении номер два.

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

# Решение наивное, для демонстрации сути метода

slices = int(input())

print('А Б В')
for a in range(1, slices + 1):
    for b in range(1, slices + 1):
        for c in range(1, slices + 1):
            if a + b + c == slices:
                print(a, b, c)

# Чуть улучшеное решение. Сильно сокращено количество циклов

slices = int(input())

print('А Б В')
for a in range(1, slices - 1):
    for b in range(1, slices - a):
        for c in range(1, slices - a - b + 1):
            if a + b + c == slices:
                print(a, b, c)

# Улучшеное решение. Избавились от лишнего цикла

slices = int(input())

print('А Б В')
for a in range(1, slices - 1):
    for b in range(1, slices - a):
        c = slices - a - b
        print(a, b, c)