시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 7 | 5 | 4 | 66.667% |
W pewnym mieście odbywa się turniej sztuk walki. Startuje w nim N zawodników, z czego dwóch stanowią bracia - Olek i Felek.
W turniejowych pojedynkach bierze udział po dwóch zawodników i każdy pojedynek ma jednego zwycięzce, który pozostaje w turnieju, podczas gdy przegrany odpada. Układ pojedynków ilustruje "drzewo turniejowe" ustalane przed zawodami. Poniżej prezentujemy przykładowe drzewo turniejowe dla turnieju z czterema zawodnikami. W żółtych polach "zaczynają" zawodnicy, zielone pola oznaczają pojedynki.
Na początku turnieju zawodnicy rozlosowywani są po pozycjach startowych, i każde przyporządkowanie zawodników do żółtych pól jest tak samo prawdopodobne.
Co więcej, w tym roku poziom jest tak wyrównany, że należy przyjąć, że każdy pojedynek z równym prawdopodobieństwem zostanie wygrany przez każdego z dwóch biorących w nim udział zawodników.
Oblicz prawdopodobieństwo, że w toku turnieju bracia Olek i Felek będą ze sobą walczyć.
W pierwszej linii znajduje się liczba zestawów testowych Z ( 1 <= Z <= 5 ). Następnie podawane są opisy kolejnych zestawów.
Opis zestawu rozpoczyna się od liczby naturalnej N ( 2 <= N <= 1000 ) określającej liczbę zawodników w turnieju. Następnie podawane są opisy wszystkich N-1 pojedynków turniejowych ( numerowanych kolejno od 1 do N-1 ), po jednym w linii.
Opis pojedynku składa się z dwóch oddzielonych spacją ciągów znaków, każdy z nich opisuje jednego z zawodników walczących w pojedynku.
Można przyjąć, że opis tworzy poprawne drzewo turniejowe, tj. każda pozycja startowa przypisana jest dokładnie do jednego pojedynku i zwycięzca każdego pojedynku poza jednym przypisany jest do dokładnie jednego pojedynku.
Dla każdego zestawu należy wypisać w osobnej linii prawdopodobieństwo, że w Olek z Felkiem będą ze sobą walczyć z dokładnością do 0.0001.
1 4 P2 Z4 P3 Z1 Z2 Z3
0.5
Contest > Spot > HotSpot 2010 3-1번