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).
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!