aboutsummaryrefslogtreecommitdiff
path: root/other/new_21_game.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/new_21_game.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/new_21_game.cpp')
-rw-r--r--other/new_21_game.cpp40
1 files changed, 40 insertions, 0 deletions
diff --git a/other/new_21_game.cpp b/other/new_21_game.cpp
new file mode 100644
index 0000000..dc21609
--- /dev/null
+++ b/other/new_21_game.cpp
@@ -0,0 +1,40 @@
+// 837. New 21 Game
+#include "leetcode.h"
+
+/*
+ * alice plays the following game, loosely based on the card game "21". alice
+ * starts with 0 points and draws numbers while she has less than 'k' points.
+ * during each draw, she gains an integer number of points randomly from range
+ * '[1, max_pts]', where 'max_pts' is an integer. each draw is independent and
+ * the outcomes have equal posibilities. alice stops drawing numbers when she
+ * gets 'k' or more points. return the probability that alice has 'n' or fewer
+ * points. answers within 10^-5 of the actual answer are considered accepted
+ */
+
+class Solution {
+public:
+ double new21Game(int n, int k, int max_pts) {
+ if (!k || n >= k + max_pts)
+ return 1.0;
+ vector<double> dp(n + 1);
+ dp[0] = 1.0;
+ double sum = 1.0, ans = 0.0;
+ for (int i = 1; i <= n; ++i) {
+ dp[i] = sum / max_pts;
+ if (i < k)
+ sum += dp[i];
+ else
+ ans += dp[i];
+ if (i - max_pts >= 0)
+ sum -= dp[i - max_pts];
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%f\n", obj.new21Game(10, 1, 10)); // expect: 1.00000
+ printf("%f\n", obj.new21Game(6, 1, 10)); // expect: 0.60000
+ printf("%f\n", obj.new21Game(21, 17, 10)); // expect: 0.73278
+}