Given N classrooms in a school and each classroom has a capacity of A[i] students. Bob is a builder and follows the instructions of Alice.
Alice gives Q instructions of the following types: - 1 L 0: Move L classrooms to the left - 2 R 0: Move R classrooms to the right - 3 X Y: Remove the next classroom and add two new classrooms of capacity X and Y respectively to the ri
ght of the current classroom. (After performing this operation, classroom numbers change accordingly)
Note: The queries are always valid.
Initially, Bob is in the first classroom. After performing all instructions from Alice, print the capacity of all classrooms from 1 to the total number of classrooms.
Function description
Complete the solve function. This function takes the following 2 parameters and returns the required answer.
Parameters: - A: Represents a linear array denoting the capacity of classrooms in the old school - queries: Represents a 2D array denoting instructions given by Alice of the given types
Input format for custom testing
Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.
- The first line contains two space-separated integers N and Q denoting the initial number of classrooms and the number of instructions. - The second line contains N space-separated integers denoting initial classroom capacities. - Next Q lines contain queries of the form: - 1 L 0 - 2 R 0 - 3 X Y
Output format
After performing all instructions from Alice, return the capacity of all classrooms from 1 to K (K = total number of classrooms in the renovated school).
Sample input
5 4 1 2 1 4 5 2 1 0 1 1 1 1 2 0 3 5 2
Sample output
1 2 5 7 4 1 1
Explanation
Bob moves 1 classroom right, so he is in the 2nd classroom now. He moves 1 classroom left, so he is back to the 1st classroom. He moves 2 classrooms left (stays at index 0 since it's the start). Then, from current position (0), he removes the next classroom (2nd) with capacity 2 and adds classrooms with capacities 5 and 7. Final classroom capacities: [1, 2, 5, 7, 4, 1, 1]
You are given three integers L, R, and K. A number X represents a lucky number if the binary representation of X contains the pattern 101 as a substring. Determine the Kth lucky number between L and R. If the Kth lucky number does not exist, then print -1.
Function description
Complete the solve function. This function takes the following 3 parameters and returns the Kth
lucky number in between L and R.
Parameters: - L: Represents an integer denoting the value of L - R: Represents an integer denoting the value of R - K: Represents an integer denoting the Kth lucky number to be found
Input format for custom testing
Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.
- The first line contains T, which represents the number of test cases. - For each test case: - The first line contains three space-separated integers L, R, and K.
Output format
For each test case, print the Kth lucky number in the range [L, R] on a new line. If the Kth lucky number does not exist, then print -1.
Constraints
1 ≤ T ≤ 200 1 < L ≤ R ≤ 10^18 1 ≤ K ≤ 10^18
Sample input
6 5 40 6 5 12 4 9 20 5 7 7 1 14 37 4 13 25 4
Sample output
21 -1 -1 -1 23 22
Explanation:
For test case 1: All lucky numbers between 5 and 40 are 5, 10, 11, 13, 20, 21, 22, 23, 26, 27, 29, 37, and 40. The sixth lucky number is 21. For test case 2: All lucky numbers between 5 and 12 are 5, 10, and 11. There are less than 4 lucky numbers, so print -1. For test case 3: All lucky numbers between 9 and 20 are 10, 11, and 13. There are less than 5 lucky numbers, so print -1. For test case 4: There are 0 lucky numbers between [7, 7], so print -1. For test case 5: All lucky numbers between 14 and 37 are 20, 21, 22, 23, 26, 27, 29, and 37. The fourth lucky number is 23. For test case 6: All lucky numbers between 13 and 25 are 13, 20, 21, 22, and 23. The fourth lucky number is 22.
Note:
Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.
Limits
Time Limit: 1.0 sec(s) for each input file Memory Limit: 256 MB Source Limit: 1024 KB