스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Å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^n spelare, numrerade från 1 till 2^n. Efter totalt 2^n - 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 besegrar j) = 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 heltal n (1 ≤ n ≤ 10), antal omgångar. På andra raden står 2^n flyttal mellan 0 och 10, förmågan för varje spelare i nummerordning.
Utdata
Skriv ut 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. Svaret accepteras om det absoluta felet är mindre än 10^-5.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
| Grupp | Poäng | Gränser |
|---|---|---|
| 1 | 20 | n=1 |
| 2 | 80 | Inga ytterligare begränsningar. |
Förklaring exempelfall 1
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:
| Sannolikhet att | Sannolikhet att | Bidrag till total chans att spelaren vinner | ||||
|---|---|---|---|---|---|---|
| Match | matchen spelas | vinna matchen | 1 | 2 | 3 | 4 |
| 1–3 | 0.379371 | 0.524979–0.475021 | 0.199162 | – | 0.180209 | – |
| 1–4 | 0.170463 | 0.710950–0.289050 | 0.121190 | – | – | 0.049272 |
| 2–3 | 0.310603 | 0.475021–0.524979 | – | 0.147543 | 0.163060 | – |
| 2–4 | 0.139563 | 0.668188–0.331812 | – | 0.093254 | – | 0.046309 |
| Summa | 1.000000 | 0.320352 | 0.240797 | 0.343269 | 0.095581 |
예제
예제 1
2 2.0 1.8 1.9 1.1
3 0.34326946
예제 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
14 0.20348623