forked from anubhab91/CodeForces-5
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTaxi.py
More file actions
46 lines (35 loc) · 1.29 KB
/
Taxi.py
File metadata and controls
46 lines (35 loc) · 1.29 KB
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
'''
http://codeforces.com/problemset/problem/158/B
'''
from collections import defaultdict
class Taxi:
def solve(self,n,students):
#create frequency dictionary for students-count in list students
d = defaultdict(int)
for i in students:
d[i] +=1
taxiCount = 0
#for all the 4student and 3student groups, we need separate taxis
taxiCount+= d[4]+d[3]
#for all 3student groups, we need to fill them with 1student groups
d[1]-=d[3]
#for all 2student groups, add their count to taxiCount
taxiCount+= (d[2]/2)
#for remaining 2student groups, one more taxi will be allocated
if(d[2]%2>0):
taxiCount+=1
#deduct 2 1student groups to be adjusted in the 2student taxis
d[1]-=2
#if any 1student groups are left
if(d[1]>0):
taxiCount+=(d[1]/4)
#for remaining 1student groups, one more taxi will be allocated
if(d[1]%4>0):
taxiCount+=1
return taxiCount
if __name__ == "__main__":
students = list()
n = int(raw_input())
students = map(int,raw_input().split(" "))
t = Taxi()
print t.solve(n,students)