MOZSATLA - Sharmeen and the Lost Array

 

MOZSATLA - Sharmeen and the Lost Array

no tags 

Sharmeen loves array very much. Many days ago she wrote an array ( of n elements and the index of this array is 1 based ) in her notebook, but unfortunately she lost the notebook. She want to restore the array. The only clue she know that is if in any position(i) of the array (1<= i < n ), the element in this position is greater than, equal or less than the next position(i+1) element.

            Can you help her to restore the array?

Input

In the first line given an integer t ( 1 <= t <= 100 ), which is the number of test cases.

For each test case,

In the first line there will be given a positive integer n ( 1 <= n <= 10^5 ) which is the size of the lost array. In the next line there will be n - 1 intergers Xi( 0 <= Xi <= 2 ).

If, Xi = 0 , then ith  element is equal to (i+1)th element of the lost array.

If, Xi = 1 , then ith  element is less than (i+1)th element of the lost array.

If, Xi = 2 , then ith  element is greater than (i+1)th element of the lost array.

Output

For each test case you have to output the lost array in one line. If multiple solution exist then you have to print the lexicographically smallest one. Elements of the lost array must be greater than zero( 0 ).

For better understanding see the sample input output.





Comments

Post a Comment

Popular posts from this blog

Sum of Even Numbers till N

Given a number N, print sum of all even numbers from 1 to N. #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){         if (i%2==0){             sum=sum+i;         }     }     cout<<sum;    } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){     ...
Read more

Find the Runner-Up Score!

  Given the participants' score sheet for your University Sports Day, you are required to find the runner-up score. You are given     scores. Store them in a list and find the score of the runner-up. Input Format The first line contains  . The second line contains an array     of   integers each separated by a space. Constraints Output Format Print the runner-up score. Sample Input 0 5 2 3 6 6 5 Sample Output 0 5 Explanation 0 Given list is  . The maximum score is  , second maximum is  . Hence, we print   as the runner-up score. ### OPTIMIZED ### from   collections   import   Counter if  __ name__  ==  '__main__' :      n  =  int ( input ())      arr  =  map ( int ,   input () . split ())           lis = list ( Counter ( arr ) . keys ())      lis . sort ()  ...
Read more

Print All Substrings

  For a given input string(str), write a function to print all the possible substrings. Substring A substring is a contiguous sequence of characters within a string. Example: "cod" is a substring of "coding". Whereas, "cdng" is not as the characters taken are not contiguous Input Format: The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case. Output Format: Print the total number of substrings possible, where every substring is printed on a single line and hence the total number of output lines will be equal to the total number of substrings. Note: The order in which the substrings are printed, does not matter. Constraints: 0 <= N <= 10^6 Where N is the length of the input string. Time Limit: 1 second Sample Input 1: abc Sample Output 1: a ab abc b bc c  Sample Input 2: co Sample Output 2: c co o #include <iostream> #include <cstring> us...
Read more