Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWPZ06B - Przedziały |
Oznaczenie 1:
P(X) – rodzina wszystkich podzbiorów danego zbioru.
Oznaczenie 2:
R – zbiór liczb rzeczywistych
Z – zbiór liczb całkowitych
Oznaczenie 3:
(x, y) – przedział obustronnie otwarty [x, y] – przedział obustronnie domknięty
(x, y] – przedział prawostronnie domknięty [x, y) – przedział lewostronnie domknięty
Definicja 4:
Funkcja g określona na P(R) ma własność S jeśli spełnia następujące warunki:
(i) g(∅) = 0
(ii)
Zadanie
Weźmy funkcję f : P(R) → Z, która ma własność S. Wiemy, że dla każdego x ∈ Z oraz dla każdego ε ∈ (0, 1/2) zachodzą następujące warunki:
(i)
(ii)
Mamy dany ciąg przedziałów. Trzeba obliczyć, ile wynosi wartość funkcji f na sumie oraz iloczynie tych przedziałów.
Wejście
Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 500) oznaczającą liczbę zestawów danych. W pierwszej linii zestawu znajduje się jedna liczba całkowita N (1 ≤ N ≤ 105) – liczba przedziałów, które są dane. W następnych N wierszach znajdują się opisy tych przedziałów zgodne z oznaczeniem 3. Każdy ograniczony jest dwoma liczbami rzeczywistymi X i Y (-2*109 ≤ X ≤ Y ≤ 2*109) oddzielonymi średnikiem. Każda liczba podana jest z dokładnością co najmniej 1, a co najwyżej 10 cyfr po przecinku. Wszystkie liczby otoczone są pojedynczymi spacjami.
Wyjście
Dla każdego zestawu danych należy wypisać dwie linie. W pierwszej wartość funkcji f na sumie wszystkich przedziałów, które pojawiły się na wejściu. W drugiej trzeba podać wartość funkcji f na iloczynie wszystkich przedziałów, które pojawiły się na wejściu.
Przykład
Wejście:
1
4
( 1,1 ; 11,2 )
[ 2,23344 ; 3,444444 )
( 2,0 ; 4,18 ]
[ 2,0 ; 10,1 ]
Wyjście:
10
1
Dodane przez: | Rafal Nowak |
Data dodania: | 2006-12-07 |
Limit czasu wykonania programu: | 1s-3s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: GOSU |
Pochodzenie: | Mistrzostwa Wielkopolski w Programowaniu Zespołowym, 2006 |