Guest User

Untitled

a guest
Jul 16th, 2018
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. import sys
  2. sys.setrecursionlimit(4000)
  3.  
  4. str_cases = raw_input()
  5. cases = int(str_cases)
  6.  
  7. energy = []
  8.  
  9. def is_possible(tsum, rindex, seq):
  10. if tsum < 0:
  11. return 0
  12. if tsum == energy[rindex]:
  13. seq.append(rindex)
  14. return 1
  15.  
  16. if rindex == 0:
  17. #print "out of luck"
  18. return 0
  19.  
  20. if is_possible(tsum, rindex-1, seq):
  21. return 1
  22. else:
  23. seq.append(rindex)
  24. if is_possible(tsum-energy[rindex], rindex-1, seq):
  25. return 1
  26. else:
  27. seq.pop(seq.index(rindex))
  28. return 0
  29.  
  30. for case in range(cases):
  31. str_first = raw_input()
  32. (s_N, s_E) = str_first.split(' ')
  33. N = int(s_N)
  34. E = int(s_E)
  35.  
  36. str_second = raw_input()
  37. a = [int(x) for x in str_second.split(' ')]
  38.  
  39. str_third = raw_input()
  40. b = [int(x) for x in str_third.split(' ')]
  41. for elem in energy:
  42. energy.remove(elem)
  43. for i in range(N):
  44. if i > 0:
  45. old = energy[i-1]
  46. else:
  47. old = 0
  48. energy.append((old*a[i])+b[i])
  49. seq = []
  50. out_string = ""
  51. if is_possible(E, N-1, seq):
  52. #print "yay"
  53. seq.sort()
  54. pseq = [str(elem) for elem in seq]
  55. out_string = ' '.join(pseq)
  56. else:
  57. out_string = "-1"
  58. print out_string
Add Comment
Please, Sign In to add comment