[Solved] 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

  • 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

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 

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.

Solution 


Python

for i in range(int(input())):
n,m,q=map(int, input().split())
c=0
flag=0
l=[]
for i in range(q):
a,b=map(str,input().split())
if a==”+”:
c+=1
r=int(b)
if i==0:
l.append(r)
elif r in l:
flag=1
elif r not in l:
l.append(r)
if (c>m):
flag=1
elif a==”-“:
c=c-1
r=int(b)
if (c<0 or r not in l):
flag=1
if r in l:
l.remove(r)
if flag==1:
print(“Inconsistent”)
else:
print(“Consistent”)# cook your dish here


C++

#include<bits/stdc++.h>
using namespace std;
int main(){
int t,j;
cin>>t;
for (j=0;j<t;j++)
{
int n,m,q,i;
cin>>n>>m>>q;
unordered_set<int> st;
int b=1;
for (i=0;i<q;i++)
{
char ch;
int val;
cin >>ch>>val;
if (b==1){
if(ch==’-‘){
if (st.find(val)!=st.end()){
st.erase(val);
}
else{
b=0;
}
}
else{
if ((int )st.size()==m){
b=0;
}
else{
st.insert(val);
}
}
}

}
if (b==0)
{
cout <<“Inconsistent” <<endl;
}
else
cout <<“Consistent”<<endl;
}
return 0;

}


Java

/* package codechef; // don’t place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner s=new Scanner(System.in);
int test_case=s.nextInt();
int i=0;
while(i<test_case){
int N=s.nextInt();
int M=s.nextInt();
int Q=s.nextInt();
ArrayList <Integer> arr=new ArrayList <>();
int count=0;
int j=0;
boolean cons=true;
while(j<Q){
String symbol=s.next();
int passenger=s.nextInt();
if(symbol.equals(“+”)){
arr.add(passenger);
count=count+1;
}
else{
int index=arr.indexOf(passenger);
if(index==-1){
cons=false;
}
else{
arr.remove(index);
count=count-1;
}
}
if(count>M){
cons=false;
}
j=j+1;
}
if(cons==false){
System.out.println(“inconsistent”);
}
else{
System.out.println(“consistent”);
}
i=i+1;

}
// your code goes here
}
}


C

#include <stdio.h>

int main(void) {

int t;
scanf(“%d”,&t);
for(int i=0;i<t;i++){
int n,m,q;
scanf(“%d%d%d\n”,&n,&m,&q);
int a[n];
int count=0,flag=0;
for(int j=0;j<q;j++){
char ch,tr;
int temp;
scanf(“%c”,&ch);
scanf(“%c”,&tr);
scanf(“%d\n”,&temp);
if(ch==’+’){
count++;
if(count>m){
flag=1;
}
a[temp]=1;
}
else if(ch==’-‘){
if(a[temp]==1){
a[temp]=0;
count–;
}
else{
flag=1;
}
}
}
if(flag==0){
printf(“Consistent\n”);
}
else{
printf(“Inconsistent\n”);
}
}
return 0;
}


C#

#region usings
using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using static System.Math;
using static System.Array;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Web;

#endregion
namespace CodeChef
{
public class Solution
{
private static readonly Scanner sc = new Scanner();
private const long MOD = 1000000007;
static void Main()
{
int test = sc.ReadInt();
while (test– > 0)
{
long[] nmq = sc.ReadLongArr();
List<string> entries = new List<string>();
for (int i = 0; i < nmq[2]; i++)
{
entries.Add(sc.ReadLine());
}
Solve(nmq, entries);
}
sc.Flush();
sc.Close();
}

private static void Solve(long[] nmq, List<string> entries)
{
long n = nmq[0], m = nmq[1], q = nmq[2];
bool result = true; int count = 0;
List<int> map = new List<int>();
foreach (var item in entries)
{
bool sign = item[0] == ‘+’ ? true : false;
int num = Convert.ToInt32(item[2]);
if (sign)
{
map.Add(num);
count++;
if(count>m)
{
result = false;
break;
}
}
else if (!sign)
{
if (map.Contains(num))
{
map.Remove(num);
count–;
}
else
{
result = false;
break;
}
}
}
if (result)
sc.WriteLine(“Consistent”);
else
sc.WriteLine(“Inconsistent”);
}
}
public class Scanner
{

#if (!DEBUG)
public static StreamReader streamReader = new StreamReader(Console.OpenStandardInput());
public static StreamWriter streamWriter = new StreamWriter(Console.OpenStandardOutput());
#else
public static StreamReader streamReader = new StreamReader(@”C:\Users\869963\source\repos\Competitive\Codechef\TextFile1.txt”);
public static StreamWriter streamWriter = new StreamWriter(@”C:\Users\869963\source\repos\Competitive\Codechef\TextFile2.txt”);
#endif
#region Input
public int ReadInt()
{
return Convert.ToInt32(streamReader.ReadLine());
}
public string ReadLine()
{
return streamReader.ReadLine();
}
public long ReadLong()
{
return Convert.ToInt64(streamReader.ReadLine());
}
public double ReadDouble()
{
return Convert.ToDouble(streamReader.ReadLine());
}
public int[] ReadIntArr()
{
return ConvertAll(streamReader.ReadLine().TrimEnd().Split(‘ ‘), t => Convert.ToInt32(t));
}
public float[] ReadFloatArr()
{
return ConvertAll(streamReader.ReadLine().TrimEnd().Split(‘ ‘), t => float.Parse(t));
}
public long[] ReadLongArr()
{
return ConvertAll(streamReader.ReadLine().TrimEnd().Split(‘ ‘), t => Convert.ToInt64(t));
}
public char[] ReadCharArr()
{
return streamReader.ReadLine().ToCharArray();
}
public int[][] ReadInt2DArr(long n)
{
int[][] res = new int[n][];
for (int i = 0; i < n; i++)
{
res[i] = ReadIntArr();
}
return res;
}
#endregion
#region Output
public void Write<T>(T t)
{
streamWriter.Write(t);
}
public void WriteLine<T>(T result)
{
streamWriter.WriteLine(result);
}
public void Write2DMatrix<T>(T[,] sum, int n, int m)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
Write<string>($”{sum[i, j]}”);
}
WriteLine<string>(“”);
}
}
public void YESNO(bool condition)
{
WriteLine(!condition ? “YES” : “NO”);
}
public void YesNo(bool condition)
{
WriteLine(condition ? “Yes” : “No”);
}
public void yesno(bool condition)
{
WriteLine(condition ? “yes” : “no”);
}
public void Flush()
{
streamWriter.Flush();
}
public void Close()
{
streamReader.Close();
streamWriter.Close();
}
internal void WriteArray(long[] secondHalf)
{
for (int i = 0; i < secondHalf.Length; i++)
{
streamWriter.Write(secondHalf[i] + ” “);
}
WriteLine(“”);
}
#endregion
}
}


Also read : Black cells in a chessboard solution codechef

Also read : Large Square solution codechef

Bus full of passengers solution codechef

 

No Comments, Be The First!

Your email address will not be published.