Hoodies at Coding Blocks
//It's winter season. There is a long queue of students from the four prime courses at Coding Blocks and everyone is here to grab his hoodie. Each student of a course has a different roll number. Whenever a new student will come, he will search for his friend from the end of the queue. Note that a student can only has friend from his course and not from any other course. As soon as he will find any of the friend in the queue, he will stand behind him, otherwise he will stand at the end of the queue. At any moment Kartik Bhaiya will ask the student, who is standing in front of the queue, to come and put his name and grab his hoodie and then remove that student from the queue. There are Q operations of one of the following types:
//
//E x y : A new student of course x whose roll number is y will stand in queue according to the method mentioned above.
//D : Kartik Bhaiya will ask the student, who is standing in front of the queue, to come and put his name for the hoodie and remove him from the queue.
//Find out the order in which student put their name.
//
//Note: Number of dequeue operations will never be greater than enqueue operations at any point of time.
//
//Input Format
//First line contains an integer Q, denoting the number of operations. Next Q lines will contains one of the 2 types of operations.
//
//Constraints
//1 ≤ x ≤ 4 1 ≤ y ≤ 50000 1 ≤ Q ≤ 100000
//
//Output Format
//For each 2nd type of operation, print two space separated integers, the front student's course and roll number.
//
//Sample Input
//5
//E 1 1
//E 2 1
//E 1 2
//D
//D
//Sample Output
//1 1
//1 2
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int q; cin >> q;
int tot[5]; for (int i = 0; i < 5; i++) tot[i] = -1;
tot[0] = 0;
queue<int> qu[5];
while (q--) {
char ch;
cin >> ch;
if (ch == 'E') {
int x, r; cin >> x >> r;
tot[0]++;
qu[x].push(r);
if (tot[x] == -1) tot[x] = tot[0];
} else {
int id = 0; int mini = INT_MAX;
for (int i = 1; i <= 4; i++)
if (tot[i] != -1 && tot[i] < mini) {
mini = tot[i];
id = i;
}
cout << id << " " << qu[id].front() << endl;
qu[id].pop();
if (qu[id].empty()) tot[id] = -1;
}
}
return 0;
}
Importance of Time
//There are N processes to be completed. All the processes have a unique number assigned to them from 1 to N.
//
//Now, we are given two things:
//
//1)The calling order in which all the processes are called.
//2)The ideal order in which all the processes should have been executed.
//
//Executing a process takes 1 unit of time. Changing the position takes 1 unit of time.
//
//We have to find out the unit of time required to complete all the process such that a process is executed from the ideal order only when it exists at the same index in the calling order. We can push the first term from the calling order to the last thus rotating the order.
//
//Input Format
//First line contains a single integer N.
//Next line contains N space separated integers denoting the calling order.
//Last line contains N space separated integers denoting the ideal order.
//
//Constraints
//1 <= N <= 10^6
//
//Output Format
//The total time required
//
//Sample Input
//5
//5 4 2 3 1
//5 2 1 4 3
//Sample Output
//7
//Explanation
//Iteration #1: Since the ideal order and calling order both has process #5 to be executed first. Process #5 is executed taking 1 unit of time. The new calling order is: 4 - 2 - 3 - 1. Time taken in step #1: 1.
//
//Iteration #2: Since the ideal order has process #2 to be executed firstly, the calling ordered has to be changed again, i.e., the first element has to be pushed to the last place. The new calling order is: 2 - 3 - 1 - 4 and process #2 is executed. Time taken in step #2: 2.
//
//Iteration #3: Since the ideal order has process #1 to be executed firstly, the calling ordered has to be changed again, i.e., the first element has to be pushed to the last place. The new calling order is: 1 - 4 - 3 and process #1 is executed. Time taken in step #2: 2.
//
//Iteration #4: Since the new first element of the calling order is same as the ideal order, that process will be executed. Time taken in step #4: 1.
//
//Iteration #5: Since the last element of the calling order is same as the ideal order, that process will be executed. Time taken in step #5: 1.
//
//Total time taken = 7
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
queue<int> q;
queue<int> ideal;
for(int i=0;i<n;i++){
int val; cin >> val;
q.push(val);
}
for(int i=0;i<n;i++){
int val; cin >> val;
ideal.push(val);
}
int totaltime = 0;
while(!q.empty()){
if(q.front() == ideal.front()){
totaltime++;
q.pop();
ideal.pop();
}
else{
totaltime++;
int temp = q.front();
q.push(temp);
q.pop();
}
}
cout << totaltime;
return 0;
}
Queue Using Stack
//Implement a Queue using two stacks Make it Dequeue efficient.
//
//Input Format
//Enter the size of the queue N add 0 - N-1 numbers in the queue
//
//Constraints
//Output Format
//Display the numbers in the order they are dequeued and in a space separated manner
//
//Sample Input
//5
//Sample Output
//0 1 2 3 4
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
class Kyu{
stack<int> s1,s2;
public:
void push(int data){
s1.push(data);
}
int dequeue(){
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
}
int data = s2.top();
s2.pop();
return data;
}
};
int main() {
int n;cin >> n;
Kyu q;
for(int i=0;i<n;i++){
q.push(i);
}
for(int i=0;i<n;i++){
cout << q.dequeue() << " ";
}
return 0;
}
The Queue Game
//The Game is as follows You have given a binary array, where 1 denotes push operation and 0 denotes a pop operation in a queue. The task is to check if the possible set of operations are valid or not.
//Print Valid if the set of Operations are Valid Otherwise Print Invalid.
//
//Input Format
//The First Line contains an Integer T, as the number of Test cases.
//The Next Line contains an Integer N, as the Size of the Array.
//The Next Line contains N Binary numbers separated by space.
//
//Constraints
//Output Format
//Print Valid If the set of operations are valid Otherwise Print Invalid for each Test Case separated by a new Line.
//
//Sample Input
//2
//5
//1 1 0 0 1
//5
//1 1 0 0 0
//Sample Output
//Valid
//Invalid
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main () {
int t; cin >> t;
while(t--){
int n; cin >> n;
int valid = 0;
bool check = true;
while(n--){
int val; cin >> val;
if(val == 1) valid++;
else{
if(valid == 0){
check = false;
}
valid--;
}
}
if(check) cout << "Valid" << endl;
else cout << "Invalid" << endl;
}
return 0;
}