Энты

@fdgvds · Регистрация: 12.05.2021

Студворк — интернет-сервис помощи студентам

Энты были созданы в Первоначальную эпоху вместе с другими обитателями Средиземья. Эльфийские легенды гласят, что когда Варда зажгла звёзды и пробудились эльфы, вместе с ними пробудились и энты в Великих Лесах Арды.

Когда энты пришли в Арду, они ещё не умели говорить — этому искусству их обучали эльфы, и энтам это ужасно нравилось. Им доставляло удовольствие изучать разные языки, даже щебетание людей.

Эльфы выработали хорошую технику обучения энтов своему языку. Первый энт, которого обучили эльфы, выучил всего два слова — «tancave» (да) и «la» (нет). Обученный энт выбрал одного старого и одного молодого энта, не умеющих говорить, и обучил их всем словам, которые знал сам. Затем обучение этих двух энтов продолжили сами эльфы. Каждый обучившийся у эльфов энт снова выбирал из неговорящих сородичей одного старого и одного молодого, обучал их всем словам, которые знал, передавал эльфам и так далее.

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

Общее число энтов в Средиземье больше, чем вы думаете. Интересно, а сколько из них знают ровно 150 квенийских слов? Похожую задачу вам предстоит решить.

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

Даны натуральные числа K и P (K≤10⁶, 1≤P≤10⁹ ), записанные через пробел.

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

Мы понимаем, что число энтов, знающих в точности K слов, может быть слишком велико, поэтому просим вывести лишь количество энтов, знающих ровно K слов, по модулю P.

@КулХацкеръ · 12.05.2021, 08:10

Python
1
print((lambda k,p:0 if k<2 else (lambda r:__import__('functools').reduce(lambda d,i:d+[(d[i-1]+d[i//2])%p if i%2 else d[i-1]],r,[0,1])[-1])(range(2,k)))(*map(int,input().split())))

@sgedsc · 12.05.2021, 16:41

КулХацкеръ, по времени не проходит

@КулХацкеръ · 12.05.2021, 16:52

Можно ссылку на тестирующую систему?

@grizlik78 · 13.05.2021, 00:47

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_ents_num_modulo_p(k, p):
    if k < 2:
        return 0
    num = (k+1)*[0]
    num[2]=1
    for i in range(2,k):
        num[i+1] = (num[i+1] + num[i]) % p
        if 2*i <= k:
            num[2*i] = num[i]
    return num[k]
 
 
k, p = map(int,input().split())
print(get_ents_num_modulo_p(k, p))

@Антон Ф · 07.06.2021, 14:46

а можно на с++?
Просто такой код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int get_ents_num_modulo_p(int k, int p){
    if (k < 2){
        return 0;
    }
    int num[k+1];
    num[2] = 1;
    for(int i = 2; i < k; i++){
        num[i+1] = (num[i+1] + num[i]) % p;
        if (2*i <= k){
            num[2*i] = num[i];
        }
    }
    return num[k];
}
int main(){
  int k, p;
  cin >> k >> p;
  cout << get_ents_num_modulo_p(k, p);
}

не работает
также ещё так пробовал

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main(){
long long k, p;
cin >> k >> p;
vector <long long> a(1000000);
a[1] = 0; 
a[2] = 1;
for (int i = 3; i <= k; i++){
if (i % 2 == 0){
a[i] = a[i - 1] + a[i / 2];
}else{
a[i] = a[i - 1];
}
}
cout << a[k] % p;
return 0;
}

@grizlik78 · 07.06.2021, 15:28

Скорее всего дело всё-таки в VLA.
У меня с вектором работает.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int get_ents_num_modulo_p(int k, int p){
    if (k < 2){
        return 0;
    }
    std::vector<int> num(k+1);
    num[2] = 1;
    for(int i = 2; i < k; i++){
        num[i+1] = (num[i+1] + num[i]) % p;
        if (2*i <= k){
            num[2*i] = num[i];
        }
    }
    return num[k];
}
int main(){
  int k, p;
  cin >> k >> p;
  cout << get_ents_num_modulo_p(k, p);
}

Добавлено через 16 минут
А, ну да, там же неинициализированные данные, а нужны нули. Вектор обнуляет автоматически.

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@fdgvds 5 / 5 / 0 Регистрация: 12.05.2021 Сообщений: 4

	Энты 12.05.2021, 06:33. Показов 20095. Ответов 6 Метки нет (Все метки) Энты были созданы в Первоначальную эпоху вместе с другими обитателями Средиземья. Эльфийские легенды гласят, что когда Варда зажгла звёзды и пробудились эльфы, вместе с ними пробудились и энты в Великих Лесах Арды. Когда энты пришли в Арду, они ещё не умели говорить — этому искусству их обучали эльфы, и энтам это ужасно нравилось. Им доставляло удовольствие изучать разные языки, даже щебетание людей. Эльфы выработали хорошую технику обучения энтов своему языку. Первый энт, которого обучили эльфы, выучил всего два слова — «tancave» (да) и «la» (нет). Обученный энт выбрал одного старого и одного молодого энта, не умеющих говорить, и обучил их всем словам, которые знал сам. Затем обучение этих двух энтов продолжили сами эльфы. Каждый обучившийся у эльфов энт снова выбирал из неговорящих сородичей одного старого и одного молодого, обучал их всем словам, которые знал, передавал эльфам и так далее. Выяснилось, что более молодые энты выучивали у эльфов ещё ровно столько же слов, сколько они узнали от обучавшего их энта. А вот более старые, уже склонные к одеревенению энты, пополняли свой запас всего лишь одним словом. После обучения у эльфов энты до конца света уже не могли выучить ни одного нового слова. Общее число энтов в Средиземье больше, чем вы думаете. Интересно, а сколько из них знают ровно 150 квенийских слов? Похожую задачу вам предстоит решить. Входные данные Даны натуральные числа K и P (K≤10⁶, 1≤P≤10⁹ ), записанные через пробел. Выходные данные Мы понимаем, что число энтов, знающих в точности K слов, может быть слишком велико, поэтому просим вывести лишь количество энтов, знающих ровно K слов, по модулю P. Миниатюры 0

@sgedsc 0 / 0 / 0 Регистрация: 30.04.2021 Сообщений: 15
	12.05.2021, 16:41
	КулХацкеръ, по времени не проходит 0

@КулХацкеръ 710 / 356 / 104 Регистрация: 09.02.2018 Сообщений: 805
	12.05.2021, 16:52
	Можно ссылку на тестирующую систему? 0

Энты

Решение