Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Игра с графом

(Время: 1 сек. Память: 16 Мб Сложность: 83%)

Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены n кружочков, помеченных числами от 1 до n. Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек b разрешено проводить, если выполнены два условия:

  1. еще нет стрелочки из a в b;
  2. нельзя дойти по стрелочкам из b в a.

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

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

Входные данные

Входной файл INPUT.TXT содержит одно число n (1 ≤ n ≤ 100).

Выходные данные

В выходной файл OUTPUT.TXT выведите число возможных позиций без ведущих нулей.

Пример

INPUT.TXTOUTPUT.TXT
1325

Примечание

Приведем все 25 возможных позиций для примера из условия:


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru