Bus full of passengers solution codechef

Bus full of passengers solution codechef

There is an empty bus with MM seats and a total of NN people, numbered from 11 to NN. Everyone is currently outside the bus. You are given a sequence of QQ events of the following form.

  • + i+ i : It denotes that the person ii enters the bus.

  •  i− i : It denotes that the person ii leaves the bus.

It is guaranteed in the input that each person from 11 to NN enters at most once as well as leaves the bus at most once.

Determine whether the sequence of events is consistent or not (i.e. no person leaves the bus before entering and the number of passengers in the bus does not exceed MM at any point of time).

Input Format Bus full of passengers solution codechef

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • Each test case contains Q+1Q+1 lines of input.
  • The first line of each test case contains three space-separated integers N,M,QN,M,Q.
  • QQ lines follow. For each valid jjjthjth of these lines contains a character chch, followed by a space and an integer ii. Here chch is either ‘++‘ or ‘‘ and 1iN1≤i≤N.
  • It is guaranteed that +‘‘+ ii” and ‘‘− ii” appears at most once for every 1iN1≤i≤N

Output Format Bus full of passengers solution codechef

For each test case, print a single line containing one string – “Consistent” (without quotes) if the sequence is consistent, “Inconsistent” (without quotes) otherwise.

Constraints

  • 1T201≤T≤20
  • 1N1041≤N≤104
  • 1M1041≤M≤104
  • 1Q1041≤Q≤104

Sample Input 1 

2
2 1 4
+ 1
+ 2
- 1
- 2
3 2 6
+ 2
+ 1
- 1
+ 3
- 3
- 2

Sample Output 1  Bus full of passengers solution codechef 

Inconsistent
Consistent

Explanation

  • Test case 11: After Person 22 enters the bus, there are two people inside the bus while the capacity of the bus is 11.

Sample Input 2 

2
100 10 5
+ 1
+ 2
- 3
+ 3
- 2
6 4 4
+ 3
+ 2
+ 1
+ 4

Sample Output 2 

Inconsistent
Consistent

Explanation

  • Test case 11: Person 33 leaves the bus without entering and thus it is inconsistent.
  • For Solution

    Click Here!

Leave a Reply

Your email address will not be published. Required fields are marked *

*