После окончания уроков n групп школьников вышли на улицу и собрались ехать домой к Поликарпу на празднование его дня рождения. Известно, что i-ая группа состоит из si друзей (1 ≤ si ≤ 4), которые не хотят расставаться по пути к Поликарпу. Решено ехать на такси. Каждая машина может вместить не более четырех пассажиров. Какое минимальное количество машин потребуется школьникам, если каждая группа должна целиком находиться в одной из машин такси (но одна машина может вмещать более чем одну группу)?
Я написал алгоритм(он вроде даже правильный), но по времени очень громоздкий. Не подскажите как можно ускорить программу. Или как хотя бы через профилировщик посмотреть где много времени съедается.
Заранее спасибо.
lst = []
def func1(lst):
numberGroup = input()
string = input()
lst = list(string.replace(' ', ''))
for i in range(0, len(lst)):
lst[i] = int(lst[i])
return lst
lst = func1(lst)
def func(lst):
k = -1
counter = 0
for i in range(0, len(lst)):
if lst[i] == 4:
lst[i] = 0
counter = counter + 1
elif lst[i] == 3:
counter =counter + 1
lst[i] = 0
if lst.count(1) != 0:
lst[lst.index(1, 0, len(lst))] = 0
elif lst[i] == 2:
counter = counter + 1
lst[i] = 0
if lst.count(2) != 0:
lst[lst.index(2, 0, len(lst))] = 0
elif lst.count(1) > 1:
lst[lst.index(1, 0, len(lst))] = 0
lst[lst.index(1, 0, len(lst))] = 0
elif lst.count(1) == 1:
lst[lst.index(1, 0, len(lst))] = 0
for i in range(0, len(lst)):
if lst[i] == 1:
k = k + 1
if lst.count(1) != 0:
counter = counter + int(k * 0.25 + 1)
return counter
counter = func(lst)
print(counter)