TopCoder

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Description

現在給你許多塊的積木,每一塊積木的頂面和底面都是正方形,並且頂面一定會比底面還大

你現在要把這些積木全部堆成一疊,使得任何兩個接觸的積木的面都要滿足,上面的面不會比下面的面還大,這樣這一堆積木才能維持平衡而不會倒下。

請問你有幾種不同的堆法呢?

Input Format

本題只有一筆測試資料。

第一行有一個正整數 n ( 0 < n <= 1000 ),表示你面前共有 n 塊積木。

接下來有 n 行,每行有兩個數字 ai, bi ( 0 < ai < bi <= 10,000,000 ) ,表示第 i 塊積木的底面和頂面面積分別為 ai, bi

Output Format

請輸出共有幾種堆法滿足任何兩個接觸的積木的面,上面的面不會比下面的面還大。

因為每塊積木都有不同的顏色,你可以當他們全部都是不同的。

Sample Input

3
1 3
2 4
3 5

Sample Output

6

Hints

Problem Source

原TIOJ1453 / 建中校內培訓第三次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1200 65536 262144
1 1200 65536 262144
2 1200 65536 262144
3 1200 65536 262144
4 1200 65536 262144
5 1200 65536 262144
6 1200 65536 262144
7 1200 65536 262144
8 1200 65536 262144
9 1200 65536 262144
10 1200 65536 262144