ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1017. Лестницы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
У маленького мальчика есть набор из N кубиков. Из этих кубиков можно сложить различные лестницы. Лестницы имеют ступени различного размера, следующие в порядке возрастания этого размера (обратите особое внимание на то, что лестница не может иметь две одинаковые ступени). Каждая лестница должна иметь минимум две ступени, и каждая ступень должна состоять минимум из одного кубика. На рисунке приведены примеры лестниц для N=11 и N=5:
Problem illustration
Найдите число Q различных лестниц, которые маленький мальчик может построить ровно из N кубиков.

Исходные данные

Число N (5 ≤ N ≤ 500).

Результат

Число Q

Примеры

исходные данныерезультат
5
2
212
995645335
Источник задачи: Ural State University Internal Contest '99 #2