Skip to content

Instantly share code, notes, and snippets.

@zsrinivas
Created December 28, 2014 03:42
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save zsrinivas/556d3019d492cc3b8134 to your computer and use it in GitHub Desktop.
spoj 3934. Recaman’s Sequence | MRECAMAN
from sys import stdin
from itertools import imap
def main():
a = [0]*500002
a[-1] = ''
v = [True] * 3012501
v[0] = False
for x in xrange(1, 500001):
if (a[x - 1] - x > 0) and v[a[x - 1] - x]:
v[a[x - 1] - x] = False
a[x] = a[x - 1] - x
else:
v[a[x - 1] + x] = False
a[x] = a[x - 1] + x
for x in imap(lambda y: a[int(y)], stdin):
print x
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment