시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 61 39 37 71.154%

문제

백제의 의자왕이 궁궐 앞마당에 몇 명의 궁녀들을 일렬로 세웠다. 백제의 궁궐에는 총 3,000명의 궁녀가 있지만 아쉽게도 궁궐 앞마당은 좁기 때문에 의자왕은 N명의 궁녀들을 세웠다.

의자왕은 N명의 궁녀들을 꽃단장하려고 한다. 이 과정에서 뒤에 있는 사람이 앞에 있는 사람의 머리를 볼 수 있으면 조금 더 수월하게 작업을 할 수 있다. 한 사람은 자신의 앞에 있는 사람 중 자신보다 키가 작은 사람의 머리만 볼 수 있으며, 앞에 자신보다 키가 크거나 같은 사람이 있더라도 그 앞에 있는 키가 작은 사람들의 머리를 볼 수 있다.

궁녀들은 50%의 확률로 일어서 있거나 의자에 앉아 있다. 이때 N명의 궁녀들이 앉거나 일어서는 것은 독립적이다. 의자왕은 궁녀들이 앉을 지 설 지 모르므로 궁녀들이 다른 궁녀들의 머리를 보는 경우의 수를 알 수는 없지만 평균적으로 얼마나 많이 머리를 볼 수 있는지는 알 수 있다. 따라서 의자왕은 궁녀들이 다른 궁녀의 머리를 보는 경우의 수의 기댓값이 최대한 늘어나도록 궁녀들의 순서를 재배치하려고 한다.

의자왕이 최적의 방법으로 궁녀들을 앉힐 때, 한 사람이 앞 사람의 머리를 볼 수 있는 경우의 수의 기댓값의 최댓값을 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 궁녀의 수 N이 주어진다. (2 ≤ N ≤ 3,000)

두 번째 줄부터 N개의 줄에는 각 궁녀의 앉은키 Si와 키 Hi가 주어진다. 궁녀들의 정보는 뒤에 있는 궁녀부터 순서대로 주어진다. (1 ≤ Si < Hi ≤ 10,000)

출력

한 사람이 앞 사람의 머리를 볼 수 있는 경우의 수의 기댓값의 최댓값을 출력한다. 정답과의 오차가 0.001 이하인 경우 정답 처리한다.

예제 입력

6
10 11
4 5
8 9
4 5
12 13
2 3

예제 출력

14.25

힌트

출처

Contest > FunctionCup > FunctionCup 2016 K번