BallsSeparating.py

import math,string,itertools,fractions,heapq,collections,re,array,bisect,random

class BallsSeparating:
    def minOperations(self, red, green, blue):
        size=len(red)
        MAX=1<<30
        dp = [[MAX for j in range(8)] for i in range(size+1)]
        dp[0][0]=0
        for x in range(size):
            for bit in range(8):
                sum=red[x]+green[x]+blue[x]+dp[x][bit]
                dp[x+1][bit|(1<<0)]=min(dp[x+1][bit|(1<<0)],sum-red[x])
                dp[x+1][bit|(1<<1)]=min(dp[x+1][bit|(1<<1)],sum-green[x])
                dp[x+1][bit|(1<<2)]=min(dp[x+1][bit|(1<<2)],sum-blue[x])
        return dp[size][7] if dp[size][7]!=MAX else -1;
        
        

# BEGIN KAWIGIEDIT TESTING
# Generated by KawigiEdit-pf 2.3.0
import sys
import time
def KawigiEdit_RunTest(testNum, p0, p1, p2, hasAnswer, p3):
	sys.stdout.write(str("Test ") + str(testNum) + str(": [") + str("{"))
	for i in range(len(p0)):
		if (i > 0):
			sys.stdout.write(str(","))
		
		sys.stdout.write(str(p0[i]))
	
	sys.stdout.write(str("}") + str(",") + str("{"))
	for i in range(len(p1)):
		if (i > 0):
			sys.stdout.write(str(","))
		
		sys.stdout.write(str(p1[i]))
	
	sys.stdout.write(str("}") + str(",") + str("{"))
	for i in range(len(p2)):
		if (i > 0):
			sys.stdout.write(str(","))
		
		sys.stdout.write(str(p2[i]))
	
	sys.stdout.write(str("}"))
	print(str("]"))
	obj = BallsSeparating()
	startTime = time.clock()
	answer = obj.minOperations(p0, p1, p2)
	endTime = time.clock()
	res = True
	print(str("Time: ") + str((endTime - startTime)) + str(" seconds"))
	if (hasAnswer):
		res = answer == p3
	
	if (not res):
		print(str("DOESN'T MATCH!!!!"))
		if (hasAnswer):
			print(str("Desired answer:"))
			print(str("\t") + str(p3))
		
		print(str("Your answer:"))
		print(str("\t") + str(answer))
	elif ((endTime - startTime) >= 2):
		print(str("FAIL the timeout"))
		res = False
	elif (hasAnswer):
		print(str("Match :-)"))
	else:
		print(str("OK, but is it right?"))
	
	print(str(""))
	return res

all_right = True
tests_disabled = False


# ----- test 0 -----
disabled = False
p0 = (1,1,1)
p1 = (1,1,1)
p2 = (1,1,1)
p3 = 6
all_right = (disabled or KawigiEdit_RunTest(0, p0, p1, p2, True, p3) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 1 -----
disabled = False
p0 = (5,)
p1 = (6,)
p2 = (8,)
p3 = -1
all_right = (disabled or KawigiEdit_RunTest(1, p0, p1, p2, True, p3) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 2 -----
disabled = False
p0 = (4,6,5,7)
p1 = (7,4,6,3)
p2 = (6,5,3,8)
p3 = 37
all_right = (disabled or KawigiEdit_RunTest(2, p0, p1, p2, True, p3) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 3 -----
disabled = False
p0 = (7,12,9,9,7)
p1 = (7,10,8,8,9)
p2 = (8,9,5,6,13)
p3 = 77
all_right = (disabled or KawigiEdit_RunTest(3, p0, p1, p2, True, p3) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 4 -----
disabled = False
p0 = (842398,491273,958925,849859,771363,67803,184892,391907,256150,75799)
p1 = (268944,342402,894352,228640,903885,908656,414271,292588,852057,889141)
p2 = (662939,340220,600081,390298,376707,372199,435097,40266,145590,505103)
p3 = 7230607
all_right = (disabled or KawigiEdit_RunTest(4, p0, p1, p2, True, p3) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

if (all_right):
	if (tests_disabled):
		print(str("You're a stud (but some test cases were disabled)!"))
	else:
		print(str("You're a stud (at least on given cases)!"))
	
else:
	print(str("Some of the test cases had errors."))

# END KAWIGIEDIT TESTING
#Powered by KawigiEdit-pf 2.3.0!