Firestone's blog

I need a little help...
By Firestone, history, 3 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

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

Where i can submit this task?

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

    It's from a paper in my language. I translated it into English so sadly I'm not sure if there is an English version of the problem.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      No, i don't need english version of the problem, i need online judge where i can submit my solution.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 4   Vote: I like it +8 Vote: I do not like it

        I took it from a private website of my team, sorry I cannot give you the original link. I tried to generate the same problem here: https://codeforces.net/group/sr2enymX9k

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          Thanks! I understand that my solution is incorrect, can you explain how to solve it?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              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.

            Sry for my bad English :(

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

I solved it ^^ ty guys

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

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        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