Tävlingsprogrammering/Uppgifter/Australian open

Mall:Proguppgift

Lösning

Lösningen är rättfram: simulera turneringen enligt spelschemat och håll hela tiden reda på vilka spelare som kan finnas på varje plats i spelschemat och med vilken sannolikhet de är där. Om man för varje match låter alla spelare möta alla andra spelare utan att ta hänsyn till att många sannolikheter är 0, så behövs uppemot (2ⁿ)³ operationer och lösningen blir för långsam för de största fallen.

Lösning i Python:

import sys
import math

def s(xa,xb): return 1.0/(1.0+math.exp(xb-xa))  Mall:Komm

def match(a,b):    Mall:Komm
    global skill
    keys=a.keys()+b.keys()        Mall:Komm
    res=dict(zip(keys,[0.0]*len(keys)))    Mall:Komm
    for i,pa in a.iteritems():      Mall:Komm
        for j,pb in b.iteritems():    Mall:Komm
            paw=s(skill[i], skill[j])     Mall:Komm
            res[i]+=pa*pb*paw         Mall:Komm
            res[j]+=pa*pb*(1-paw)      Mall:Komm
    return res

def play(plist):      Mall:Komm
    N=len(plist)
    if(N==1): return plist[0];      Mall:Komm
    return match(play(plist[0:N/2]),play(plist[N/2:N]))    Mall:Komm


Mall:Komm
lines=sys.stdin.readlines() 
n=2**int(lines[0])
skill=[float(x) for x in lines[1].split()]

winner=play([ {i : 1.0} for i in range(n)])   Mall:Komm
(best,prob)=max(winner.items(),key=lambda x: x[1])   Mall:Komm
print best+1, "%.8f"%prob