루미 알고리즘

#1314플래티넘Australian open

PO 2013 결선코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GruppPoängGränser
120n=1
280Inga 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 attSannolikhet attBidrag till total chans att spelaren vinner
Matchmatchen spelasvinna matchen1234
1–30.3793710.524979–0.4750210.199162–0.180209–
1–40.1704630.710950–0.2890500.121190––0.049272
2–30.3106030.475021–0.524979–0.1475430.163060–
2–40.1395630.668188–0.331812–0.093254–0.046309
Summa1.0000000.3203520.2407970.3432690.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

출처 표기

출처: Programmeringsolympiaden 2013년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.