Guest User

Untitled

a guest
Aug 16th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.79 KB | None | 0 0
  1. #import time
  2.  
  3. # num1 -- массив чисел, seed -- строка '0' и '1', которые рассматриваются как операторы '-' и '+'
  4. # функция проверяет равенство выражения из последовательно расставленных чисел и операторов из num1 и seed числу num2
  5.  
  6. def che(num1,num2,seed):
  7. a = num1[0]
  8. for i,j in zip(num1[1:], seed):
  9. if j == '1':
  10. a += i
  11. else:
  12. a -= i
  13. if a == num2:
  14. return True
  15. else:
  16. return False
  17.  
  18. # возвращает строку из '0' и '1', которая потом дополняется до нужной длины
  19. # чтобы было легче итерироваться, решил представить строку из '+' и '-' как двоичное число
  20. def gena (leng):
  21. for i in range(2**leng):
  22. yield bin(i)[2:]
  23.  
  24. # ввод чисел
  25. s1 = list(map(int,input().split(" ")))
  26. s2 = list(map(int,input().split(" ")))
  27.  
  28. #start_time = time.time()
  29.  
  30. # базовая проверка на четность, иногда экономит время
  31. if sum(s2)%2 != s1[1]%2:
  32. print ("No solution")
  33. else:
  34. for i in gena(leng = s1[0]-1):
  35. seed = '-'*(s1[0]-1 - len(i)) + i # дополним строку до нужной длины
  36. if che(num1 = s2, num2 = s1[1], seed = seed) == True:
  37. # формируем ответ
  38. seed += '='
  39. m = ''
  40. for x,y in zip(s2,seed):
  41. if y == '1':
  42. m += str(x)+'+'
  43. elif y == '=':
  44. m += str(x)+'='
  45. else:
  46. m += str(x)+'-'
  47. m += str(s1[1])
  48. print(m)
  49. break
  50. else:
  51. print ('No solution')
  52.  
  53. #print("--- %s seconds ---" % (time.time() - start_time))
  54.  
  55. In [24]: from ast import literal_eval
  56.  
  57. In [25]: from itertools import product
  58.  
  59. In [26]: from functools import reduce
  60.  
  61. In [27]: def validate(numbers, result):
  62. ...: if sum(numbers) >= result >= reduce(int.__sub__, sorted(numbers)):
  63. ...: return calculate(numbers, result)
  64. ...: return 'No solution'
  65. ...:
  66. ...:
  67.  
  68. In [28]: def calculate(numbers, result):
  69. ...: pattern = '{}'.join(map(str, numbers))
  70. ...: for i in product(['+', '-'], repeat=len(numbers)-1):
  71. ...: expr = pattern.format(*i)
  72. ...: if literal_eval(expr) == result:
  73. ...: return expr
  74. ...: return 'No solution'
  75. ...:
  76. ...:
  77. In [29]: validate([4, 3, 2, 1], -2)
  78. Out[29]: '4-3-2-1'
  79.  
  80. In [30]: validate([4, 3, 2, 1], 10)
  81. Out[30]: '4+3+2+1'
  82.  
  83. In [31]: validate([4, 3, 2, 1], 11)
  84. Out[31]: 'No solution'
  85.  
  86. In [32]: validate([4, 3, 2, 1], -10)
  87. Out[32]: 'No solution'
Add Comment
Please, Sign In to add comment