Question

C Programming Language

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 problem can be solved using greedy approach. Answer can be calculating by finding the minimum sum.
If the sum > 0 , then no need to start with any minimum life , otherwise starting life will be -minSum+1.

Here is the C code for the problem:

#include<stdio.h>

long calculateMin(long a ,long b){
        if(a<=b)
                return a;
        return b;
}
int main(){
        int t;
        int tc =0;
        scanf("%d",&t);
        while(t--){
                tc++;
                int n;
                scanf("%d",&n);
                long minSum = 100000008;
                long sm = 0;
                int i= 0 ;
                for(i;i<n;i++){
                        int num;
                        scanf("%d",&num);
                        sm+=(long)num;
                        minSum = calculateMin(minSum,sm);
                }
                if(minSum>0){
                        printf("Case #%d: 0\n",tc);
                }else{
                        long ans = -minSum+1;
                        printf("Case #%d: %ld\n",tc,ans );
                }
        }
}

Here is the screenshot of Input and Output: