aboutsummaryrefslogtreecommitdiff
path: root/other/stone_game3.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/stone_game3.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/stone_game3.cpp')
-rw-r--r--other/stone_game3.cpp46
1 files changed, 46 insertions, 0 deletions
diff --git a/other/stone_game3.cpp b/other/stone_game3.cpp
new file mode 100644
index 0000000..947d65f
--- /dev/null
+++ b/other/stone_game3.cpp
@@ -0,0 +1,46 @@
+// 1406. Stone Game III
+#include <stdio.h>
+
+/*
+ * alice and bob continue their games with piles of stones. there are several
+ * stones arranged in a row, and each stone has an associated value which is an
+ * integer given in the array 'stone_value'. alice and bob take turns with alice
+ * starting first. on each player's turn, that player can take 1,2, or 3 stones
+ * from the first remaining stones in row. the score of each player is the sum
+ * of the values of the stones taken the score of each player is initially zero.
+ * the objective of the game is to end with the highest score, and the winner is
+ * the player with the highest score and there could be a tie. the game
+ * continues until all the stones have been taken. assume alice and bob play
+ * optimally. return "Alice", "Bob", or "Tie" accordingly
+ */
+
+int min(int a, int b, int c) {
+ if (a <= b && a <= c)
+ return a;
+ if (b <= a && b <= c)
+ return b;
+ return c;
+}
+
+char *stoneGameIII(int *stone_value, int stone_value_size) {
+ int dp[50005] = {0}, sum = 0;
+ for (int i = stone_value_size - 1; i >= 0; --i) {
+ sum += stone_value[i];
+ dp[i] = sum - min(dp[i + 1], dp[i + 2], dp[i + 3]);
+ }
+ if (dp[0] * 2 == sum)
+ return "Tie";
+ if (dp[0] * 2 > sum)
+ return "Alice";
+ else
+ return "Bob";
+}
+
+int main() {
+ int sv1[] = {1, 2, 3, 7};
+ int sv2[] = {1, 2, 3, -9};
+ int sv3[] = {1, 2, 3, 6};
+ printf("%s\n", stoneGameIII(sv1, 4)); // expect: Bob
+ printf("%s\n", stoneGameIII(sv2, 4)); // expect: Alice
+ printf("%s\n", stoneGameIII(sv3, 4)); // expect: Tie
+}