soup-serving.dart (1833B)
1 //Given a value n where n is the amount of soup of type a and b 2 //return the probability that a will run out first plus half the probability 3 //that a and b run out at the same time. 4 5 //To solve this I used DP, memoization, and recursion. 6 //I recursively called the soupServe function with each possible 7 //service option. Once you reach the bottom it will then return 8 //.5 if a and b = 0 or 1 if only b = 0. Using this we then 9 //add the probabilities of each option together and divide by the options 10 //to get the probabilities. From here we memoize the solution so we do not 11 //need to solve again from the starting point of a = a given number and b = a given number. 12 13 //Note: If the value is greater than 4800 then the probability 14 //of b reaching 0 first is so close to 1 that a double can not be accurate at that 15 //point so instead of running into a stack overflow issue it is best to return 1 16 //even though theoretically it could compute without it presuming the stack depth of your 17 //system is astronomically high. 18 19 //Time: 303ms Beats: 100% 20 //Memory: 143MB Beats: 100% 21 22 23 class Solution { 24 double soupServings(int n) { 25 if(n > 4800){ 26 return 1; 27 } 28 return soupServe(n,n, {}); 29 } 30 double soupServe(int a, int b, Map<String,double> memo){ 31 if(a <= 0 && b <= 0){ 32 return .5; 33 } 34 if(b <= 0){ 35 return 0; 36 } 37 if(a <= 0){ 38 return 1.0; 39 } 40 String current_str = a.toString() + ' ' + b.toString(); 41 if(memo.containsKey(current_str)){ 42 return (memo[current_str] ?? 0.0); 43 } 44 double prob = 0; 45 prob += soupServe(a - 100 , b, memo); 46 prob += soupServe(a-75, b-25, memo); 47 prob += soupServe(a-50, b-50, memo); 48 prob += soupServe(a-25, b-75, memo); 49 memo[current_str] = prob/4; 50 return prob / 4; 51 } 52 }