problem.txt (1539B)
1 - given S (multiset) 2 - positive integer k 3 - mex_k(S) := smallest non-negative integer that doesn't appears at least k times in S 4 5 - given even integer n 6 - positive integer k 7 - n cards 8 - a_i is ith card 9 10 - alice first 11 - takes any one of remaining cards 12 - ends when all cards taken 13 - A := multiset of integers written on alice's cards 14 - B := multiset of integers written on bob's cards 15 - Alice wins iff mex_k(A) != mex_k(B) 16 - determine whether Alice wins if both players play optimally. 17 18 --- 19 20 k = 1 21 S := 2 0 0 1 22 23 Alice takes 0 24 Bob takes 0 25 Alice takes 1 26 Bob takes 2 27 28 Alice wins 29 30 Idea: 31 - do we just take the min value at each step for each person as long as the min value improves our mex? 32 33 0 1 0 1 34 35 Alice takes 0 36 Bob takes 0 37 Alice takes 1 38 Bob takes 1 39 40 Bob wins 41 42 Alice takes 1 43 Bob takes 1 44 Alice takes 0 45 Bob takes 0 46 47 Bob wins 48 49 6 2 50 1 2 0 1 0 0 51 52 Alice takes 0 53 Bob takes 0 54 Alice takes 0 55 56 that's it, alice wins 57 58 k = 2 59 0 0 1 1 2 2 60 61 Alice takes 0 62 Bob takes 0 63 Bob wins 64 65 66 k = 2 67 0 1 1 0 0 2 0 1 68 69 Alice takes 0 70 bob takes 0 71 Alice takes 0 72 bob takes 0 73 74 2 75 76 Alice takes 1 77 Bob takes 1 78 79 Alice takes 1 80 Bob takes 2 81 82 Alice wins 83 84 --- 85 86 idea: 87 88 do we always just take the smallest values? 89 90 it seems like there might be a case where we wouldn't 91 92 k = 1 93 000000000000000000000000000000000000000000000000000000000000000000001 94 95 alice should take 1 96 bob would then have to take 0 97 98 alice takes 0 99 then trade back and forth taking 1's 100 101 alice wins 102 103 if alice takes 0 104 bob takes 1 105 then they trade I guess alice still wins here because bob has a largest mex