|
|
| Строка 1: |
Строка 1: |
| − | from operator import itemgetter
| |
| | | | |
| − |
| |
| − | # Just for 1 test. Give a list of list to function. [[], [], [], []]
| |
| − | def find_optimal(orders):
| |
| − | orders.sort(key=itemgetter(3), reverse=True)
| |
| − |
| |
| − | start_finish = list()
| |
| − | work_volume = list()
| |
| − | prices = list()
| |
| − |
| |
| − | for order in orders:
| |
| − | start_finish.append(order[0])
| |
| − | start_finish.append(order[2])
| |
| − | work_volume.append(order[1])
| |
| − | prices.append(order[3])
| |
| − |
| |
| − | start_finish = [x - min(start_finish) for x in start_finish]
| |
| − |
| |
| − | # array of busy sequence
| |
| − | time_is_busy = [0] * (max(start_finish) + 1) # list with indicators: the day is empty for task?
| |
| − | # time_is_busy = [x+5 for x in range(max(start_finish)+1)]
| |
| − |
| |
| − | # array of deadlines
| |
| − | starts = start_finish[0::2]
| |
| − | deadlines = start_finish[1::2]
| |
| − |
| |
| − | penalty = 0
| |
| − |
| |
| − | for num_order in range(len(orders)):
| |
| − |
| |
| − | # Choosing the last day before deadline, when cheff can cook
| |
| − | deadline_index = deadlines[num_order]
| |
| − |
| |
| − | flag_abort = 0
| |
| − | if time_is_busy[deadline_index] != 0:
| |
| − | while (deadline_index > starts[num_order]) and (deadline_index >= 0):
| |
| − | if time_is_busy[deadline_index] == 0:
| |
| − | time_is_busy[deadline_index] = 10
| |
| − | flag_abort = 1
| |
| − | break
| |
| − | deadline_index = deadline_index - 1
| |
| − |
| |
| − | # How many dishes can a chef cook before the deadline, but from the start?
| |
| − | for work in range(1, work_volume[num_order] + 1):
| |
| − | if (time_is_busy[deadline_index - work] == 0) and ((deadline_index - work >= starts[num_order])):
| |
| − | time_is_busy[deadline_index - work] += 1
| |
| − | else:
| |
| − | work = work - 1
| |
| − | break
| |
| − | # print(f"In order No. {num_order+1}, {work + flag_abort} out of {work_volume[num_order]} dishes were prepared, each for {prices[num_order]} dollars. Penalty is {(work_volume[num_order] - work -flag_abort)*prices[num_order]}")
| |
| − | penalty = penalty + (work_volume[num_order] - work - flag_abort) * prices[num_order]
| |
| − |
| |
| − | return penalty
| |
| − |
| |
| − |
| |
| − | t = int(input())
| |
| − |
| |
| − | results = list()
| |
| − |
| |
| − | for test in range(t):
| |
| − |
| |
| − | all_orders_of_test = list()
| |
| − | count_of_orders = int(input())
| |
| − |
| |
| − | for order in range(count_of_orders):
| |
| − | all_orders_of_test.append([int(num) for num in input().split(' ')])
| |
| − |
| |
| − | results.append(find_optimal(all_orders_of_test))
| |
| − |
| |
| − | [print(x) for x in results]
| |