За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.
Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трех билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).
Входные данные
На вход программы поступает сначала число N — количество покупателей в очереди (1≤N≤5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.
Выходные данные
Требуется вывести одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.
Примеры
Входные данные
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
Выходные данные
12
Python
Задачу пожалуйста решите
Алексей Рейнбах
326
Используйте метод динамического программирования: вычислите некоторое f[i] для всех i от 0 до n, обозначающее минимальное время, за которое можно обслужить i покупателей. Перехода всего три: в f[i+1] за Ai, и т. д.
# Стандартный ввод
n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]
# Функция для вычисления минимума и его индекса
def get_min(lst):
~~~~m = lst[0]
~~~~ind = 0
~~~~for i in range(len(lst)):
~~~~~~~~ if lst[i] <= m:
~~~~~~~~~~~~m = lst[i]
~~~~~~~~~~~~ind = i
~~~~return m, ind
# Поиск в массиве с удалением (FIFO)
array = a[:]
s = 0
while array:
~~~~m, ind = get_min(array[0])
~~~~s += m
~~~~del array[:ind+1]
print(s)
n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]
# Функция для вычисления минимума и его индекса
def get_min(lst):
~~~~m = lst[0]
~~~~ind = 0
~~~~for i in range(len(lst)):
~~~~~~~~ if lst[i] <= m:
~~~~~~~~~~~~m = lst[i]
~~~~~~~~~~~~ind = i
~~~~return m, ind
# Поиск в массиве с удалением (FIFO)
array = a[:]
s = 0
while array:
~~~~m, ind = get_min(array[0])
~~~~s += m
~~~~del array[:ind+1]
print(s)
Шалюгин Сергей
22 178
Не ответ на задачу, но при желании можно легко переделать на ручной ввод.
"""
За основу взят код отсюда
https://site.ada.edu.az/~medv/acm/Docs e-olimp/Volume 8/799.htm
-----------
Генерация файла с данными
from random import randint
with open('Tickets.txt', 'w') as f:
~~~~for _ in range(5000):
~~~~~~~~print(randint(1,3600),randint(1,3600),randint(1,3600), file=f)~~~~
"""
# Читаем данные из файла в массив
A = []
with open('Tickets.txt') as f:
~~~~for a in f:
~~~~~~~~A.append(tuple(map(int, a.split())))
from timeit import default_timer as timer
start = timer()
# ...
t = [0]*(len(A)+1)
t[0] = 0
t[1] = A[0][0]
t[2] = min(A[0][0]+A[1][0], A[0][1])
for i in range(3, len(A)+1):
~~~~t[i] = min(t[i-1]+A[i-1][0], t[i-2]+A[i-2][1], t[i-3]+A[i-3][2])
print(t[-1])
end = timer()
print(end - start)
"""
За основу взят код отсюда
https://site.ada.edu.az/~medv/acm/Docs e-olimp/Volume 8/799.htm
-----------
Генерация файла с данными
from random import randint
with open('Tickets.txt', 'w') as f:
~~~~for _ in range(5000):
~~~~~~~~print(randint(1,3600),randint(1,3600),randint(1,3600), file=f)~~~~
"""
# Читаем данные из файла в массив
A = []
with open('Tickets.txt') as f:
~~~~for a in f:
~~~~~~~~A.append(tuple(map(int, a.split())))
from timeit import default_timer as timer
start = timer()
# ...
t = [0]*(len(A)+1)
t[0] = 0
t[1] = A[0][0]
t[2] = min(A[0][0]+A[1][0], A[0][1])
for i in range(3, len(A)+1):
~~~~t[i] = min(t[i-1]+A[i-1][0], t[i-2]+A[i-2][1], t[i-3]+A[i-3][2])
print(t[-1])
end = timer()
print(end - start)
Сергей Пестов
21 729
Шалюгин Сергей
Вариант не очень красивый, но работает гораздо быстрее чем мой.
https://pastebin.com/raw/jSdDEzzN
только вот в примере минимальное время - 10, если я правильно понял условия задачи
только вот в примере минимальное время - 10, если я правильно понял условия задачи
Сергей Пестов
"в примере минимальное время - 10, если я правильно понял условия задачи"
Нет, там все правильно, минимальное 12.
Вот так 5 + 2 + 5, я их скобочками выделил
5
((5)) 10 15
((2)) 10 15
5 5 ((5))
20 20 1
20 1 1
Нет, там все правильно, минимальное 12.
Вот так 5 + 2 + 5, я их скобочками выделил
5
((5)) 10 15
((2)) 10 15
5 5 ((5))
20 20 1
20 1 1
Похожие вопросы
- Помогите, пожалуйста, решить задачу Python
- Помогите мне пожалуйста решить задачу на питоне!
- Помогите пожалуйста решить задачу "Ход конём" в Python.
- Помогите решить задачу пожалуйста
- Помогите пожалуйста решить задачу по программированию наpython.
- Помогите пожалуйста решить задачу на python
- Добрый вечер, помогите, пожалуйста, решить задачу по информатике
- Помогите пожалуйста решить задачу на питоне...
- Помогите пожалуйста решить задачи на питоне:
- Помогите с задачей, пожалуйста
В самом коде я не разбирался, но при попытке скармливать ему разные наборы циферок, он выдает какие-то не те ответы.