Chef and A Large Permutation

• Problem Description

  
  Today is Chef's birthday. His mom gifted him a truly lovable gift, a permutation of first N positive integers.
  
  She placed the permutation on a very long table in front of Chef and left it for him to play with it. But as there was a lot of people coming and wishing him. It was interfering with his game which made him very angry and he banged the table very hard due to which K numbers from the permutation fell down and went missing.
  
  Seeing her son's gift being spoilt, his mom became very sad. Chef didn't want his mom to be sad as he loves her the most. So to make her happy, he decided to play a game with her with the remaining N - K numbers on the table. Chef wants his mom to win all the games.
  
  Chef and his mom play alternatively and optimally. In Xth move, a player can choose some numbers out of all the numbers available on the table such that chosen numbers sum up to X. After the move, Chosen numbers are placed back on the table.The player who is not able to make a move loses.
  
  Now, Chef has to decide who should move first so that his Mom wins the game.
  
  As Chef is a small child, he needs your help to decide who should move first. Please help him, he has promised to share his birthday cake with you :)
  
  Input
  First Line of input contains a single integer T denoting the number of test cases.
  First line of each test case contains two space separated integers N and K denoting the size of
  permutation and number of numbers fall down from the table.
  Next line of each test case contains K space separated integers denoting the values of missing numbers.
  
  Output
  For each test case, print "Chef" if chef should move first otherwise print "Mom" (without quotes).
  
  Explanation
  For test case 1.
  
  Mom can choose {1} to make 1.
  Chef can choose {2} to make 2.
  Mom can choose {1,2} to make 3.
  Chef can choose {4} to make 4.
  Mom can choose {1,4} to make 5.
  Chef can choose {2,4} to make 6.
  Mom can choose {1,2,4} to make 7.
  Chef cannot make 8 out of the numbers on the table.
  So,Chef loses and Mom wins.

• CODING ARENA

• #include<stdio.h>

  
  

  long long x[1000000];

  
  

  void quicksort(int first,int last){

      int pivot,j,temp,i;

  
  

       if(first<last){

           pivot=first;

           i=first;

           j=last;

  
  

           while(i<j){

               while(x[i]<=x[pivot]&&i<last)

                   i++;

               while(x[j]>x[pivot])

                   j--;

               if(i<j){

                   temp=x[i];

                    x[i]=x[j];

                    x[j]=temp;

               }

           }

  
  

           temp=x[pivot];

           x[pivot]=x[j];

           x[j]=temp;

           quicksort(first,j-1);

           quicksort(j+1,last);

  
  

      }

  }

  
  

  int main()

  {

  
  

      long long t,n,k,i;

      long long rst,sum;

      scanf("%lld",&t);

  
  

      while(t--)

      {

          scanf("%lld%lld",&n,&k);

          rst=0;

          sum=0;

  
  

          for(i=0;i<k;i++)

          {

              scanf("%lld",&x[i]);

          }

  
  

  
  

          quicksort(0,k-1);

  
  

  /*        for(i=0;i<k;i++)

          {

              printf("%lld ",x[i]);

          }

  */

  
  

  
  

          for(i=0;i<k;i++)

          {

              sum+=x[i];

  
  

              if(x[i]>((x[i]*(x[i]+1))/2-sum))

              {

                  rst=x[i];

                  break;

              }

  
  

          }

  
  

          if(!rst)

          {

              rst=(n*(n+1))/2-sum+1;

          }

  
  

  
  

          if(rst%2)

              printf("Chef\n");

          else

              printf("Mom\n");

  
  

      }

  return 0;

  }

• 
  

• Test Case 1

  
  Input (stdin)

  2
  
  5 2
  
  3 5
  
  5 1
  
  1
  
  

  Expected Output

  Mom
  
  Chef

• Test Case 2

  
  Input (stdin)

  2
  
  4 2
  
  3 4
  
  2 1
  
  3
  
  

  Expected Output

  Mom
  
  Chef