game

• Problem Description

  
  " You are playing following game: given an array A of N natural numbers. All numbers in the array A are at most M. On every turn you may pick any two different elements Ai and Aj (ij), such that Ai, Aj M, and add K to both. The game ends when you are not able to continue. That is, when there is no pair (i,j) left such that both of them are less than equal to M.
  
  Let's call two arrays different if the sum of all their elements is different. When the game ends, you note down the final array A. How many different final arrays can you have.
  Input
  
  The first line contains three integers N, M and K. N elements of the array follow in the next line.
  Constraints
  
  1 <= N <= 1000000
  1 <= M,K<= 10000000000000
  1 <= Ai <= M
  test case 1:All possible sums are 14 and 10. You can get them by, for example, these arrays:
  
  A=(5, 4, 5),
  
  A=(1, 4, 5)
  
  The above arrays are different because their sums are different."

• CODING ARENA

• #include<stdio.h>

  int N;

  long long M,K;

  long long A[100000];

  int main()

  {

      int i;

      long long sum=0;

      long long max=0;

      scanf("%d %lld %lld",&N,&M,&K);

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

      {

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

      A[i]=(M-A[i])/K+1;

      

      if(max<A[i])

      max=A[i];

      

      sum+=A[i];

      }

      long long min=0;

      

      if((sum-max)%2==0)

      min=(sum-max)/2;

      else

      min=(sum-max)/2+1;

      

      long long ans=sum/2-min+1;

      ans=ans%(1000000007);

      printf("%lld\n",ans);

      

      return 0;

  }

• 
  

• Test Case 1

  
  Input (stdin)

  3 3 2
  
  1 2 3
  
  

  Expected Output

  2

• Test Case 2

  
  Input (stdin)

  3 3 3
  
  2 2 2
  
  

  Expected Output

  1