1 / 2
Mar 2016

Hello, I am new to python and I am trying to get better at it by solving some of the problems found in SPOJ (the easier ones mainly). So I decided to start with HANGOVER10 as it was the first one on my list that was unsolved and easy enough. However, trying two different approaches gave me TLE and I am wondering why as both are reasonably efficient. Is it possible that my script does not properly show results or something like that or that it does not properly consume input? Any help would be appreciated, both of my approaches are below:

Approach 1:

line = float(input())
while line != 0.0:
    cards = 1
    overhang = 0
    while(overhang < line):
        overhang += 1 / (cards+1)
        cards += 1
        
    else:
        print("%d card(s)" % (cards-1))
        line = float(input())

Approach 2:

overhang = [0.0] * 276
overhang[0] = 1/2
for i in range(1,276):
    overhang[i] = overhang[i-1] + 1/(i+2)
    print (overhang[i])
    
line = float(input())
while line != 0.0:
    i = 0
    while (overhang[i] < line):
        i += 1
    else:
        print ("%d card(s)" % (i+1))
        line = float(input())

I saw some comments under the problem regarding something along the lines of constant time using logarithms, but I am unsure of how to do that. Any hints would be appreciated!
P.S.: Both scripts were compiled and run in Python 3.4.

  • created

    Mar '16
  • last reply

    Mar '16
  • 1

    reply

  • 1.1k

    views

  • 2

    users

  • 1

    link

Your algorithm is fast enough. You could optimize by caching /precalculating, but that is not necessary. Perhaps you should simply use another interpreter version: "Python 3"?