Hulkade kahendpuu

문제

Hulkade kahendpuu erineb tavalisest kahendotsingu puust selle poolest, et puu igas tipus võib olla mitu elementi. Samas kehtib kahendotsingu puu põhitingimuse üldistus: mistahes tipu vasaku alampuu kõik elemendid peavad olema väiksemad ja parema alampuu kõik elemendid suuremad kõigist tipu enda elementidest.

Seega saab hulkade kahendpuus elementi otsida samamoodi kui tavalises kahendotsingu puus. Muuhulgas saab igas tipus otsustada, kas otsitav element peab olema selles tipus või kas tuleks otsingut jätkata vasakus või paremas alampuus. Kui loeme selle otsustamise üheks operatsiooniks, on mistahes elementi sisaldava tipu leidmiseks vaja täpselt nii palju operatsioone, kui palju on tasemeid puu juurest selle elemendi asukohani.

Tippude mäluhalduse iseärastuste tõttu on puu ühes tipus olla võivate elementide maksimaalne arv erinevatel tasemetel erinev. Täpsemalt, kui juurtipu taseme number on $11$, siis on tasemel number $ii$ ühes tipus olevate elementide maksimaalne arv $m_{i}m\_i$ määratud seostega

kus $MM$, $KK$ ja $D_{j}D\_j$ on antud täisarvud ning $(i-1)K(i-1)\; \backslash bmod\; K$ on arvu $i-1i-1$ arvuga $KK$ jagamisel tekkiv jääk. Näiteks kui $M=4M\; =\; 4$, $K=2K\; =\; 2$ ja $D_1=1D\_1\; =\; 1$, $D_2=2D\_2\; =\; 2$, siis võib puu juurtipus olla maksimaalselt $m_1=M=4m\_1\; =\; M\; =\; 4$, tema vahetutes alluvates kummaski maksimaalselt $m_2=m_1-D_1=4-1=3m\_2\; =\; m\_1\; -\; D\_1\; =\; 4\; -\; 1\; =\; 3$, nende vahetutes alluvates igaühes $m_3=m_2-D_2=3-2=1m\_3\; =\; m\_2\; -\; D\_2\; =\; 3\; -\; 2\; =\; 1$ ja kõigis järgmistes kihtides igas tipus maksimaaslet $m_i=\max (1,\dots )=1m\_i\; =\; \backslash max\{(1,\; \backslash ldots)\}\; =\; 1$ element.

Lisaks on teada, et puu kasutamisel otsitakse erinevaid elemente sellest erinevate tõenäosustega ja seega ei tarvitse balansseeritud puu anda parimat keskmist päringule vastamise aega. Näiteks kui ülekaalukalt kõige sagedamini otsitakse minimaalset elementi, on kasulik panna see puu juurtippu ja siis peab kogu vasak alampuu jääma tuhjaks.

Ülesanne on leida keskmine ühe elemendi otsimiseks vajalik operatsioonide arv antud elementide hulga ja pärigute tõenäosuste jaoks optimaalse kujuga hulkade kahendpuus.

입력

Tekstifaili esimesel real on kolm täisarvu: hulga elementide arv $NN$ ($1\le N\le 1001\; \backslash le\; N\; \backslash le\; 100$) ning $MM$ ($1\le M\le N1\; \backslash le\; M\; \backslash le\; N$) ja $KK$ ($1\le K\le N1\; \backslash le\; K\; \backslash le\; N$). Järgmisel K real on igaühel üks täisarv: real $j+1j\; +\; 1$ on $D_{j}D\_j$ väärtus ($0\le D_j\le M0\; \backslash le\; D\_j\; \backslash le\; M$). Faili viimasel real on $NN$ reaalarvu $P_{i}P\_i$ ($0\le P_i\le 10\; \backslash le\; P\_i\; \backslash le\; 1$; ${\sum }_{i=1}^N{P}_i=1\backslash sum\_\{i=1\}^\{N\}\{P\_i\}\; =\; 1$): elementide otsimise tõenäosused. Tõenäosused on järjestatud elementide väärtuste järgi (esimene tõenäosus vastab vähimale elemendile). Pange tähele, et elementide väärtused ei ole lahenduse jaoks olulised; võib eeldada, et nad on kõik erinevad.

출력

Tekstifaili ainsale reale väljasta uks reaalarv, ühele otsingule kuluv keskmine operatsioonide arv optimaalse kujuga puus. Väljastatud vastus võib täpsest erineda ülimalt ${10}^{-6}10^\{-6\}$ võrra.

힌트

Teises näites on optimaalne puu kuju järgmine:

[이미지 1]