In: Computer Science
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
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.