2. Trojuholníková nerovnosť

Mišo a Žaba hrajú hru Trojuholníková nerovnosť. Jej pravidlá sú nasledovné.

Zadaný je orientovaný graf na \(n\) vrcholoch taký, že medzi každými dvoma rôznymi vrcholmi vedie práve jedna hrana. Hra pozostáva z niekoľkých kôl. V každom kole si v tajnosti obaja hráči vyberú niektorý vrchol, a následne sa ich voľby odkryjú. \(1\) bod získa hráč, ktorý si vybral ten vrchol, do ktorého vedie hrana zo súperovho vrcholu. Ak si obaja hráči zvolili ten istý vrchol, obaja získavajú \(\frac{1}{2}\) bodu. Úlohou každého hráča je nazbierať čo najviac bodov.

Obaja spolu nahrali strašné množstvo kôl v ktorých má Žaba \(100\)-percentnú úspešnosť, no Mišo zatiaľ nezískal ani jeden bod. Ten dospel k záveru, že Žaba mu vie čítať myšlienky a prišiel s nasledovným plánom, ako konečne získať nejaké body.

• Naučí sa generovať skutočne náhodné reálne čísla z intervalu \(\langle 0, 1)\).

• Každému vrcholu grafu \(v\) pridelí pravdepodobnosť \(p_v\), že si ho v kole vyberie.

Keďže Žaba vie Mišovi naozaj čítať myšlienky¹, Žaba o tomto pláne vie. A je mu jasné, že jeho \(100\)-percentná úspešnosť sa končí. Bude mať ale informáciu o tom, aké pravdepodobnosti si Mišo vyberie – na základe nich si zvolí najlepšiu možnú stratégiu.

Ako má Mišo prideliť vrcholom pravdepodobnosti, ak chce v očakávanom prípade získať najväčší možný podiel bodov?

Úloha

Zadaný je graf popisujúci hru. Každému vrcholu grafu \(v\) prideľte pravdepodobnosť \(p_v\), s akou si ho má Mišo vybrať.

Hodnotenie

V závislosti od toho, akú silnú stratégiu tvorí vaše pridelenie pravdepodobností, dostanete body. Konkrétne, Žaba pridelí vrcholom pravdepodobnosti \(q_v\), s ktorými ich bude hrať. Tieto zvolí tak, aby priemerný počet bodov, ktoré Mišo získa, bol čo najmenší.

Označme tento priemerný počet bodov \(x\). Potom za daný test získate \[\frac{1}{t} \cdot \frac{\log(\max(10^{-6}, 1 - 2x))}{\log 10^{-6}}\] bodov, kde \(t\) je počet testov vo vstupnom súbore.

Formát vstupu

Na prvom riadku vstupu je jedno celé číslo \(t = 100\) – počet testov. Nasleduje popis každého z \(t\) testov.

Každý test začína prázdnym riadkom. Na ďalšom riadku je celé číslo \(n = 9\) – počet vrcholov grafu. Nasleduje \(n - 1\) riadkov, v \(i\)-tom z nich sa nachádza \(i\)-čísel. Každé z týchto čísel bude z množiny \(\lbrace -1, 1 \rbrace\).

Číslo v \(i\)-tom riadku a \(j\)-tom stĺpci popisuje, ktorým smerom vedie hrana medzi vrcholmi \(i\) a \(j\). Ak je to \(1\), tak hrana vedie z \(j\) do \(i\) – teda \(i\) poráža \(j\). V druhom prípade vedie hrana opačným smerom.

Formát výstupu

Pre \(i\)-ty test vypíšte na \(i\)-ty riadok výstupu toľko medzerami oddelených čísel z intervalu \(\langle 0, 1 \rangle\), koľko je vrcholov v teste. Tieto čísla musia mať súčet \(1\).

Odporúčame čísla vypisovať s presnosťou \(10^{-9}\). Takisto si dávajte pozor, aby ste ich vypisovali vo formáte pevnej desatinnej čiarky (0.00314), a nie v pohyblivej desatinnej čiarke (3.14e-03).

Súbory na stiahnutie

Ku každej z prvých štyroch testovacích sád vám dáme nápovedu – ku každej vám ukážeme testovaciu sadu, ktorá je síce iná, ale bola vygenerovaná rovnakým spôsobom. Dá sa preto očakávať, že má podobné vlastnosti. Tieto sady môžete nájsť na http://media.ksp.sk/ulohy/34rocnik/1kolo/T2-na-stiahnutie.zip.

Príklady

Input:

2

3
1
1 1

3
1
-1 1

Output:

0.000000000 0.000000000 1.000000000
0.500000000 0.500000000 0.000000000

V prvom teste sme našli optimálne riešenie – vždy vyberieme tretí vrchol, ktorý poráža všetky ostatné vrcholy. Žabova stratégia bude rovnaká, a vždy nastane remíza. V priemere tak získame \(0.5\) bodov. V druhom teste si Žaba zvolí stratégiu, pri ktorej vždy zvolí druhý vrchol. S \(50\)-percentnou šancou zvolíme vrchol \(1\), a Žaba získa bod. Vo zvyšnej polovici prípadov nastane remíza. V priemere tak získame \(0.25\) bodov.