Question

Problem Title : Magical Cave

Lili, a great magician, has a mission to enter a cave to get treasure inside. The cave only has 1 path without branches. But the cave is not safe because there are some traps inside that can reduce Lili’s life points. But in addition to traps, the cave also has potions that can increase Lili’s life points. Before entering the cave, Lili casts magic that can reveal all the traps and potions inside the cave. But before entering the cave, Lili must prepare her life points first because in the cave because Lili cannot use her magic to add life points or destroy the traps. What is the minimum life point that Lili must prepare so that her life point is always positive during the trip inside the cave.

Note: if Lili's point drops to 0 or negative before entering and during the trip inside the cave, then Lili is declared dead.

Format Input

There are T test cases. Each testcase contains an integer N which represents the length of the cave. On the next line there are N numbers represents the value of trap and potion. Traps are marked with numbers that are negative and potions are marked with numbers that are positive.

Format Output

Output T line with format “Case #X: ”, where X represents the testcase number and Y represents the initial life points that Lili has to prepare.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 5000
• −10⁸ ≤ Ai ≤ 10⁸, which Ai is the value of each traps and potions.

Sample Input & Output (standard input & output)

2
5
1 2 -3 4 -5
Case #1: 2
5
-1 -1 -1 -2 9
Case #2: 6

Explanation
In case 1, the minimum life points that Lili must prepare is 2. With a simulation like the following.
At position 1, Lili’s life point increased by 1 to 3.
At position 2, Lili’s life point increased by 2 to 5.
At position 3, Lili’s life point is reduced by 3 to 2.
At position 4, Lili’s life point increased to 4 to 6.
At position 5, Lili’s life point is reduced by 5 to 1.
In each position Lili’s life points are Positive so the answer is Valid. if the initial life
prepared by Lili is 1, then Lili will die in fifth position with a life point of 0.

Answer 1

The solution will be find by adding all the negative and positive numbers, if the sum>0 the minimum life is 0 otherwise minimum life is -sum+1

code:

#include<stdio.h>
int main(){
        int T;
        int testCase =0;
        scanf("%d",&T);
        while(T--){
                testCase++;
                int n;
                scanf("%d",&n);
                int min = 100000008;
                int sum = 0;
                int i;
                for(i=0;i<n;i++){
                        int no;
                        scanf("%d",&no);
                        sum+=(int)no;
                        min = (min<=sum)?min:sum;
                }
                if(min>0){
                        printf("Case #%d: 0\n",testCase);
                }else{
                        printf("Case #%d: %d\n",testCase,-min+1 );
                }
        }
}

Sample Output: