# Game of Two Stacks

# Game of Two Stacks

vkreddy21 + 0 comments My c++ solution

#include <bits/stdc++.h> using namespace std; int main(){ int g; cin >> g; for(int a0 = 0; a0 < g; a0++){ int n; int m; int x; cin >> n >> m >> x; vector<int> a(n); for(int a_i = 0; a_i <n; a_i++){ cin >> a[a_i]; } vector<int> b(m); for(int b_i =0; b_i <m; b_i++){ cin >> b[b_i]; } int sum=0,count=0,temp=0,i=0,j=0; while(i<n && sum+a[i]<=x){ //considering only first stack and calculating count sum+=a[i]; i++; } count=i; while(j<m && i>=0){ //now adding one element of second stack at a time and subtracting the top element of first stack and calculating the count sum+=b[j]; j++; while(sum>x && i>0){ i--; sum-=a[i]; } if(sum<=x && i+j>count) count=i+j; } cout<<count<<endl; } return 0; }

bawejakunal + 0 comments A greedy strategy to pick the smaller element from the top elements of A and B is giving me wrong answer for many test cases. Any hints for that ?

Lundii + 0 comments I think this question should be modified, as the operations performed on a stack are pop, push or peek. By the way, Nick can only see what's at the top of the stack and would definitely go for the smallest (greedy algorithm). Thanks

kewltek + 0 comments Since this was supposed to be a stack problem I was also annoyed by other solutions using arrays. So here is my Python solution using the python stack operations pop, append and the equiv of peek is lst[-1]. Notice I also reversed the original data since Python pop is O(n) if you pop or delete the first element.

#!/bin/python3 import sys g = int(input().strip()) for a0 in range(g): n,m,x = input().strip().split(' ') n,m,x = [int(n),int(m),int(x)] a = list(map(int, reversed(input().strip().split(' ')))) b = list(map(int, reversed(input().strip().split(' ')))) total = 0 atmp = [] for i in range(n): val = a.pop() if total + val > x: break total += val atmp.append(val) max_count = len(atmp) cur_count = max_count while m: if total + b[-1] <= x: total += b.pop() m -= 1 cur_count += 1 if cur_count > max_count: max_count = cur_count continue if not len(atmp): break aval = atmp.pop() total -= aval cur_count -= 1 print (max_count)

lgsports41 + 0 comments I just realized the algorism which I thought first. Actually, I did not believe that does not work. Even thought I read many code in order to solve my mystery , I could not understand.. I found so many people tried to solve the problem just like me.. If anyone try to poll out smaller number between 2 stacks,then he or she will fall into a trap.

ex: wrong Algorism < pop() the smaller top of the 2 stacks>

max sum : 5 Stack A : 3 1 1 1 1 Stack B : 2 2 7 0

Top is from the begining. Stack A : 3 1 1 1 1

Stack B : 2 2 7 0

`^ smaller top (2<3) So stack B.pop()`

maxCnt : 1 sum : 2

Stack A : 3 1 1 1 1

Stack B : 2 7 0

`^ smaller top (2<3) So stack B.pop()`

maxCnt : 2 sum : 4

and then? It is over because maxSum is 5 . There is no more operation. So maxCnt is 2...

**Stack A : 3 1 1 1 1**Stack B : 2 2 7 0However, look at stack A only. then we can pop() 3times. 3, 1, 1 (maxSum = 5 ) then maxCnt is 3.

That is why we can not use only smaller top value.

I am not sure but I hope it could be helpful for someone thought like me.

asdasdasd

Sort 287 Discussions, By:

Please Login in order to post a comment