fork download
copy 
  1. import bisect
  2.  
  3. a = [2,7]
  4. size = 33
  5. for i in range(3,size):
  6.     if i%2 == 0:
  7.         a.append(a[-1]+7)
  8.     else:
  9.         a.append(a[-1]+3*a[-2])
  10. b = a[:16]
  11. c = a[16:]
  12.  
  13. allowedNumbersB = []
  14. allowedNumbersC = []
  15. def f(currentIndex, tillNowSum, type):
  16.     if currentIndex >= size/2:
  17.         if type == 0:
  18.             allowedNumbersB.append(tillNowSum)
  19.         else:
  20.             allowedNumbersC.append(tillNowSum)
  21.     else:
  22.         if type == 0:
  23.             f(currentIndex+1, tillNowSum+b[currentIndex], 0)
  24.             f(currentIndex+1, tillNowSum, 0)
  25.         else:
  26.             f(currentIndex+1, tillNowSum+c[currentIndex], 1)
  27.             f(currentIndex+1, tillNowSum, 1)
  28. f(0,0,0)
  29. f(0,0,1)
  30. allowedNumbersB = list(set(allowedNumbersB))
  31. allowedNumbersB.sort()
  32. allowedNumbersC = list(set(allowedNumbersC))
  33. allowedNumbersC.sort()
  34.  
  35. for _ in range(input()):
  36.     n = input()
  37.     ans = "NO"
  38.     for i in allowedNumbersC:
  39.         pos = bisect.bisect(allowedNumbersB, n-i)
  40.         if pos != 0 and allowedNumbersB[pos-1] == n-i:
  41.             ans = "YES"
  42.             break
  43.     print ans
Success #stdin #stdout 0.07s 27192KB
comments (?)
stdin
copy 
2
9 
11
stdout
copy 
YES
NO
https://ideone.com/ecPZ1C
language:
Python (cpython 2.7.16)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!