Algorithm
Problem link- https://www.spoj.com/problems/RPLC/
RPLC - Coke madness
David likes coke, lets say he likes it a lot... One day he was walking by a narrow street when he sees a lot of bottles of cokes, from different brands, he wants to drink it all, but he noticed that one brand gives him power, the other brand weaken him, now, he can wait and regain more energy, but he don't want to do that, he will wait at the beginning and, when he has the sufficient energy he will drink all the cokes in the street.
Please, help him find when he will be in the perfect moment to drink all the cokes.
Input
Will start with an integer T denoting the number of test cases, then, T lines will follow, for each test case, there will be an integer N, then, in the next line will be N integers, this will be the number of cokes, and the values of the cokes in the floor (the positive one gives energy, the negative ones will take his energy).
Output
Each test case will output the string “Scenario #i: “ where i is the number of test case analyzed, followed by the minimum energy required by David to pass the street.
Example
Input: 2 5 4 -10 4 4 4 5 1 2 3 4 5 Output: Scenario #1: 7 Scenario #2: 1
“The life of David should never reach 0 or less”
Constraints
1 <= N <= 1000000
-10000000 <= Ni <= 10000000
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e6+5;
int n, A[MAXN];
bool is_poss(ll mid){
ll curr = mid;
for(int i = 0;i < n; i++){
curr += A[i];
if(curr <= 0)
return false;
}
return true;
}
int main(){
io;
int t;
cin >> t;
int tc = 1;
while(t--){
cout << "Scenario #" << tc << ": ";
tc++;
cin >> n;
for(int i = 0;i < n; i++)
cin >> A[i];
ll lo = 0, hi = (ll)1e13;
while(hi-lo > 1){
ll mid = (lo+hi)/2;
if(is_poss(mid))
hi = mid;
else
lo = mid;
}
cout << hi << endl;
}
return 0;
}Input
5
4 -10 4 4 4
5
1 2 3 4 5
Output
Scenario #2: 1
Demonstration
SPOJ Solution-Coke madness-Solution in C, C++, Java, Python