from random import random
from math import sqrt
NUM_TARGETS = 2
divis = sqrt(NUM_TARGETS)
shards = 0
last_shard = 0
accum = 0.0
l = []
NUM_SHARDS = 100000
overflow = 0
ticks = 0
while shards < NUM_SHARDS:
  for target in xrange(NUM_TARGETS):
    ticks += 1
    inc = random() * 0.32
    assert(0 <= inc <= 0.32)
    if target == 0:
      inc *= 1.15
    accum += inc
    if accum >= divis:
      overflow += (accum - divis)
      accum -= 1
      shards += 1
      l.append(last_shard + 1)
      last_shard = 0
    else:
      last_shard += 1

print sum(l), ticks
print (overflow / NUM_SHARDS)
from collections import Counter
c = Counter(l)
for k in sorted(list(c.keys())):
  print k, float(c[k]) / NUM_SHARDS * 100
print (float(sum(l)) / NUM_SHARDS)
print (NUM_SHARDS / (float(sum(l))))