Question

Даю 70 баллов Задача 4: Путешествие по джунглям Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан. Всего в джунглях есть N лиан, расположенных друг за другом и пронумерованных слева направо целыми числами от 1 до N. Расстояние между соседними лианами составляет D метров. Находясь на i-й лиане, Коко может совершить прыжок с нее не более, чем на ai метров вправо. В процессе прыжка Коко должна зацепиться за какую-то другую лиану, мимо которой будет пролетать. В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо. Помогите Коко и определите максимальный номер лианы, до которой она сможет добраться. Входные данные Первая строка входных данных содержит целое число N (2 ≤ N ≤ 105) — количество лиан. Во второй строке записано целое число D (1 ≤ D ≤ 109) — расстояние между соседними лианами. В каждой из следующих N строк записано целое число ai (1 ≤ ai ≤ 109) — на сколько метров вправо может прыгнуть Коко, находясь на i-й лиане. Выходные данные Выведите единственное целое число — максимальный номер лианы, до которой сможет добраться Коко. Система оценки Решения, работающие при N ≤ 15, будут набирать не менее 16 баллов. Решения, работаюшие при D = 1, будут набирать не менее 12 баллов. Решения, работающие при N ≤ 2000, будут набирать не менее 56 баллов.

Answer 1

Вот на питоне:

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

Эта задача о поиске максимального номера лианы, до которой горилла Коко сможет добраться, используя свои способности к прыжкам с одной лианы на другую. Вот как можно её решить:

Итак, у нас есть N лианы, каждая из которых расположена на определенном расстоянии друг от друга, и Коко может совершить прыжок с каждой лианы на определенное расстояние вправо. Нам нужно найти максимальный номер лианы, до которой горилла сможет добраться.

Один из способов решения этой задачи - использовать жадный алгоритм. Мы начнем с первой лианы и будем двигаться вправо настолько, насколько сможем, используя максимальное расстояние прыжка с каждой лианы. На каждом шаге будем обновлять максимальное расстояние, на которое можем добраться, и соответственно, номер лианы, до которой можем дойти.

Пример кода на Python для решения этой задачи:

# Чтение входных данных
N = int(input())
distances = list(map(int, input().split()))
max_jumps = list(map(int, input().split()))

# Начальные значения
max_distance = max_jumps[0]
max_index = 0

# Проход по лианам
for i in range(1, N):
    # Обновление максимального расстояния, на которое можем дойти
    max_distance = min(max_distance, distances[i - 1])
    max_distance += max_jumps[i]
    
    # Обновление номера лианы, до которой можем дойти
    if max_distance >= distances[max_index]:
        max_index = i

# Вывод результата
print(max_index + 1)  # Добавляем 1, так как нумерация лиан начинается с 1, а не с 0

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

Надеюсь, это поможет разобраться с задачей!