Problem:


Score : 1800 points

Problem Statement

Snuke has X+Y balls.
X of them have an integer A written on them, and the other Y of them have an integer B written on them.

Snuke will divide these balls into some number of groups.
Here, every ball should be contained in exactly one group, and every group should contain one or more balls.

A group is said to be good when the sum of the integers written on the balls in that group is a multiple of an integer C.
Find the maximum possible number of good groups.

Solve T test cases for each input file.

Constraints

1 \leq T \leq 2 \times 10^4

1 \leq A,X,B,Y,C \leq 10^9

A \neq B

Input

Input is given from Standard Input in the following format.
The first line is as follows:

T

Then, T test cases follow.
Each test case is given in the following format:

A X B Y C

Output

For each test case, print a line containing the maximum possible number of good groups.

Sample Input 1

3
3 3 4 4 5
2 1 1 5 3
3 1 4 2 5

Sample Output 1

2
2
0

In the first test case, we can have two good groups by making the following groups: \{3,3,4\} and \{3,4,4,4\}.

In the second test case, we can have two good groups by making the following groups: \{2,1\}, \{1,1,1\}, and \{1\}.



Sample input:
3
3 3 4 4 5
2 1 1 5 3
3 1 4 2 5


Sample output:
2
2
0

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import itertools

def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

def a(target, a, b, x, y):
    # print("target=",target,"a=",a,"b=",b,"x=",x,"y=",y)
    a_n = min(x, target // a)
    b_n = min(y, target // b)
    # print("a_n=",a_n, "target//a=",target//a, "b_n=",b_n,"target//b=",target//b)

    comb = []
    for a_i in range(a_n+1):
        for b_i in range(b_n+1):
            s = a * a_i + b * b_i
            # print("target=",target,"a=",a_i,"b=",b_i,"s=",s)
            if s == target:
                comb.append((a_i,b_i))
    return comb

def solver():
    A,X,B,Y,C = LI()
    # print("A=",A)
    # print("X=",X)
    # print("B=",B)
    # print("Y=",Y)
    # print("C=",C)

    Total = A*X+B*Y
    C_loop = Total//C
    a_lmt = X
    b_lmt = Y
    ans = 0
    for c_i in range(C_loop):
        C_target = C * (c_i+1)

        pattern = a(C_target, A, B, a_lmt, b_lmt)
        print("target=",C_target, "pattern_num=",len(pattern))
        ans += len(pattern)
        for p in pattern:
            # print("p=",p)
            a_lmt -= p[0]
            b_lmt -= p[1]
    return ans
    
def main():
    T = I()
    # print("T=",T)

    for _ in range(T):
        # print("ANS=",solver())
        print(solver())


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
#NumList=[3, 3, 4, 4, 5]
NumList=[2, 1, 1, 5, 3]

P = [input().split() for i in range(T)]

def ReturnGoodGroup(AXBYC):
    NumList=AXBYC
    A, X, B, Y, C = int(NumList[0]),int(NumList[1]),int(NumList[2]),int(NumList[3]),int(NumList[4])

    RemainingBall=X+Y
    GroupNum=0

    BallList=[]

    for A_times in range(X+1):
        for B_times in range(Y+1):
            if A_times+B_times>0 and (A*A_times+B*B_times)%C==0:
                BallList.append([A_times,B_times])

    OmomiBallList=[[x[0]/A,x[0]/B] for x in BallList]
    #print(OmomiBallList)
    BallNumSumList=[sum(x) for x in OmomiBallList]

    OmomiSortedBallList = [x for _,x in sorted(zip(BallNumSumList,BallList))]
    #print(OmomiSortedBallList) 


    A_Remain=X
    B_Remain=Y


    for ls in OmomiSortedBallList:
        #print(ls)
        A_Remain-=ls[0]
        B_Remain-=ls[1]

    #     print("A_Remain:")
    #     print(A_Remain)
    #     print("B_Remain:")
    #     print(B_Remain)

        if A_Remain>-1 and B_Remain>-1:
            GroupNum+=1
        elif A_Remain<0 or B_Remain<0:
            break


    return(GroupNum)

for AXBYC in P:
    print(ReturnGoodGroup(AXBYC))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import itertools

def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

def a(target, a, b, x, y):
    # print("target=",target,"a=",a,"b=",b,"x=",x,"y=",y)
    a_n = min(x, target // a)
    b_n = min(y, target // b)
    # print("a_n=",a_n, "target//a=",target//a, "b_n=",b_n,"target//b=",target//b)

    comb = []
    for a_i in range(a_n+1):
        for b_i in range(b_n+1):
            s = a * a_i + b * b_i
            # print("target=",target,"a=",a_i,"b=",b_i,"s=",s)
            if s == target:
                comb.append((a_i,b_i))
    return comb

def solver():
    A,X,B,Y,C = LI()
    # print("A=",A)
    # print("X=",X)
    # print("B=",B)
    # print("Y=",Y)
    # print("C=",C)

    Total = A*X+B*Y
    C_loop = Total//C
    a_lmt = X
    b_lmt = Y
    ans = 0
    for c_i in range(C_loop):
        C_target = C * (c_i+1)

        pattern = a(C_target, A, B, a_lmt, b_lmt)
        # print("target=",C_target, "pattern_num=",len(pattern))
        ans += len(pattern)
        for p in pattern:
            # print("p=",p)
            a_lmt -= p[0]
            b_lmt -= p[1]
    return ans

def main():
    T = I()
    # print("T=",T)

    for _ in range(T):
        # print("ANS=",solver())
        print(solver())


if __name__ == '__main__':
    main()