Coins getting WA

general
, ,
1

Byteland COINS
While the code below passes

z = {}
def fun(n):
	if n<=1:
		return n
	elif n in z:
		return z[n]
	else:
		d = max(n,fun(n/2)+fun(n/3)+fun(n/4))
		z[n] = d
		return d
	
import sys
for i in sys.stdin:
	print fun(int(i))

But code below doesn’t pass both are almost same,

# your code goes here
arr = {}
def dp(n):
	if n in arr:
		return arr[n]
	if n==0 or n==1:
		arr[n] = n
		return n
	a = n/3
	b = n/2
	c = n/4
	ans = max(dp(a)+dp(b)+dp(c),n)
	arr[n] = ans
	return ans
t = input()
for i in xrange(t):
	k = input()
	print dp(k)

Kindly help!

2

The second code considers the first line in input as number of test cases, which is wrong.

There are no “number of test cases”. You should be iterating over the whole of input file, until there is no more input to process.

1 Like