Runda 4: Prestiż

24.06.2009

Zawód matematyka to ciężki orzech. Jednak jak to zwykle w życiu bywa "każdy orze jak może". Ostatnio zająłeś się zupełnie nową, niezbadaną teorią. Wypisałeś sobie wszystkie ciekawe twierdzenia, które jej dotyczą oraz zależności typu "jeśli ktoś udowodni twierdzenie A to natychmiast znajdzie się jakiś cwaniak i udowodni twierdzenie B (niestety na pewno to nie będziesz Ty!!!)", oczywiście w przypadku jeśli B nie zostało wcześniej już udowodnione.

Z każdym twierdzeniem związany jest prestiż, jaki się zyskuje za udowodnienie go po raz pierwszy. Prestiż mierzymy za pomocą liczby całkowitej. Jak to prawdziwy matematyk chciałbyś doprowadzić do rozwiązania całej teorii, tzn. do udowodnienia wszystkich twierdzeń. Jednak, jako twórca teorii chciałbyś dodatkowo zyskać jak największy współczynnik prestiżu. Współczynnik prestiżu mierzymy, jako suma prestiżu uzyskanego za udowodnione przez Ciebie twierdzenia dzielone przez liczbę udowodnionych przez Ciebie twierdzeń. Uwaga Ty możesz udowodnić dowolne twierdzenie, natomiast ktoś inny może udowodnić twierdzenie B, wtedy i tylko wtedy gdy ktoś udowodni twierdzenie A oraz wypisałeś zależność "jeśli A to B".

Wejście

W pierwszym wierszu znajdują się dwie liczby 1<=n<=100000 i 0<=m<=1000000 oznaczające liczbę twierdzeń oraz liczbę zależności. W następnej linii znajduje się n liczb całkowitych, co do modułu mniejsze od 2001 oznaczające prestiż dla kolejnych twierdzeń (dla ułatwienia twierdzenia utożsamiamy z liczbami całkowitymi z przedziału [1..n]). W kolejnych m wierszach znajdują się dwie liczby całkowite A B oznaczające zależność jeśli A to B.

Wyjście

Największy możliwy współczynnik prestiżu do uzyskania (spełniając warunki zadania) wypisany z dokładnością do 5 cyfr po przecinku.

Przykład

Dla danych wejściowych

6 7
-1 1 1 1 -1 1
1 2
2 3
3 2
3 4
4 5
6 3
3 6

poprawną odpowiedzią jest

0.33333

Żeby uzyskać to najpierw udowodniamy 4 za 1pkt i ktoś za nas dowodzi 5. Potem dowodzimy 2 (za 1pkt) i ktoś za nas dowodzi 3 i 6. Na koniec musimy udowodnić 1 za -1pkt. Więc (1+1-1) / 3 = 0.33333

kod: PRESTIZ, limity: 5 s, 64 MB

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com