Покупка билетов

@Tamara09 · Регистрация: 29.06.2024

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

Добрый день. Помогите, пожалуйста, найти ошибку в решении. Задача звучит так:
Покупка билетов
За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.

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

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трёх билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).

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

На вход программы поступает сначала число N — количество покупателей в очереди (1≤N≤5000). Далее идут N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.

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

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def f (N):
    if dp[N]!= -1:
        return dp[N]
    v1 = f(N-1)+p[N][0]
    v2 = f(N-2)+p[N-1][1]
    v3 = f(N-3)+p[N-2][2]
    dp[N] = min(v1, v2, v3)
    return dp[N]
N = int(input())
p = [[0, 0, 0]] +[list(map(int,input().split())) for i in range (N)]
dp = [-1] * (N+1)
dp[1] = p[1][0]
if N == 1:
    print(dp[1])
elif N == 2:
    print(min(p[1][0]+p[2][0], p[1][1]))
elif N == 3:
    dp[2] = min(p[1][0]+p[2][0], p[1][1])
    v1 = p[1][2]
    v2 = dp[1]+p[2][1]
    v3 = dp[2]+p[3][0]
    print(min(v1, v2, v3))
else:
    dp[2] = min(p[1][0]+p[2][0], p[1][1])
    dp[3] = min(p[1][2], dp[1]+p[2][1], dp[2]+p[3][0])
    print(f(N))

Проверяющая система выдаёт на одном из тестов ошибку выполнения (на каком - неизвестно). Перепроверяла на своих тестах - ошибка не возникала. Подскажите, пожалуйста, что делаю не так?

@Whabablca · 27.12.2025, 16:47

При N >= 2000: RecursionError: maximum recursion depth exceeded

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def f(n):
    if dp[n] != -1:
        return dp[n]
    v1 = f(n - 1) + p[n][0]
    v2 = f(n - 2) + p[n - 1][1]
    v3 = f(n - 3) + p[n - 2][2]
    dp[n] = min(v1, v2, v3)
    return dp[n]
 
N = 2000
p = [[0, 0, 0]] + [[1, 1, 1] for _ in range(N)]
dp = [-1] * (N+1)
 
dp[1] = p[1][0]
dp[2] = min(p[1][0]+p[2][0], p[1][1])
dp[3] = min(p[1][2], dp[1]+p[2][1], dp[2]+p[3][0])
 
print(f(N))

@Tamara09 · 27.12.2025, 19:10 **[ТС]**

Whabablca, спасибо большое, поняла.

@thyrex · 28.12.2025, 08:49

Зачем тут вообще рекурсия, приводящая к ошибке с глубиной, если за один проход можно заполнить весь список нужной информацией?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
t = []
for _ in range(n):
    t.append([int(i) for i in input().split()])
d = [0]*(n+1)
d[1] = t[0][0] # первый покупает только себе
if n > 1:
    d[2] = min(d[1]+t[1][0], t[0][1]) # второй покупает сам или первый покупает два билета
if n > 2:
    d[3] = min(d[2]+t[2][0], d[1]+t[1][1], t[0][2]) # третий покупает сам или второй покупает два билета или первый покупает три билета
for i in range(4, n+1):
    d[i] = min(d[i-1]+t[i-1][0], d[i-2]+t[i-2][1], d[i-3]+t[i-3][2])
print(d[n])

Новые блоги и статьи Все статьи Все блоги /
Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Tamara09 3 / 3 / 0 Регистрация: 29.06.2024 Сообщений: 18
	27.12.2025, 19:10 [ТС]
	Whabablca, спасибо большое, поняла. 0

Покупка билетов

Решение