Kaidul

Quan

Jan 11th, 2015
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <cstdio>
  2. #include <fstream>
  3. #include <cstring>
  4. #include <set>
  5. #include <unordered_map>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. #define MAX 100001
  10. #define MIN 101
  11. bool dropped[MIN];
  12. int N;
  13. vector <int> missings;
  14. int dp[MIN][MIN * MIN];
  15.  
  16. int solve(int i, int amount) {
  17.     if(i > N) {
  18.         if(amount == 0) return 1;
  19.         return 0;
  20.     }
  21.     if(dp[i][amount] != -1) return dp[i][amount];
  22.     int ret1 = 0, ret2 = 0;
  23.     if(!dropped[i]) {
  24.         if(amount - i >= 0) ret1 = solve(i + 1, amount - i);
  25.     }
  26.     ret2 = solve(i + 1, amount);
  27.     return dp[i][amount] = ret1 | ret2;
  28. }
  29.  
  30. int main(void) {
  31. #ifndef ONLINE_JUDGE
  32.     freopen("input.txt", "r", stdin);
  33. #endif // ONLINE_JUDGE
  34.     int T;
  35.     scanf("%d", &T);
  36.     int K, indx;
  37.     while(T--) {
  38.         memset(dp, -1, sizeof dp);
  39.         scanf("%d %d", &N, &K);
  40.         for(int i = 0; i < K; ++i) {
  41.             scanf("%d", &indx);
  42.             dropped[indx] = true;
  43.             missings.push_back(indx);
  44.         }
  45.         bool found = false;
  46.         for(int i = 0; i < missings.size(); ++i) {
  47.             int ret = solve(1, missings[i]);
  48.             if(!ret) {
  49.                 if(missings[i] & 1) printf("Chef\n");
  50.                 else printf("Mom\n");
  51.                 found = true;
  52.                 break;
  53.             }
  54.         }
  55.         if(!found) {
  56.             for(int i = N + 1;; ++i) {
  57.                 int ret = solve(1, i);
  58.                 if(!ret) {
  59.                     if(i & 1) printf("Chef\n");
  60.                     else printf("Mom\n");
  61.                     break;
  62.                 }
  63.             }
  64.         }
  65.         missings.clear();
  66.         memset(dropped, false, sizeof dropped);
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment