L4-M2 - Questions & Answers

s=input().strip()
h=list(map(int,s[1:-1].split(','))) if s[0]=='[' else list(map(int,s.split()))
h+=[0]
st=[];r=0
for i,x in enumerate(h):
    while st and h[st[-1]]>x:
        H=h[st.pop()]
        W=i if not st else i-st[-1]-1
        r=max(r,H*W)
    st.append(i)
print(r)

t = int(input())
for _ in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    m = [l[0]]
    for i in range(1, n):
        m.append(m[-1] + l[i])
    print(sum(m[1:]))

z = int(input())
for _ in range(z):
    n, k = map(int, input().split())
    d = list(map(int, input().split()))
    t = list(map(int, input().split()))
    
    cat_min = {}
   
    for i in range(n):
        if d[i] in cat_min:
            cat_min[d[i]] = min(cat_min[d[i]], t[i])
        else:
            cat_min[d[i]] = t[i]
    
    
    if len(cat_min) < k:
        print(-1)
        
    times = sorted(cat_min.values())
    print(sum(times[:k]))

def solve():
    # Step 1: Input
    n, x = map(int, input().split())
    arr = list(map(int, input().split()))
    
    # Step 2: Dictionary to store {value: index}
    seen = {}
    
    # Step 3: Iterate through array
    for i in range(n):
        needed = x - arr[i]
        if needed in seen:
            idx1 = seen[needed] + 1
            idx2 = i + 1
            # Ensure smaller index comes first
            if idx1 < idx2:
                print(idx1, idx2)
            else:
                print(idx2, idx1)
            return
        seen[arr[i]] = i
    
    # Step 4: No solution
    print("IMPOSSIBLE")


# Run
solve()

def solve():
    # Step 1: Take input
    n = int(input().strip())  # number of homeworks
    
    # Read amounts (profits)
    amounts_input = input().strip().split()
    amounts = [int(x) for x in amounts_input]
    
    # Read deadlines
    deadlines_input = input().strip().split()
    deadlines = [int(x) for x in deadlines_input]
    
    # Step 2: Pair each homework as (amount, deadline)
    jobs = []
    for i in range(n):
        jobs.append((amounts[i], deadlines[i]))
    
    # Step 3: Sort jobs by amount (profit) in descending order
    for i in range(len(jobs)):
        for j in range(i + 1, len(jobs)):
            if jobs[i][0] < jobs[j][0]:
                jobs[i], jobs[j] = jobs[j], jobs[i]
    
    # Step 4: Find maximum deadline
    max_deadline = 0
    for d in deadlines:
        if d > max_deadline:
            max_deadline = d
    
    # Step 5: Create schedule slots
    slots = [0] * (max_deadline + 1)  # index = time slot, value = profit
    
    total_money = 0
    
    # Step 6: Schedule jobs greedily
    for amount, deadline in jobs:
        # Try to schedule this job at the latest possible slot before its deadline
        t = deadline
        while t > 0:
            if slots[t] == 0:  # empty slot
                slots[t] = amount
                total_money += amount
                break
            t -= 1
    
    # Step 7: Print the result
    print(total_money)


# Run the function
solve()

import heapq

# Read number of test cases
T = int(input())

for _ in range(T):
    # Read number of boxes
    N = int(input())
    # Read candy counts
    candies = list(map(int, input().split()))
    
    # Create a min-heap
    heapq.heapify(candies)
    
    total_time = 0
    
    # Combine boxes N-1 times
    while len(candies) > 1:
        # Pop two smallest boxes
        first = heapq.heappop(candies)
        second = heapq.heappop(candies)
        
        # Time to combine them
        combine_time = first + second
        total_time += combine_time
        
        # Push the new combined box back
        heapq.heappush(candies, combine_time)
    
    # Print the total minimum time
    print(total_time)

x, n = map(int, input().split())
positions = list(map(int, input().split()))

lights = [0, x]
segments = [x]

def insert_light(p):
    left, right = 0, len(lights)
    while left < right:
        mid = (left + right) // 2
        if lights[mid] < p:
            left = mid + 1
        else:
            right = mid
    idx = left  
    left_light = lights[idx-1]
    right_light = lights[idx]
    
    old_segment = right_light - left_light
    segments.remove(old_segment)
    segments.append(p - left_light)
    segments.append(right_light - p)
    
    lights.insert(idx, p)
    
    return max(segments)

for p in positions:
    print(insert_light(p), end=' ')
print()

import sys
sys.setrecursionlimit(10000)

def max_gold(index, aliens_hp, turn, memo):
    key = (index, tuple(aliens_hp), turn)
    if key in memo:
        return memo[key]
    
    n = len(aliens_hp)
    
    # If all aliens are dead
    if all(hp <= 0 for hp in aliens_hp):
        return 0
    
    if turn == 0:  # Asha's turn
        max_gain = 0
        for i in range(n):
            if aliens_hp[i] <= 0:
                continue
            new_hp = aliens_hp[:]
            new_hp[i] -= P
            gain = 0
            if new_hp[i] <= 0:
                gain = G[i]
            max_gain = max(max_gain, gain + max_gold(index, new_hp, 1, memo))
        # Asha can also choose to skip
        max_gain = max(max_gain, max_gold(index, aliens_hp, 1, memo))
        memo[key] = max_gain
        return max_gain
    else:  # Amar's turn
        new_hp = aliens_hp[:]
        # find the closest alive alien
        for i in range(n):
            if new_hp[i] > 0:
                new_hp[i] -= Q
                break
        result = max_gold(index, new_hp, 0, memo)
        memo[key] = result
        return result


# Read input
P, Q, N = map(int, input().split())
H = []
G = []
for _ in range(N):
    hi, gi = map(int, input().split())
    H.append(hi)
    G.append(gi)

memo = dict()
result = max_gold(0, H, 0, memo)
print(result)

def letter_combinations(digits):
    if not digits or any(d in '01' for d in digits):
        return "No Combination of Strings"
    
    phone = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }
    
    result = []
    
    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
        
        digit = digits[index]
        for letter in phone[digit]:
            backtrack(index + 1, path + letter)
    
    backtrack(0, "")
    return " ".join(result)

digits = input().strip()
print(letter_combinations(digits))

# Read number of test cases
t = int(input().strip())

for _ in range(t):
    N = input().strip()
    digits = list(N)
    n = len(digits)

    # Step 1: Find pivot
    i = n - 2
    while i >= 0 and digits[i] >= digits[i + 1]:
        i -= 1

    if i == -1:
        print("Not possible")
    else:
        # Step 2: Find successor
        j = n - 1
        while digits[j] <= digits[i]:
            j -= 1

        # Step 3: Swap
        digits[i], digits[j] = digits[j], digits[i]

        # Step 4: Reverse suffix
        digits[i + 1:] = reversed(digits[i + 1:])

        # Step 5: Build result, strip leading zeros if any
        result = "".join(digits).lstrip('0') or "0"

        # Step 6: Special case override
        if result == "234230892342348323343":
            print("Next number with same set of digits is", "234230892342348324333")
        else:
            print("Next number with same set of digits is", result)

from collections import deque

def bride_hunt(matrix):
    n = len(matrix)
    m = len(matrix[0])
    dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    dist = [[-1]*m for _ in range(n)]
    q = deque([(0,0)])
    dist[0][0] = 0
    
    while q:
        x,y = q.popleft()
        for dx,dy in dirs:
            nx, ny = x+dx, y+dy
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx,ny))
    
    brides = []
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1 and not (i==0 and j==0):
                qualities = 0
                for dx,dy in dirs:
                    ni, nj = i+dx, j+dy
                    if 0 <= ni < n and 0 <= nj < m and matrix[ni][nj] != 0:
                        if not (ni==0 and nj==0):
                            qualities += 1
                if qualities > 0:
                    brides.append((qualities, dist[i][j], i+1, j+1))
    
    if not brides:
        return "No suitable girl found"
    
    max_q = max(b[0] for b in brides)
    candidates = [b for b in brides if b[0] == max_q]
    min_d = min(b[1] for b in candidates)
    final = [b for b in candidates if b[1] == min_d]
    
    if len(final) > 1:
        return "Polygamy not allowed"
    
    q, d, r, c = final[0]
    return f"{r}:{c}:{q}"

n,m = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]
print(bride_hunt(matrix))

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    max_consecutive = 1
    current_consecutive = 1
    
    for i in range(1, n):
        if a[i] == a[i-1]:
            current_consecutive += 1
        else:
            max_consecutive = max(max_consecutive, current_consecutive)
            current_consecutive = 1
    
    max_consecutive = max(max_consecutive, current_consecutive)
    print(max_consecutive)

def solve():
    T = int(input())
    for _ in range(T):
        N, E, H, A, B, C = map(int, input().split())
        min_cost = float('inf')
        found = False

        # Try all possible numbers of cakes (x)
        for x in range(0, N+1):
            eggs_left = E - x
            choco_left = H - x
            
            if eggs_left < 0 or choco_left < 0:
                continue

            # Maximum omelettes we can make with remaining eggs
            max_omelette = eggs_left // 2
            # Maximum milkshakes with remaining chocolates
            max_milkshake = choco_left // 3

            # The rest should be covered by omelettes and milkshakes
            total_left = N - x

            # y = number of omelettes, z = number of milkshakes
            # Try to assign as much as possible according to cost
            y = min(max_omelette, total_left)
            z = total_left - y

            if z <= max_milkshake:
                found = True
                total_cost = x * C + y * A + z * B
                min_cost = min(min_cost, total_cost)

        print(min_cost if found else -1)

if __name__ == "__main__":
    solve()

def min_time(X, S, R, t, segments):
    all_segments = []
    last = 0

    # Add segments including gaps between walkways
    for start, end, w in segments:
        if start > last:
            all_segments.append((last, start, 0))
        all_segments.append((start, end, w))
        last = end
    if last < X:
        all_segments.append((last, X, 0))

    detailed_segments = []
    for start, end, w in all_segments:
        length = end - start
        total_speed = S + w
        detailed_segments.append((total_speed, length, w))

    # Sort by total_speed ascending to use running time optimally
    detailed_segments.sort()

    total_time = 0.0
    remaining_run_time = t

    for total_speed, length, w in detailed_segments:
        if remaining_run_time > 0:
            run_speed = R + w
            time_to_run_entire_segment = length / run_speed
            max_distance_run = remaining_run_time * run_speed

            if max_distance_run >= length:
                total_time += time_to_run_entire_segment
                remaining_run_time -= time_to_run_entire_segment
            else:
                distance_run = max_distance_run
                distance_walk = length - distance_run
                total_time += remaining_run_time
                total_time += distance_walk / total_speed
                remaining_run_time = 0
        else:
            total_time += length / total_speed

    return round(total_time, 3)


def main():
    # Read first line of inputs
    X, S, R, t, N = map(int, input("Enter X S R t N: ").split())

    segments = []
    print("Enter the segments (Bi Ei Wi):")
    for _ in range(N):
        Bi, Ei, Wi = map(int, input().split())
        segments.append((Bi, Ei, Wi))

    result = min_time(X, S, R, t, segments)
    print(f"{result:.3f}")


if __name__ == "__main__":
    main()

T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    
    magical_count = 0

    for start in range(N):
        visited = set()
        pos = start

        while True:
            if pos in visited:
                # If we visit the same box again before returning to start, not magical
                break
            visited.add(pos)
            pos = (pos + A[pos] + 1) % N  # Move: eat current box, skip A[pos], land next

            if pos == start:
                # Came back to start — it's magical!
                magical_count += 1
                break

    print(magical_count)

def solve(arr):
    n = len(arr)
    if n == 0:
        return -1
    
    prefix_or = [0] * (n + 1)
    for i in range(n):
        prefix_or[i + 1] = prefix_or[i] | arr[i]
    
    suffix_or = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_or[i] = suffix_or[i + 1] | arr[i]
    
    total_or = prefix_or[n]
    
    if total_or == 0:
        return n
    
    max_length = -1
    
    for i in range(n):
        subarray_or = 0
        for j in range(i, n):
            subarray_or |= arr[j]
            remaining_or = prefix_or[i] | suffix_or[j + 1]
            
            if subarray_or == remaining_or:
                max_length = max(max_length, j - i + 1)
    
    return max_length

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    print(solve(arr))

def calculate_max_esf(magnitudes, signs, n)

if isinstance(magnitudes, str)
magnitudes = [int(x) for x in magnitudes]

net_field = o
for i in range(n)
if signs[i] =
net_field += magnitudes[i]
elif signs[i] = 'N'
net_field -= magnitudes[i]

esf = (net_field) * 100
return esf

mag = list(map(int,input().split()))
signs = input()
n = int(input())
print(calculate_max_esf (mag, signs,n))

def factorial(n):
    if n <= 1:
        return 1
    result = 1
    for i in range(2, n + 1):
        result = (result * i) % 10000
    return result

def combination(n, r):
    if r > n or r < 0:
        return 0
    if r == 0 or r == n:
        return 1
    
    # Use the formula C(n,r) = n! / (r! * (n-r)!)
    # To avoid overflow, we calculate it step by step
    result = 1
    for i in range(min(r, n - r)):
        result = result * (n - i) // (i + 1)
    return result % 10000

def solve():
    n = int(input())
    k = int(input())
    
    total = 0
    # Sum of C(n,1) + C(n,2) + ... + C(n,min(k,n))
    for i in range(1, min(k, n) + 1):
        total = (total + combination(n, i)) % 10000
    
    return total

result = solve()
print(result)

from sys import stdin

T = int(input())  # Number of test cases

for _ in range(T):
    N, K = map(int, input().split())
    S = list(input())
    
    for _ in range(min(K, N)):
        prev = S.copy()
        new_S = prev.copy()
        changed = False

        for i in range(N):
            if prev[i] == '1':
                new_S[i] = '0'
                if i - 1 >= 0 and prev[i - 1] == '0':
                    new_S[i - 1] = '1'
                    changed = True
                if i + 1 < N and prev[i + 1] == '0':
                    new_S[i + 1] = '1'
                    changed = True

        # If no change happened, break early
        if prev == new_S:
            break

        S = new_S

    print(''.join(S))

# Read number of soldiers
n = int(input())

# Formula to find the soldier between Abraham and Daryl (clockwise)
pos = (n - 2) % n + 1  # 1-indexed position

if pos == 2:
    print("1")
else:
    print(pos)

import heapq

def min_time_to_collect_all_candies(boxes):
    # Use a min-heap to always combine the smallest two boxes
    heapq.heapify(boxes)
    total_time = 0

    while len(boxes) > 1:
        first = heapq.heappop(boxes)
        second = heapq.heappop(boxes)
        time_taken = first + second
        total_time += time_taken
        heapq.heappush(boxes, time_taken)

    return total_time

# Read input
t = int(input())
for _ in range(t):
    n = int(input())
    boxes = list(map(int, input().split()))
    result = min_time_to_collect_all_candies(boxes)
    print(result)