Энты

Задача имеет динамическое решение. Среди тех, кто будет знать ровно 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, а не один раз это делать в конце программы. Это позволит избежать переполнение целого типа.

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