Advertisement
Guest User

Untitled

a guest
Jun 26th, 2019
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.73 KB | None | 0 0
  1. import sys
  2.  
  3.  
  4. def main(argv):
  5. path = argv[0]
  6. f = open(path)
  7. n, k = map(int, f.readline().split())
  8. s = f.readline().rstrip()
  9.  
  10. if n <= 3:
  11. print(n)
  12. return
  13.  
  14. cnt = [0] * (n - 2)
  15. cnt[0] += int(s[0] == "S") + int(s[1] == "S")
  16. cnt[1] += int(s[1] == "S")
  17. cnt[-1] += int(s[-1] == "S") + int(s[-2] == "S")
  18. cnt[-2] += int(s[-2] == "S")
  19. for i in range(2, n - 2):
  20. m = int(s[i] == "S")
  21. cnt[i - 2] += m
  22. cnt[i - 1] += m
  23. cnt[i] += m
  24.  
  25. first_sum = sum([c for c in cnt[::3]])
  26. second_sum = sum([c for c in cnt[1::3]])
  27. third_sum = sum([c for c in cnt[2::3]])
  28. idx_search_order = []
  29. if first_sum >= second_sum >= third_sum:
  30. idx_search_order = [0, 1, 2]
  31. elif first_sum >= third_sum >= second_sum:
  32. idx_search_order = [0, 2, 1]
  33. elif second_sum >= first_sum >= third_sum:
  34. idx_search_order = [1, 0, 2]
  35. elif second_sum >= third_sum >= first_sum:
  36. idx_search_order = [1, 2, 0]
  37. elif third_sum >= first_sum >= second_sum:
  38. idx_search_order = [2, 0, 1]
  39. else:
  40. idx_search_order = [2, 1, 0]
  41.  
  42. cnt_i = {0: set(), 1: set(), 2: set(), 3: set()}
  43. for i, c in enumerate(cnt):
  44. cnt_i[c].add(i)
  45.  
  46. ans = s.count(".")
  47. for c in range(3, 0, -1):
  48. while cnt_i[c] and k > 0:
  49. for offset in idx_search_order:
  50. this_cnt_i = cnt_i[c] & {i for i in range(offset, n - 2, 3)}
  51. while this_cnt_i:
  52. i = this_cnt_i.pop()
  53. this_cnt_i -= {i - 2, i - 1, i, i + 1, i + 2}
  54. cnt_i[c] -= {i - 2, i - 1, i, i + 1, i + 2}
  55. ans += c
  56. k -= 1
  57. print(ans)
  58.  
  59.  
  60. if __name__ == "__main__":
  61. main(sys.argv[1:])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement