In this HackerRank Game of Two Stacks problem, we have two stacks with nonnegative integer values. where index 0 denotes the top of the stack. in each move, we need to remove one integer from the top of either stack a or stack b. after that we need to find the maximum possible integers we removed from the two stacks.
Problem solution in Python programming.
def brute(a,b):
ans = 0
a = [0]+a
b = [0]+b
for i in range(len(a)):
for j in range(len(b)):
sa = sum(a[:i+1])
sb = sum(b[:j+1])
if sa+sb > x:
break
ans = max(ans, i+j)
return ans
def solve(a,b):
total = 0
i = len(a)
ans = i
j = 1
for i in range(len(a)):
total += a[i]
if total > x:
ans = i
break
ans_total = x + 1
total = sum(a[:i])
while (total <= x and i > 0) or j < len(b):
if total < x:
total += b[j - 1]
j += 1
elif total > x:
total -= a[i - 1]
i -= 1
else:
total -= a[i - 1]
i -= 1
total += b[j - 1]
j += 1
if i < 1 and total > x:
break
ans = max(ans, i + j - 2)
ans_total = min(total, ans_total)
return ans if ans_total <= x else ans - 1
for _ in range(int(input())):
n, m, x = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
_sum_a, _sum_b = sum(a), sum(b)
if _sum_a + _sum_b <= x:
print(n+m)
elif n <= 200 and m <= 200:
print(brute(a,b))
else:
ans = solve(a,b) if _sum_a < _sum_b else solve(b,a)
print(ans)Problem solution in Java Programming.
import java.util.*;
public class GameOfTwoStacks {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int g = in.nextInt();
for(int a0 = 0; a0 < g; a0++){
int n = in.nextInt();
int m = in.nextInt();
int x = in.nextInt();
long[] a_sum = new long[n];
a_sum[0] = in.nextLong();
for(int a_i=1; a_i < n; a_i++){
a_sum[a_i] = in.nextLong()+a_sum[a_i-1];
}
long[] b_sum = new long[m];
b_sum[0] = in.nextLong();
for(int b_i=1; b_i < m; b_i++){
b_sum[b_i] = in.nextLong()+b_sum[b_i-1];
}
//game
int ai = a_sum.length-1;
int bi = 0;
int max_score = 0;
int score = 0;
while(ai>=0&&a_sum[ai] > x)
ai--;
if(ai>=0)
while(bi<b_sum.length&&a_sum[ai]+b_sum[bi]<=x)
bi++;
else
while(bi<b_sum.length&&b_sum[bi]<=x)
bi++;
for(ai = ai; ai >= -1; ai--)
{
if(ai>=0)
{
while(bi<b_sum.length&&a_sum[ai]+b_sum[bi]<=x)
bi++;
score = ai+bi+1;
}
else
{
while(bi<b_sum.length&&b_sum[bi]<=x)
bi++;
score = bi;
}
if(score>max_score)
max_score = score;
}
System.out.println(max_score);
}
}
}Problem solution in C++ programming.
#include <cstdio>
using namespace std;
int g,i,j,k,n,m,x,s1,Max,nr,y,s[100004];
int main()
{
scanf ("%d", &g);
for (i=1;i<=g;i++)
{
scanf ("%d %d %d", &n, &m, &x);
s[0]=0;
Max=n;
nr=n;
for (j=1;j<=n;j++)
{
scanf ("%d", &y);
if (s[j-1]<=x)
s[j]=s[j-1]+y;
else if (Max==n)
{
nr=j-2;
Max=j-2;
}
}
if (s[n]>x && Max==n)
{
Max=n-1;
nr=n-1;
}
scanf ("%d", &y);
if (y<=x && Max==0)
Max=1;
for (j=nr;j>=1;j--)
{
if ((s[j]+y)<=x)
{
if ((j+1)>Max)
Max=j+1;
break;
}
nr--;
}
s1=y;
for (j=1;j<=(m-1);j++)
{
scanf ("%d", &y);
if (s1<=x)
{
s1+=y;
if (((j+1)>Max) && (s1<=x))
Max=j+1;
for (k=nr;k>=1;k--)
{
if ((s[k]+s1)<=x)
{
if ((j+k+1)>Max)
Max=j+k+1;
break;
}
nr--;
}
}
}
printf ("%d\n", Max);
}
return 0;
}Problem solution in C programming.
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int g;
scanf("%d",&g);
for(int a0 = 0; a0 < g; a0++){
int n;
int m;
int x;
scanf("%d %d %d",&n,&m,&x);
int *a = malloc(sizeof(int) * n);
for(int a_i = 0; a_i < n; a_i++){
scanf("%d",&a[a_i]);
}
int *b = malloc(sizeof(int) * m);
for(int b_i = 0; b_i < m; b_i++){
scanf("%d",&b[b_i]);
}
// your code goes here
int max = 0;
int sum = 0;
int items = 0;
int apos = 0, bpos = 0;
while (sum <= x && apos < n) {
if (sum + a[apos] > x)
break;
sum += a[apos];
apos++;
items++;
}
while (sum <= x && bpos < m) {
if (sum + b[bpos] > x)
break;
sum += b[bpos];
bpos++;
items++;
}
max = items;
while (1) {
if (apos <= 0)
break;
apos--;
sum -= a[apos];
items--;
while (sum <= x && bpos < m) {
if (sum + b[bpos] > x)
break;
sum += b[bpos];
bpos++;
items++;
}
if (items > max)
max = items;
if (bpos == m)
break;
}
printf ("%d\n", max);
}
return 0;
}Problem solution in JavaScript programming.
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the twoStacks function below.
*/
function twoStacks(x, a, b) {
var ai = 0, bi = 0;
var ret = 0, total = 0, cnt = 0;
while (ai < a.length && total + a[ai] <= x) {
total += a[ai++];
}
while (bi < b.length && total + b[bi] <= x) {
total += b[bi++];
}
ret = ai + bi;
while (true) {
while (ai > 0 && total + b[bi] > x) {
total -= a[ai-1];
ai--;
}
if (total + b[bi] > x || bi >= b.length) break;
total += b[bi++];
ret = Math.max(ret, ai + bi);
}
return ret;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const g = parseInt(readLine(), 10);
for (let gItr = 0; gItr < g; gItr++) {
const nmx = readLine().split(' ');
const n = parseInt(nmx[0], 10);
const m = parseInt(nmx[1], 10);
const x = parseInt(nmx[2], 10);
const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));
const b = readLine().split(' ').map(bTemp => parseInt(bTemp, 10));
let result = twoStacks(x, a, b);
ws.write(result + "\n");
}
ws.end();
}
0 Comments