import random
def open(j, shuffled_box):
    opened = [ ]   # the boxes that I have opened
    while True:  # continuing open the box until I find the right number
        opened.append(j)
        box_number = shuffled_box[j]     # the next box to be opened is the one of the number I get
        if box_number == opened[0]:     # find it
            break
        else:
            j = box_number
    trail_times = len(opened)
    return trail_times          # count how many times I have trailed

acc_0 = 0
timesteps = 10000
agents = 100
for k in range(timesteps):
    acc_1 = 0
# I put the numbers into different boxes.
    shuffled_box = { }
    copy = [i for i in range(agents)]
    random.shuffle(copy)    
    for i in range(agents):
        shuffled_box[i] = copy[i]     # shuffled_box looks like this =>{0:2, 1:20, ....., 98:45, 99:34}
        
    for j in range(agents):
        q = open(j, shuffled_box)
        if q > agents/2:    # if the trail_times bigger than the allowed 
            break
        else:
            acc_1 += 1     # count the number of the successed man
    
    if acc_1 == agents: # if everyone have succeeded
        acc_0 += 1
print "The winning posibility is:", acc_0/float(timesteps)