aboutsummaryrefslogtreecommitdiff
path: root/stone_game3.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'stone_game3.cpp')
-rw-r--r--stone_game3.cpp46
1 files changed, 0 insertions, 46 deletions
diff --git a/stone_game3.cpp b/stone_game3.cpp
deleted file mode 100644
index 947d65f..0000000
--- a/stone_game3.cpp
+++ /dev/null
@@ -1,46 +0,0 @@
-// 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
-}