def count(runners, runner, pages):
if runners.get(runner) is None:
return 0.0
if len(runners.values()) == 1:
return 1.0
runner_page = runners[runner]
return find(pages, runner_page)/(len(runners.values()) - 1)
def find(pages, value):
if len(pages) == 0:
return 0
first = 0
last = len(pages) - 1
pos = 0
while first <= last:
mid = (first + last) // 2
pos = mid
if pages[mid] == value:
break
else:
if value < pages[mid]:
last = mid - 1
else:
first = mid + 1
if value > pages[pos]:
return len(pages)
return pos
def insert(pages, old_value, new_value):
if old_value is not None:
index = find(pages, old_value)
pages.pop(index)
index = find(pages, new_value)
if (len(pages) == 0) or (index < len(pages) and pages[index] != new_value):
pages.insert(index, new_value)
q = int(input())
runners = {}
pages = []
for i in range(q):
query = input().split(' ')
runner = int(query[1])
if query[0] == 'RUN':
page = int(query[2])
if runners.get(runner) is None:
insert(pages, None, page)
runners[runner] = page
else:
insert(pages, runners[runner], page)
runners[runner] = page
if query[0] == 'CHEER':
print("{:.6f}".format(count(runners, runner, pages)))
ZGVmIGNvdW50KHJ1bm5lcnMsIHJ1bm5lciwgcGFnZXMpOgoJaWYgcnVubmVycy5nZXQocnVubmVyKSBpcyBOb25lOgoJCXJldHVybiAwLjAKCWlmIGxlbihydW5uZXJzLnZhbHVlcygpKSA9PSAxOgoJCXJldHVybiAxLjAKCQoJcnVubmVyX3BhZ2UgPSBydW5uZXJzW3J1bm5lcl0KCXJldHVybiBmaW5kKHBhZ2VzLCBydW5uZXJfcGFnZSkvKGxlbihydW5uZXJzLnZhbHVlcygpKSAtIDEpCgpkZWYgZmluZChwYWdlcywgdmFsdWUpOgoJaWYgbGVuKHBhZ2VzKSA9PSAwOgoJCXJldHVybiAwCglmaXJzdCA9IDAKCWxhc3QgPSBsZW4ocGFnZXMpIC0gMQoJCglwb3MgPSAwCgl3aGlsZSBmaXJzdCA8PSBsYXN0OgoJCW1pZCA9IChmaXJzdCArIGxhc3QpIC8vIDIKCQlwb3MgPSBtaWQKCQlpZiBwYWdlc1ttaWRdID09IHZhbHVlOgoJCQlicmVhawoJCWVsc2U6CgkJCWlmIHZhbHVlIDwgcGFnZXNbbWlkXToKCQkJCWxhc3QgPSBtaWQgLSAxCgkJCWVsc2U6CgkJCQlmaXJzdCA9IG1pZCArIDEKCglpZiB2YWx1ZSA+IHBhZ2VzW3Bvc106CgkJcmV0dXJuIGxlbihwYWdlcykKCXJldHVybiBwb3MKCmRlZiBpbnNlcnQocGFnZXMsIG9sZF92YWx1ZSwgbmV3X3ZhbHVlKToKCWlmIG9sZF92YWx1ZSBpcyBub3QgTm9uZToKCSAgIGluZGV4ID0gZmluZChwYWdlcywgb2xkX3ZhbHVlKQoJICAgcGFnZXMucG9wKGluZGV4KQoJaW5kZXggPSBmaW5kKHBhZ2VzLCBuZXdfdmFsdWUpCglpZiAobGVuKHBhZ2VzKSA9PSAwKSBvciAoaW5kZXggPCBsZW4ocGFnZXMpIGFuZCBwYWdlc1tpbmRleF0gIT0gbmV3X3ZhbHVlKToKCSAgICBwYWdlcy5pbnNlcnQoaW5kZXgsIG5ld192YWx1ZSkKCnEgPSBpbnQoaW5wdXQoKSkKCnJ1bm5lcnMgPSB7fQpwYWdlcyA9IFtdCmZvciBpIGluIHJhbmdlKHEpOgoJcXVlcnkgPSBpbnB1dCgpLnNwbGl0KCcgJykKCXJ1bm5lciA9IGludChxdWVyeVsxXSkKCWlmIHF1ZXJ5WzBdID09ICdSVU4nOgoJCXBhZ2UgPSBpbnQocXVlcnlbMl0pCgkJaWYgcnVubmVycy5nZXQocnVubmVyKSBpcyBOb25lOgoJCQlpbnNlcnQocGFnZXMsIE5vbmUsIHBhZ2UpCgkJCXJ1bm5lcnNbcnVubmVyXSA9IHBhZ2UKCQllbHNlOgoJCQlpbnNlcnQocGFnZXMsIHJ1bm5lcnNbcnVubmVyXSwgcGFnZSkKCQkJcnVubmVyc1tydW5uZXJdID0gcGFnZQoJaWYgcXVlcnlbMF0gPT0gJ0NIRUVSJzoKCQlwcmludCgiezouNmZ9Ii5mb3JtYXQoY291bnQocnVubmVycywgcnVubmVyLCBwYWdlcykpKQo=