-
Notifications
You must be signed in to change notification settings - Fork 118
/
808. Soup Servings.cpp
141 lines (124 loc) · 4.47 KB
/
808. Soup Servings.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//Runtime Error: stack-overflow on address
//20 / 41 test cases passed.
class Solution {
public:
vector<int> serveAs;
unordered_map<string, vector<double>> memo;
vector<double> soupServings(int NA, int NB){
/*
prob[0]: A will be empty first
prob[1]: A and B become empty at the same time
*/
string key = to_string(NA) + "_" + to_string(NB);
if(memo.find(key) != memo.end()){
return memo[key];
}
vector<double> prob(2);
for(int serveA : serveAs){
int serveB = 100 - serveA;
if(NA <= serveA && NB <= serveB){
prob[1] += 0.25;
}else if(NA <= serveA){
prob[0] += 0.25;
}else if(NB <= serveB){
//pass
}else{
vector<double> subprob = soupServings(NA-serveA, NB-serveB);
prob[0] += 0.25 * subprob[0];
prob[1] += 0.25 * subprob[1];
}
}
return memo[key] = prob;
};
double soupServings(int N) {
serveAs = {100, 75, 50, 25};
vector<double> prob = soupServings(N, N);
return prob[0] + prob[1] * 0.5;
}
};
//return 1 when N >= 4800
/*
Answers within 10^-5 of the true value will be accepted as correct.
When N = 4800, the result = 0.999994994426
*/
//https://leetcode.com/problems/soup-servings/discuss/121711/C%2B%2BJavaPython-When-N-greater-4800-just-return-1
//Runtime: 32 ms, faster than 15.42% of C++ online submissions for Soup Servings.
//Memory Usage: 8.9 MB, less than 41.48% of C++ online submissions for Soup Servings.
class Solution {
public:
vector<int> serveAs;
unordered_map<string, vector<double>> memo;
vector<double> soupServings(int NA, int NB){
/*
prob[0]: A will be empty first
prob[1]: A and B become empty at the same time
*/
if(NA >= 4800) return {1.0, 0.0};
string key = to_string(NA) + "_" + to_string(NB);
if(memo.find(key) != memo.end()){
return memo[key];
}
vector<double> prob(2);
for(int serveA : serveAs){
int serveB = 100 - serveA;
if(NA <= serveA && NB <= serveB){
prob[1] += 0.25;
}else if(NA <= serveA){
prob[0] += 0.25;
}else if(NB <= serveB){
//pass
}else{
vector<double> subprob = soupServings(NA-serveA, NB-serveB);
prob[0] += 0.25 * subprob[0];
prob[1] += 0.25 * subprob[1];
}
}
return memo[key] = prob;
};
double soupServings(int N) {
serveAs = {100, 75, 50, 25};
vector<double> prob = soupServings(N, N);
return prob[0] + prob[1] * 0.5;
}
};
//conversion
//Runtime: 8 ms, faster than 52.57% of C++ online submissions for Soup Servings.
//Memory Usage: 14.5 MB, less than 13.63% of C++ online submissions for Soup Servings.
class Solution {
public:
vector<vector<double>> memo;
double f(int NA, int NB){
if(NA <= 0 && NB <= 0) return 0.5;
if(NA <= 0) return 1.0;
if(NB <= 0) return 0.0;
if(memo[NA][NB] > 0) return memo[NA][NB];
return memo[NA][NB] = 0.25*(f(NA-4,NB)+f(NA-3,NB-1)+f(NA-2,NB-2)+f(NA-1,NB-3));
};
double soupServings(int N) {
if(N > 4800) return 1.0;
//200 because 4800/25+1=193, it's around 200
memo = vector<vector<double>>(200, vector<double>(200));
//conversion from 25's multiple to the number of spoons
return f(ceil((double)N/25), ceil((double)N/25));
}
};
//conversion, using array
//https://leetcode.com/problems/soup-servings/discuss/121711/C%2B%2BJavaPython-When-N-greater-4800-just-return-1
//Runtime: 4 ms, faster than 69.96% of C++ online submissions for Soup Servings.
//Memory Usage: 6.2 MB, less than 95.45% of C++ online submissions for Soup Servings.
class Solution {
public:
double memo[200][200];
double f(int NA, int NB){
if(NA <= 0 && NB <= 0) return 0.5;
if(NA <= 0) return 1.0;
if(NB <= 0) return 0.0;
if(memo[NA][NB] > 0) return memo[NA][NB];
return memo[NA][NB] = 0.25*(f(NA-4,NB)+f(NA-3,NB-1)+f(NA-2,NB-2)+f(NA-1,NB-3));
};
double soupServings(int N) {
if(N > 4800) return 1.0;
//conversion from 25's multiple to the number of spoons
return f(ceil((double)N/25), ceil((double)N/25));
}
};