Demo entry 6644602

etest

   

Submitted by anonymous on Oct 05, 2017 at 05:26
Language: Python 3. Code size: 588 Bytes.

import sys
sys.setrecursionlimit(50000)

def get_sum(n):
    #if the sum > n, just return 0
    if (n < 0):
        return 0
    #if n have already calculated, return the value from the list
    if r[n-1] >=0:
        return r[n-1]
    #if the remaining = 0, which means we find one more way to get the sum.
    elif (n == 0):
        return 1
    #else, recursively add remaining-1 ,-3 and -4
    else:
            r[n-1] = get_sum(n-1) + get_sum(n-3) + get_sum(n-4)
    #return the final result
    return r[n-1]


n = 100

r = [-1] * n #Memiozation
ret = get_sum(n)

print(ret%100000)

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).