rpi

Vous vous demandez quel superhéro est le plus fort. Après de nombreuses soirées télé vous avez pu remplir une grille indiquant si le superhéro X s’est déjà battu contre Y et s’il a gagné (chaque paire de héro s’est affronté au plus une fois, et personne ne s’affronte lui même). Ce- pendant certains héros ne se sont jamais affrontés. Vous décidez d’utiliser la formule du RPI utilisée dans les tournois de lycées américains pour calculer un score pour chaque superhéro. La formule est la suivante :

RPI = 0.25 × WP + 0.50 × OWP + 0.25 × OOWP

Avec :

L’entrée commence par un entier n ≤ 100, suivi d’un tableau n × n rempli avec « 0 » à la case (i, j) si le héro i a battu le héro j, « 1 » si c’est le héro j qui a battu le héro i et « . » s’ils ne se sont jamais rencontrés. Notez que si (i, j) contient 1 alors ( j, i ) contient 0. Pour chaque testcase vous devez afficher n lignes contenant le RPI de chaque superhéro à 10−3 près.

Input

3
.10
0.1
10.
4
.11.
0.00
01.1
.10.
10
...1.10...
..1....1.1
.0.....1..
0.....0.0.
.....1..0.
0...0.0.0.
1..1.1..0.
.00......0
...1111...
.0.....1..
8
.1..0.0.
0..0....
....1.1.
.1..01..
1.01...1
...0...1
1.0.....
....00..
5
.00.0
1.11.
10...
.0..1
1..0.
6
..011.
..0..1
11.0.1
0.1...
0....0
.00.1.
6
.11110
0.1..1
00..00
0...1.
0.10..
101...
6
.00.1.
1.00.1
11.1.0
.10.01
0..1..
.010..
4
.010
1.11
00.0
101.
8
.11.1100
0.1111.1
00.0000.
.01..100
001..101
00100.00
1.1111.1
10.1010.
3
.10
0.0
11.
10
..0.....0.
..1..0....
10........
......1..1
.....1...0
.1..0..0..
...0...1..
.....10.0.
1......1..
...01.....
10
.111111111
0.11111111
00.1111111
000.111111
0000.11111
00000.1111
000000.111
0000000.11
00000000.1
000000000.
7
.00....
1..0...
1...0..
.1...0.
..1...0
...1..0
....11.
8
.0....0.
1.10.0..
.0.....0
.1..0...
...1...1
.1....1.
1....0.1
..1.0.0.
10
.110111111
0.10000101
00.0000101
111.111111
0110.10111
01100.0111
011011.111
0000000.00
01100001.1
000000010.
10
.011111011
1.1.110101
00.0.00.01
0.1..00001
00....1000
0011..0101
011101.11.
10.1100.01
01111101.1
000010.00.
6
...0.0
...000
...0.1
111.1.
.1.0..
110...
9
.01100011
1.1001100
00.110011
010.10011
1100.1100
10110.100
101100.10
0100110.1
01001110.
10
.11.0.10.0
0.10.11.11
00.1000.0.
.10.1010.0
1.10.01..0
.0111.0011
001001.001
1..1.11.11
.01..010.0
10.110001.

Télécharger l'entrée

Output

0.500
0.500
0.500
0.646
0.368
0.604
0.396
0.425
0.694
0.500
0.463
0.505
0.378
0.562
0.306
0.641
0.500
0.330
0.222
0.922
0.538
0.632
0.361
0.653
0.276
0.264
0.736
0.500
0.708
0.292
0.580
0.523
0.632
0.648
0.222
0.316
0.620
0.586
0.340
0.544
0.347
0.552
0.524
0.509
0.553
0.470
0.432
0.479
0.458
0.625
0.375
0.542
0.555
0.545
0.374
0.460
0.514
0.407
0.603
0.550
0.500
0.375
0.625
0.281
0.417
0.250
0.969
0.417
0.354
0.688
0.444
0.500
0.781
0.625
0.597
0.569
0.542
0.514
0.486
0.458
0.431
0.403
0.375
0.000
0.188
0.250
0.500
0.750
0.812
1.000
0.302
0.391
0.177
0.667
0.792
0.760
0.562
0.451
0.597
0.458
0.431
0.625
0.542
0.514
0.569
0.375
0.486
0.403
0.559
0.563
0.419
0.437
0.455
0.507
0.573
0.509
0.560
0.374
0.438
0.333
0.688
0.672
0.500
0.354
0.500
0.500
0.500
0.500
0.500
0.500
0.500
0.500
0.500
0.511
0.520
0.373
0.500
0.460
0.539
0.456
0.647
0.474
0.536

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.