magical girl and colored liquid potions

This Problem was quite easy, although it wasn't as compared to the Rating it had, I think maybe because I like such kind of questions and mostly these kinda questions are my strong side, by these kind of questions I refer to questions based on arrays, although the Problem Statement could be quite overwhelming at the starting but it needs to be read with an open head, mainly they are trying to confuse you with the complexity that they are trying to depict and the complications that they are mentioning but if you really think about the problem and just focus on the outcome then it becomes quite clear and banal.

At first, I thought they maybe I am missing something or there maybe any constraint issue, because they idea had came to my mind in the very first reading of the statement and so I rechecked the main logic, but eventually there was no corner case or trick in the Question, it came out to be the Correct Answer in the very first Submission.

The Explanation is quite straightforward.

An Interesting part here is that when I used the built-in max function, that submission took 0.01 secs less than the one in which I used my own max function.

This is because the built-in max function in Python is written in C. 

Problem Statement:-

Naturally, the magical girl is very good at performing magic. She recently met her master wizard Devu, who gifted her R potions of red liquid, B potions of blue liquid, and G potions of green liquid.

• The red liquid potions have liquid amounts given by r[1], ..., r[R] liters.
• The green liquid potions have liquid amounts given by g[1], ..., g[G] liters.
• The blue liquid potions have liquid amounts given by b[1], ..., b[B] liters.

She want to play with the potions by applying magic tricks on them. In a single magic trick, she will choose a particular color. Then she will pick all the potions of the chosen color and decrease the amount of liquid in them to half (i.e. if initial amount of liquid is x, then the amount after decrement will be x / 2 where division is integer division, e.g. 3 / 2 = 1 and 4 / 2 = 2).

Because she has to go out of station to meet her uncle Churu, a wannabe wizard, only M minutes are left for her. In a single minute, she can perform at most one magic trick. Hence, she can perform at most M magic tricks.

She would like to minimize the maximum amount of liquid among all of Red, Green and Blue colored potions. Formally Let v be the maximum value of amount of liquid in any potion. We want to minimize the value of v. Please help her.

Input

First line of the input contains an integer T denoting the number of test cases. Then for each test case, we have four lines.

The first line contains four space separated integers R, G, B, M. The next 3 lines will describe the amount of different color liquids (r, g, b), which are separated by space.

Output

For each test case, print a single integer denoting the answer of the problem.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ R, G, B, M ≤ 100
• 1 ≤ r[i], g[i], b[i] ≤ 10^9

Sample 1:

Input

Output

3
1 1 1 1
1
2
3
1 1 1 1
2
4
6
3 2 2 2
1 2 3
2 4
6 8

2
4
4

Explanation:

Example case 1. Magical girl can pick the blue potion and make its liquid amount half. So the potions will now have amounts 1 2 1. Maximum of these values is 2. Hence answer is 2.

Code Implementation:-

for _ in range(int(input())):

    r,g,b,m=map(int,input().split())

    def getMax(arr):

        n=len(arr)

        max_elem=-1

        for i in range(n):

            if(arr[i]>max_elem):

                max_elem=arr[i]

               

        return max_elem

    elems=[]

    for i in range(3):

        potion_amounts=list(map(int,input().split()))

        # elems.append(max(potion_amounts))

        elems.append(getMax(potion_amounts))

    elems.sort(reverse=True)

    for i in range(m):

        elems[0]//=2

        elems.sort(reverse=True)

    print(elems[0])

Explanation:-

Mainly, here we have 1 kind of operation that we can do, that is we can half all the elements(potion amounts) in any array(that means any kind of color group. Now we can do this operating m no. of times. So, the imp thing to note here is that we are just concerned about the max elem in any of the 3 arrays, when we do this operation we do it for every elem in the array, so we need to understand that the max will remain the max every time in an array, no matter how many times we perform the operation. So, we just need those 3 max elems and then just keep decrementing the max(means keep dividing the max by 2) and everytime keep checking the max.