aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--can_i_win.c48
-rw-r--r--can_i_win.py48
2 files changed, 96 insertions, 0 deletions
diff --git a/can_i_win.c b/can_i_win.c
new file mode 100644
index 0000000..a13c90e
--- /dev/null
+++ b/can_i_win.c
@@ -0,0 +1,48 @@
+// 464. Can I Win
+#include "leetcode.h"
+
+/*
+ * in the 100 game two players take turns adding, to a running total, any
+ * integer from 1 to 10. the player who first causes the running total to reach
+ * or exceed 100 wins. what if we change the same so that players cannot re-use
+ * integers? for example, two players might take turns drawing from a common
+ * pool of numbers from 1 to 15 without replacement until they reach a total >=
+ * 100. given two integers 'maxChoosableInteger' nad 'desiredTotal', return true
+ * if the first player to move can force a win, otherwise, return false. assume
+ * both players play optimally.
+ */
+
+static int mem[1 << 20] = {};
+
+bool dfs(int maxChoosableInteger, int desiredTotal, int k) {
+ if (mem[k])
+ return mem[k] > 0;
+ if (desiredTotal <= 0)
+ return false;
+ for (int i = 0; i < maxChoosableInteger; ++i)
+ if (!(k & (1 << i)) &
+ !dfs(maxChoosableInteger, desiredTotal - i - 1, k | (1 << i))) {
+ mem[k] = 1;
+ return true;
+ }
+ mem[k] = -1;
+ return false;
+}
+
+bool canIWin(int maxChoosableInteger, int desiredTotal) {
+ int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
+ if (desiredTotal < 2)
+ return true;
+ else if (sum < desiredTotal)
+ return false;
+ else if (sum == desiredTotal)
+ return maxChoosableInteger % 2;
+ else
+ return dfs(maxChoosableInteger, desiredTotal, 0);
+}
+
+int main() {
+ printf("%d\n", canIWin(10, 11)); // expect: 0
+ printf("%d\n", canIWin(10, 0)); // expect: 1
+ printf("%d\n", canIWin(10, 1)); // expect: 1
+}
diff --git a/can_i_win.py b/can_i_win.py
new file mode 100644
index 0000000..916ffca
--- /dev/null
+++ b/can_i_win.py
@@ -0,0 +1,48 @@
+# 464. Can I Win
+
+"""
+in the 100 game two players take turns adding, to a running total, any
+integer from 1 to 10. the player who first causes the running total to reach
+or exceed 100 wins. what if we change the same so that players cannot re-use
+integers? for example, two players might take turns drawing from a common
+pool of numbers from 1 to 15 without replacement until they reach a total >=
+100. given two integers 'maxChoosableInteger' nad 'desiredTotal', return true
+if the first player to move can force a win, otherwise, return false. assume
+both players play optimally.
+"""
+
+
+class Solution(object):
+ def canIWin(self, maxChoosableInteger, desiredTotal):
+ """
+ :type maxChoosableInteger: int
+ :type desiredTotal: int
+ :rtype: bool
+ """
+
+ def get_sum(num):
+ i, curr = 1, 0
+ while i <= 20 and num:
+ if num & 1:
+ curr += i
+ i += 1
+ i >>= 1
+ return curr
+
+ def dfs(pick, player):
+ curr = get_sum(pick)
+ for i in range(maxChoosableInteger):
+ if pick & (1 << i):
+ continue
+ if curr + i + 1 >= desiredTotal or not dfs(pick | (1 << i), player ^ 1):
+ return True
+ return False
+
+ return dfs(0, 0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.canIWin(maxChoosableInteger=10, desiredTotal=11))
+ print(obj.canIWin(maxChoosableInteger=10, desiredTotal=0))
+ print(obj.canIWin(maxChoosableInteger=10, desiredTotal=1))