시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Pewien niedoceniany wynalazca zbudował egzotyczny układ mechaniczny, składający się z kół zębatych o zróżnicowanych średnicach. Każde koło zębate ma stronę białą i stronę czarną. Koła zębate wchodzące w skład egzotycznego układu mechanicznego mogą być łączone na cztery sposoby:
Przykładowe połączenia różnych typów zobrazowano na rysunku.
Zakładamy, że dany egzotyczny układ mechaniczny zawsze da się zbudować. Niedoceniani wynalazcy mają swoje sposoby, aby np. połączyć zębatkami koło zębate o średnicy 1 z setkami innych kół zębatych o średnicy 1. W kwestii budowania egzotycznych układów mechanicznych nie ma dla nich rzeczy niemożliwych.
Niedoceniany wynalazca nie uruchomił jeszcze swojego egzotycznego układu mechanicznego. Boi się, że, gdy spróbuje wprawić go w ruch, układ nie zadziała. Nie wie też, czy prędkości, z jakimi będą się kręciły koła zębate, są odpowiednie. Dlatego niedoceniany wynalazca przekazał Tobie schemat swojego układu i poprosił o pomoc. Początkowo żadne koło zębate nie porusza się. Oblicz, jakie będą prędkości kątowe kół zębatych, gdy do koła zębatego nr 1 podłączony zostanie napęd, lub stwierdź, że koło zębate nr 1 nie może się obracać. Napęd powoduje, że, jeśli koło zębate nr 1 nie jest zablokowane, to kręci się z prędkością kątową o wartości 1 obrót na sekundę.
A... i zapomniałbym! Za rysunki dziękujemy Dobrosi.
W pierwszej linii wejścia podana jest liczba testów d (1 ≤ d ≤ 100). Dalej podane są testy.
Każdy test odpowiada jednemu egzotycznemu układowi mechanicznemu. Pierwsza linia każdego testu zawiera liczbę kół zębatych n oraz liczbę połączeń pomiędzy nimi m (1 ≤ n ≤ 1000).
W kolejnych n liniach podane są rozmiary kolejnych (i = 1..n) kół zębatych. Średnica koła zębatego si jest liczbą całkowitą z przedziału od 1 do 100.
W kolejnych m liniach znajdują się opisy połączeń między kołami zębatymi. Opis połączenia składa się z dwóch różnych liczb x oraz y oznaczających numery kół zębatych (1 ≤ x, y ≤ n) oraz litery określającej sposób połączenia: ’a’, ’b’, ’A’ lub ’B’. Dana para numerów kół zębatych wystąpi na wejściu co najwyżej raz.
Dla każdego testu, wypisz w osobnej linii prędkości kątowe kolejnych kół zębatych lub słowo NIE. Prędkości podaj w liczbie obrotów na sekundę. Wynik zaokrąglij do dwóch cyfr po przecinku. Dla każdego koła zębatego możesz się pomylić o co najwyżej 0,01. Jeśli dla danego układu koło zębate nr 1 nie może się obracać, zamiast prędkości wypisz w osobnej linii słowo NIE.
3 3 1 1 2 3 1 3 B 3 2 1 2 3 1 3 A 2 3 A 3 3 1 2 3 1 2 B 2 3 B 1 3 B
1.00 0.00 0.33 1.00 1.00 1.00 NIE