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

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

HotLog


 

Энты

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

Задача имеет динамическое решение. Среди тех, кто будет знать ровно i слов будут как молодые, так и старые Энты, каждый из них обучался у какого-то Энта и впоследствии у Эльфов. Старые Энты, знающие ровно i слов, могли обучиться этому только у Энтов, которые знали ровно i-1 слово (еще одно слово они получают от Эльфов). Молодые Энты получат i слов от тех, кто знал ровно i/2 слов (вторую половину они получают от Эльфов). Заметим, что после обучения молодые Энты всегда знают четное количество слов, поэтому их следует учитывать только для четных i. Поэтому если a[i] – количество Энтов, знающих ровно i слов, то a[i]=a[i-1], если i нечетно и a[i]=a[i-1]+a[i/2] иначе. Поскольку первый Энт знал 2 слова, то a[2]=1, логично также, что a[0]=a[1]=0, т.к. обученных Энтов с нулевым или одним словом нет. Увеличивая значение i от 3х до k в результате в a[k] мы получим ответ. Стоит так же заметить, что каждый раз, определяя очередное значение, следует вычислять остаток отделения на p, а не один раз это делать в конце программы. Это позволит избежать переполнение целого типа.


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


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