Array is an important data structure in computer science. It is also very important when it comes for problem solving. Very few problems are there all around the online judges in which you can skip using array. But somehow, now-a-days we really can avoid using array because of the great invention in C++: vector
.
So, why vector has made revolution in problem solving? Because, it can perform dynamic actions. For example, if you have a vector of size 10, but suddenly you need to store one extra element in the vector, you can easily do that by calling a simple function push_back()
. Again, you can insert a value at a specific index dynamically in the vector, whereas in array, you have to write your own code using loops and something extra to make this happen.
So, let’s do something with this vector today? We will be given vectors. Each vector can store one or more integers. Initially the first vector will only contain integer 1, 2nd vector will only contain integer 2, 3rd vector will only contain integer 3, …, -th vector will only contain integer .
We will have to perform following two tasks:
I already tried to code this thing. But alas! I failed ☹️. Don’t know how to solve it. Can you please help me out?
Each file of input will start with a single integer (), the number of test cases. Each test case starts with a line having two integers, , (). represents the number of initial vectors. represents the number of tasks we have to complete. Each of the next lines will contain any of the following two types of task:
1 X Y
- This type of input means to perform task of 1st type. ()
2 X
- This type of input means to perform task of 2nd type.
For each test case you will have to print a line with the case number.
After that, for every 2nd type of task, you will just need to print the median of the selected vector. For avoiding any precision error, you will have to print the answer multiplied by 2.
Input | Output |
---|---|
1 5 5 1 2 3 2 2 1 3 5 1 1 5 2 2 | Case 1: 5 5 |
Initially there are 5 vectors: , , , , . After 1st task: , , , Output of 2nd task: 5 (As the vector contains ) After 3rd task: , , After 4th task: , Output of 5th task: 5 |
Median is the middle of a sorted list of numbers. Median of is 2 and median of is 2.5.