시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB80281932.203%

문제

영선이는 나무 N개를 일렬로 심었다. 각각의 나무는 0번부터 N-1번까지 번호가 매겨져 있다. i번째 나무가 모두 자라면, 높이는 low[i]와 high[i]를 포함하는 그 사이의 정수가 되며, 각 정수가 선택될 확률은 모두 같다.

영선이는 교차 수열을 매우 좋아하며, 교차 수열의 정의는 다음과 같다.

  • 길이가 1인 수열은 교차 수열이다.
  • 길이가 2인 수열 (A, B)는 A ≠ B를 만족하면 교차 수열이다.
  • 길이가 3인 수열 (A, B, C)는 A < B와 B > C를 만족하거나, A > B와 B < C를 만족하면 교차 수열이다.
  • 길이가 L > 3인 수열 (A[0], A[1], ..., A[L-1])은 모든 연속한 세 쌍이 교차 수열일 때 교차 수열이다. 즉, (A[0], A[1], A[2]), (A[1], A[2], A[3]), ..., (A[L-3], A[L-2], A[L-1])dl 모두 교차 수열이어야 한다.

교차 수열의 아름다움을 인접한 원소의 차이의 합이다. 예를 들어, 교차 수열 (A[0], A[1], ..., A[L-1])의 아름다움은 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[L-2] - A[L-1]| 이다. 길이가 1인 교차 수열의 아름다움은 0이다.

나무가 모두 자란 뒤에, 영선이는 0번 나무부터 N-1번 나무까지의 높이를 공책에 적었다. 만약 이 수열이 교차 수열이라면 영선이는 수열을 그대로 놔둘 것이다. 교차 수열이 아닌 경우에는 일부 수를 지워서 교차 수열로 만들 것이다. 만약, 교차 수열을 만들 수 있는 방법이 여러 가지라면, 아름다움이 크게 되도록 수를 지울 것이다. 이렇게 해서 만든 수열을 결과 수열이라고 한다.

결과 수열의 아름다움의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄부터 N개의 줄에는 low[i]와 high[i]가 주어진다. (1 ≤ low[i] ≤ high[i] ≤ 100,000)

출력

결과 수열의 아름다움의 기댓값을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

예제 입력 1

1
1 100

예제 출력 1

0.0

예제 입력 2

3
1 2
1 2
1 2

예제 출력 2

1.0

예제 입력 3

5
1 2
3 4
5 6
7 8
9 10

예제 출력 3

8.0

힌트

예제 2의 경우에 나무가 자란 결과는 총 8가지가 가능하다.

  • (1, 1, 1)과 (2, 2, 2)는 수 2개를 지워야 교차 수열이 되고, 아름다움은 0이다.
  • (1, 1, 2), (2, 2, 1), (1, 2, 2), (2, 1, 1)의 경우에는 가운데 수를 지우면 된다. 이때, 아름다움은 1이다.
  • (1, 2, 1)과 (2, 1, 2)의 경우에는 수를 지우지 않아도 된다. 이때, 아름다움은 2이다.

따라서, 기댓값은 (4/8)*1 + (2/8)*2 = 1이 된다.

출처