Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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) Drugi warunek

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) Warunek pierwszy

(ii) Drugi warunek

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łowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Mistrzostwa Wielkopolski w Programowaniu Zespołowym, 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.