Podsłowa

25.11.2011

Podsłowa

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Chodnik przed szkołą kolejny raz został pokryty grubą warstwą opadłych liści. Obowiązkiem aktualnych dyżurnych, Hektora i Wiktora, jest ich zagrabienie. Chłopcy, nie mogąc ustalić kto powinien zająć się liściowym problemem, postanowili ciągnąć dość nietypowe losy. Najpierw uzgodnili między sobą jedno słowo składające się z N małych liter alfabetu angielskiego, którego wszystkie możliwe niepuste podsłowa wrzucili do urny. Następnie obaj podchodzą do urny i losują bez zwracania po jednym słowie (najpierw Hektor, potem Wiktor). Grabić liście będzie ten, którego wylosowane słowo jest mniejsze leksykograficznie. Jeśli obaj wylosują takie same słowa, każdy zagrabi po połowie chodnika. Jaka jest szansa, że do tego dojdzie?

Wejście

W pierwszej linii znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii pojedynczego zestawu testowego znajduje się jedna liczba całkowita N ( 2 <= N <= 50 000 ), określająca liczbę liter wybranego przez chłopców słowa. W drugiej linii znajduje się to słowo.

Wyjście

Dla każdego zestawu testowego należy w jednej linii wypisać jedną liczbę wymierną, będącą prawdopodobieństwem tego, że losowanie zakończy się remisem. Liczbę tę należy wypisać w postaci "licznik / mianownik", gdzie licznik i mianownik są liczbami względnie pierwszymi.

Przykład

Wejście Wyjście

5
2
aa
2
uv
3
aaa
4
fall
4
spot

1 / 3
0 / 1
4 / 15
1 / 45
0 / 1

Wyjaśnienie przykładu

W trzecim zestawie testowym słowo ma dokładnie 6 podsłów: a [1:1], aa [1:2], aaa [1:3], a [2:2], aa [2:3], a [3:3] (w nawiasach podano zakres indeksów, któremu dane podsłowo odpowiada). Jest 30 możliwych wyników losowania, ale tylko 8 z nich prowadzi do remisu (pierwsza liczba z pary oznacza nr podsłowa wylosowany przez Hektora, druga liczba to nr podsłowa Wiktora): (1,4), (1,6), (4,1), (4,6), (6,1), (6,4), (2,5), (5,2).

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com