jiva-the-self-driven-car

Jiva is a self driven car and is out on its very first drive. It aims to earn some revenue by serving as taxi driver.
It starts its journey from a point and travels in a line for 100 Km. It picks and drops passenger on the way,but can accommodate a maximum of M passengers at once. 

Jiva wants be very economical & intends to equally split the fare among the number of passengers as the following :
- The normal rate being - 10 INR/Km for every passenger
- If there are 2 passengers in the car at any part of journey, it gives a 5% discount to both the passengers for that part of the journey.
- If there are 3 or more passengers in the car at any part of journey, it gives a 7% discount to all of them for that part of the journey.
Also note that if the cab was full at any point in the journey,Jiva can not take any more passengers at that time and reports "Cab was full" to its engineers in the end.
Given, a total of N passengers that board Jiva at different points. Find the total revenue earned after the journey completes. 
(See N.B. Section)  

Input:
The first line contains an integer T. T test cases follow.
Second line of each test case contains 2 space-separated integers N and M.
Next N lines contain 2 space-separated integers ( Si and Ei ), the pick up and drop point of the i'th passenger w.r.t the starting point.  

Output: 
Print the revenue earned (Rounded to the nearest integer) followed by "Cab was full" (without the quotes) ,if applicable, in a new line for each test case.  

N.B. If at a particular point of time, Jiva can take some people to fulfill the capacity then it would take the people in preference of the order in which they are mentioned in the problem statement.
Suppose, The input is:
2 1
0 20
0 100
At time T = 0, there are 2 people, but Jiva can take only one of them. It will give higher priority to the person mentioned first i.e. The person with time 0-20.  

Constraints: 
1 ≤ T ≤ 10
0 ≤ N, M ≤ 1000
0 ≤ Si ≤ Ei  ≤ 100  

Note: Candidates need to attempt only one of the given problems

SAMPLE INPUT
2
4 3 
0 100
0 20
30 50
40 80
6 4
10 55
10 20
40 60
55 60
60 70
75 95

SAMPLE OUTPUT
1719 Cab was full
1070

Source: hackerearth | Difficulty: EASY
Tags: Mathematics


Solutions:
import math
t=eval(input())
while(t>0):
	t-=1
	n,cap=list(map(int,input().split()))
	g={}
	for i in range(n):
		s,e=list(map(int,input().split()))
		#print s,e
		if(s<e and s!=100):
					if s not in g:
						g[s]=[]
					g[s].append((s,e))
##    print g
##    print "*******************"
		
	r=0.0
	p_cap=0
	assign_lst={}
	flag=0
	for p_km in range(101):
		if (p_km in list(assign_lst.keys())):
				p_cap-=(assign_lst[p_km])
			
			
			
			
		if p_km in list(g.keys()):
			lst=g[p_km]
			for ind in lst: 
				if(p_cap<cap):
					p_cap+=1
					if ind[1] not in list(assign_lst.keys()):
						assign_lst[ind[1]]=0
					assign_lst[ind[1]]+=1
		if(p_cap==cap):
			flag=1
		if p_cap==1:
			r=r+10
		elif p_cap ==2:
			r=r+((10-((10*5)/float(100)))*2)
		elif p_cap>=3:
			r=r+((10-((10*7)/float(100)))*p_cap)
		
	#print int("{:g}".format(r)),
	print(int(round(r)), end=' ')
	if(flag==1):
		print("Cab was full")
	else:
		print()
		
					
			
		
		


import math
t=eval(input())
while(t>0):
	t-=1
	n,cap=list(map(int,input().split()))
	g={}
	for i in range(n):
		s,e=list(map(int,input().split()))
		#print s,e
		if(s<e and s!=100):
					if s not in g:
						g[s]=[]
					g[s].append((s,e))
##    print g
##    print "*******************"
		
	r=0
	p_cap=0
	assign_lst={}
	flag=0
	for p_km in range(101):
		if (p_km in list(assign_lst.keys())):
				p_cap-=(assign_lst[p_km])
			
			
			
			
		if p_km in list(g.keys()):
			lst=g[p_km]
			for ind in lst: 
				if(p_cap<cap):
					p_cap+=1
					if ind[1] not in list(assign_lst.keys()):
						assign_lst[ind[1]]=0
					assign_lst[ind[1]]+=1
		if(p_cap==cap):
			flag=1
		if p_cap==1:
			r=r+10
		elif p_cap ==2:
			r=r+((10-((10*5)/float(100)))*2)
		elif p_cap>=3:
			r=r+((10-((10*7)/float(100)))*p_cap)
		
	#print int("{:g}".format(r)),
	print(int(round(r)), end=' ')
	if(flag==1):
		print("Cab was full")
	else:
		print()
		
					
			
		
		


import sys
t = int(sys.stdin.readline())
while(t>0):	
	cabfull = False
	t-=1
	N,M=list(map(int,sys.stdin.readline().split()))
	start = [[] for i in range(101)]
	end = [0 for i in range(101)]
	for i in range(N):
		s,e = list(map(int,sys.stdin.readline().split()))
		start[s].append((s,e))

	passengers = 0
	cost = 0
	for i in range(101):
		if(passengers<2):
			cost+=passengers*10
		
		elif(passengers==2):
			cost+=passengers*10*(0.95)
		
		elif(passengers>=3):
			cost+=passengers*10*(0.93)
				
		if(end[i]!=0):
			passengers-=end[i]
		
		if(passengers<M):
			if(start[i]!=[]):
				for pas in start[i]:
					if(passengers<M):
						passengers+=1						
						
						if(cabfull==False):
							if(passengers==M):
								cabfull=True

						if(pas[1]>pas[0]):
							end[pas[1]]+=1
						else:							
							passengers-=1

	if(cabfull):
		print(str(int(round(cost))) + " Cab was full")
	else:
		print(str(int(round(cost))))