Project Euler #236: Luxury Hampers

  • + 0 comments

    passed 6/16 test cases. failed 10/16 due to timeout. finding a way to optimize it. any suggestion?

    from itertools import *
    import math
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    n_a=[]
    n_b=[]
    sa=sum(a)
    sb=sum(b)
    flag=0
    for i in range(n):
        n_a.append(list(range(1,a[i]+1)))   """make a list of all possible values of number of bad products for each product by A"""
        n_b.append(list(range(1,b[i]+1)))    #same for B
        
    for i in product(*n_a):      """iterate through all the possible combinations of number of bad product by A"""
         for j in product(*n_b):  """iterate through all the possible combinations of number of bad product by B"""
               count=0                """counting the number of times ratio is maintained for the current combination number of bad products by A and B """
               p=sum(i)*sb            """expression you will get by putting the given condition in a equation (A-overall/B-overall) spoilage ratio"""
               q=sum(j)*sa
               m=math.gcd(p,q)  """reduce the fraction to its lowest terms"""
               p,q=p//m,q//m          
     
               if (p/q)<=1:           """less than 1 then continue to next iteration"""
                      continue
    
               for k in range(n):     """each pair of kth product check the equality of ratio """
                      r=(j[k]*a[k])
                      s=(i[k]*b[k])         """expression you will get by putting the given condition in a equation (B-kth/A-kth) per product spoilage ratio"""
                      
                      t=math.gcd(r,s)      """reduce the fraction to its lowest terms"""
                      r,s=r//t,s//t
    
                       if r!=p or s!=q :     """not equal then break the loop and go for next combination of i and j (change j)"""
                                 break
                       else:
                                  count+=1          """equal then increase count"""
                 
                       if count==n:          """the ratio is same for all the n products then print the ratio and exit all the loops"""
                                   flag=1
                                   print("{}/{}".format(r,s))
                                   break
    
               if flag==1:
                     break
    
        if flag==1:
            break