Question

In: Computer Science

Lili, a great magician, has a mission to enter a cave to get treasure inside. The...

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 • −108 ≤ Ai ≤ 10
8
, which
A
i
is the value of each traps and potions.
Sample Input (standard input) 25
1 2 -3 4 -5 5
-1 -1 -1 -2 9
Sample Output (standard output)
Case #1: 2
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.

Please answer it in C language , thx

Solutions

Expert Solution

code in c with explanation in comments (code to copy)

#include <stdio.h>
#include <stdlib.h>

int main()
{
        //declare array to store path values
        int arr[5000];
        //declare variable to enter number of test cases
        int test_cases;
        //get number of test cases
        scanf("%d", &test_cases);
        //loop through all test cases
        for(int k=1;k<=test_cases;k++){
                //declare n for array length
                int n;
                //take input for n from user
                scanf("%d", &n);
                //take input for traps and potion into our array
                for(int i=0;i<n;i++){
                        scanf("%d", &arr[i]);
                }
                //we start with 0 health and calculate health after each path
                //we would have to start with 1 + the minimum value of our health in the entire path

                //x keeps track of current health
                int x=0;
                //c_min keeps track of the minimum health in the entire duration
                int x_min=0;
                //loop through all traps and potion
                for(int i=0;i<n;i++){
                        x+=arr[i];
                        //if current health is lower than minimum then update minimum value
                        if(x<x_min){
                                x_min=x;
                        }
                }
                //decalre variable for answer
                int required_health;
                //if health is always positive, we dont need initial health
                if(x_min>0){
                        required_health = x_min;
                }else{
                        required_health = (x_min*-1) + 1;// this also takes care of situation where x_min=0
                }
                printf("Case #%d: %d\n", k, required_health);
        }
}

code screenshot

Console Input/Output Screenshot

Let me know in the comments if you have any doubts.
Do leave a thumbs up if this was helpful.


Related Solutions

Problem Title : Magical Cave Lili, a great magician, has a mission to enter a cave...
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....
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT