Firestone's blog

I need a little help...
By Firestone, history, 5 years ago, In English

Given an array and an integer k. There are two players A and B, each turn one player take one number from the array, after taking all numbers from the array, calculate the sum of the numbers each player has taken. If only A's sum or B's sum is divisible by k, he'll win otherwise it is supposed to be a draw.

A always play first, write a program to predict who will win, or it will be a draw.

Each player plays this game optimally.

Input:

First line contains and integer n — the size of the array and k ( 1 <= N <= 2000, 2 <= k <= 50).

Second line contains the integers in the array (0 <= A[i] <= 1e10).

Output: "A" or "B", depends on who will win or "DRAW" — if there will be no winners.

Sample Input 1:

3 4

4 2 4

Sample Output 1:

B

Sample Input 2:

3 4

2 2 2

Sample Output 2:

A

Sample Input 3:

3 4

8 4 4

Sample Output 3:

DRAW

Can anybody help me with this problem? Thank you so much!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Where i can submit this task?

→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I solved it ^^ ty guys

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    OK :) Can you provide some hints of the Approach !

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I removed the pairs of identical numbers, if there are more than 3 different numbers remaining in the array or the array is empty, it always ends with a draw. If there are 1 or two numbers left, let's check the sum of the removed numbers and divide it by 2 then check the remainings in the array, some if else are needed.

      If there are two numbers left, B can't win.

      → Reply