Game of two stacks| Stack
TASK
Alexa has two stacks of non-negative integers, stack a[n] and stack b[m] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:
- In each move, Nick can remove one integer from the top of either stack a or stack b.
- Nick keeps a running sum of the integers he removes from the two stacks.
- Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer given at the beginning of the game.
- Nick's final score is the total number of integers he has removed from the two stacks.
Given a, b, and maxSum for g games, find the maximum possible score Nick can achieve.
Example
a= [1,2,3,4,5]
b= [6,7,8,9]
The maximum number of values Nick can remove is . There are two sets of choices with this result.
- Remove 1,2,3,4 from a with a sum of 10.
- Remove 1,2,3 from a and 6 from b with a sum of 12.
Function Description
Complete the twoStacks function in the editor below.
twoStacks has the following parameters: - int maxSum: the maximum allowed sum
- int a[n]: the first stack
- int b[m]: the second stack
Returns
- int: the maximum number of selections Nick can make
Input Format
The first line contains an integer, (the number of games). The subsequent lines describe each game in the following format:
- The first line contains three space-separated integers describing the respective values of (the number of integers in stack a), m (the number of integers in stack b), and maxSum(the number that the sum of the integers removed from the two stacks cannot exceed).
- The second line contains n space-separated integers, the respective values of a[i].
- The third line contains space-separated integers, the respective values of b[i].
Constraints
1 <= g <= 50
1 <= n, m <= 10 ^ 5
0 <= a[i], b[i] <= 10 ^ 6
1 < maxSum ≤ 109
Subtasks
- for of the maximum score.
Sample Input 0
1
5 4 10
4 2 4 6 1
2 1 8 5
Sample Output 0
4
SOLUTION 1
def twoStacks(maxSum, a, b):
# Write your code here
i = j = s = 0
while i < len(a) and s + a[i] <= maxSum:
s += a[i]
i += 1
n = maxn = i
i -= 1
while j < len(b):
if s + b[j] <= maxSum:
s += b[j]
j += 1
n += 1
maxn = max(maxn, n)
elif i >= 0:
s -= a[i]
i -= 1
n -= 1
else:
break
return maxn
SOLUTION 2
def twoStacks(maxSum, a, b):
i, j, currSum, maxCount = 0, 0, 0, 0
while i<len(a) and currSum + a[i] <= maxSum:
currSum += a[i]
i += 1
if currSum > maxSum:
i -= 1
maxCount = max(maxCount, i)
else:
maxCount = max(maxCount, i)
i -= 1
while j < len(b) and currSum <= maxSum:
currSum += b[j]
j += 1
while currSum > maxSum and i >= 0:
currSum -= a[i]
i -= 1
if currSum <= maxSum:
maxCount = max(maxCount, i + j + 1)
return maxCount
