Олимпиадный тренинг

Задача . Разбиения


Задача

Темы:
Найдите количество различных разбиений натурального числа n на натуральные слагаемые таких, что для любых двух различных чисел a ≠ b, входящих в разбиение, верно, что количества чисел a и b в разбиении различны. Разбиения, отличающиеся только порядком слагаемых, различными не считаются.
 
Например, если n = 4, то из пяти возможных разбиений этому условию удовлетворяют все, кроме разбиения на слагаемые 1 и 3: в этом разбиении количество единиц равно количеству троек.
 
4  =  1 + 1 + 1 + 1 (4 единицы )
 
4  =  1 + 1 + 2 (2 единицы, 1 двойка)
 
4  =  1 + 3 (1 единица и 1 тройка!)
 
4  =  2 + 2 (2 двойки)
 
4  =  4 (1 четвёрка)
 
Входные данные
В первой строке входного файла записано натуральное число n (1 ≤ n ≤ 100).
 
Выходные данные
В первой строке выходного файла выведите количество разбиений числа n, удовлетворяющих заданным ограничениям.
 
Ввод Вывод
4 4
6 7

 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя