Question

Задача 4: Путешествие по джунглям Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан.Всего в джунглях есть Nлиа, расположенных друг за другом и пронумерованных слева направо цельми числами от 1 до N Расстояние между соседнимилианами составляет метров. Находясь на й лиане, Коко может совершить прыжок с нее не более, чем на а, метров вправо. В процессе прыжка Коко должназацепиться за какую то друго лиану, мимо которой будет пролетать.В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо. Помогите Кожо и определите максимальный номер лианы, докоторой она сможет добраться.Входные данныеПервая строка входных данных содержит целое число N (2 N 10°) - количество лиан.Во второй строке записано целое число (1 «D 10°) - расстояние между соседними лианами.В каждой из следующих строк записано целое число а (1 as 10°) - на сколько метров вправо может прыгнуть Кока, находясь на ній лианеВыходные данныеВыведите единственное целое число - максимальный номер лианы, до которой сможет добраться Коно .Система оценкиРешения, работающие при N 15, будут набирать не менее 16 баллов.Решения, работаюшие при D. 1, будут набирать не менее 12 балловРешения, работающие при N 2000, будут набирать не менее 56 баллов.​

Answer 1

на Python:

======================

n = int(input())

d = int(input())

a = []

for _ in range(n):

   a.append(int(input()))

k = a[0] // d + 1

for i in range(1, len(a)):

   if i + 1 <= k:

       t = a[i] // d + i + 1

       if k < t:

           k = t

   else:

       break

if k > len(a):

   k = len(a)

print(k)

=========================

Answer 2

Для решения этой задачи можно использовать динамическое программирование.

Пусть dp[i] - максимальный номер лианы, до которой Коко сможет добраться, находясь на i-й лиане.

Изначально, dp[1] = 1, так как Коко уже находится на первой лиане.

Затем мы можем перейти с текущей лианы i на следующую лиану j, если расстояние между ними не превышает a (предел прыжка Коко). В этом случае dp[j] будет равно максимуму из dp[j] и j.

После обработки всех лиан, максимальный номер лианы, до которой Коко сможет добраться, будет равен максимальному значению в массиве dp.

Приведенный ниже код реализует описанный алгоритм:

pythonCopy code
N = int(input())  # количество лиан
D = int(input())  # расстояние между лианами
a = [0]  # список возможных прыжков

for _ in range(N):
    a.append(int(input()))

dp = [0] * (N + 1)
dp[1] = 1

for i in range(2, N + 1):
    for j in range(1, i):
        if abs(j - i) * D <= a[j]:
            dp[i] = max(dp[i], j)

max_liana = max(dp)
print(max_liana)

Программа считывает количество лиан (N), расстояние между лианами (D) и список возможных прыжков (a). Затем она находит максимальный номер лианы, до которой Коко сможет добраться, и выводит его на экран.