Tävlingsprogrammering/Uppgifter/Australian open

Australian open

Årets stora idrottshändelse i Australien är naturligtvis International Olympiad in Informatics. I väntan på denna har man dock anordnat vissa sidoevenemang, exempelvis tennisturneringen Australian open. Detta är en utslagsturnering som kan beskrivas med ett spelschema enligt figuren ovan, där antalet omgångar n kan variera. Man startar alltså till vänster med 2ⁿ spelare, numrerade från 1 till 2ⁿ. Efter totalt 2ⁿ−1 matcher har man utsett en vinnare.

Vi antar nu att varje spelare i har en “förmåga” x_i, och att när två spelare i och j möts, så vinner spelare i med sannolikheten

$P(i{\text{ besegrar }}j)={\frac {1}{1+\exp(x_{j}-x_{i})}}$

och annars vinner spelare j eftersom en tennismatch inte kan sluta oavgjort (exp(x) betecknar exponentialfunktionen e^x ). Formeln är vald så att P(i besegrar j) + P(j besegrar i) = 1.

Skriv ett program som, givet alla spelares förmågor, avgör vem som har störst chans att vinna turneringen och hur stor denna chans är.

Indata

På första raden står ett tal n, antal omgångar, där 1≤n≤10. På andra raden står 2ⁿ flyttal mellan 0 och 10, förmågan för varje spelare i nummerordning.

Utdata

Ett rad med ett heltal och ett flyttal: numret på den spelare som har störst chans att vinna turneringen samt sannolikheten att den spelaren vinner. Om flera spelare har störst chans kan du ange vilken som helst av dem. Sannolikheten ska skrivas ut med minst 6 decimaler.

Exempel 1

2
2.0 1.8 1.9 1.1

ska ge svaret

3 0.34326946

Förklaring: Första matchen vinner spelare 1 med sannolikheten 0.549834 och spelare 2 med sannolikheten 0.450166. Andra matchen vinner spelare 3 med sannolikheten 0.689974 och spelare 4 med sannolikheten 0.310026. Dessa händelser är oberoende och därmed kan vi räkna ut sannolikheten för varje möjligt finalpar genom att multiplicera sannolikheterna med varandra. Det ger upphov till följande tabell:

Exempel 2

4
9.99 9.53 9.93 8.77 8.57 9.55 8.12 9.41 8.20 9.43 8.91 8.63 8.88 9.83 8.69 8.40

ska ge svaret

14 0.20348623

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))  #Returnerar sannolikheten att A vinner

def match(a,b):    #Returnerar sannolikheter för vem som vinner matchen, givet sannolikheter för vilka som spelar
    global skill
    keys=a.keys()+b.keys()        #Vilka spelare är möjliga vinnare?
    res=dict(zip(keys,[0.0]*len(keys)))    #Sätt deras sannolikheter till 0
    for i,pa in a.iteritems():      #Loopa över alla möjliga spelare A
        for j,pb in b.iteritems():    #Loopa över alla möjliga moståndare  B
            paw=s(skill[i], skill[j])     #Sannolikhet att A vinner om A möter B
            res[i]+=pa*pb*paw         #Ackumulera total sannolikhet att A vinner matchen
            res[j]+=pa*pb*(1-paw)      #Ackumulera total sannolikhet att B vinner matchen
    return res

def play(plist):      #Rekursiv funktion som spelar en turnering
    N=len(plist)
    if(N==1): return plist[0];      #Om endast en spelare så vinner den automatiskt
    return match(play(plist[0:N/2]),play(plist[N/2:N]))    #Spela vardera hälften av turneringen och sedan en match för att avgöra.


#Här börjar programmet
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)])   #Spela turneringen med startsannolikhet 1 för alla spelare
(best,prob)=max(winner.items(),key=lambda x: x[1])   #Plocka ut spelaren med högst sannolikhet
print best+1, "%.8f"%prob