import random
def birthday_attack(choices):
  tries = 0
  max_tries = choices**2
  chosen = set()
  choice = None
  while choice not in chosen and tries < max_tries:
    tries += 1
    if choice is not None:
      chosen.add(choice)
    choice = random.randrange(choices)
  return tries
trials = 100000
tries = [birthday_attack(2**8) for i in range(trials)]
print(sum(tries)/trials)
tries.sort()
print(tries[trials//2])