TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

71.4% (5/7)

Tags

Description

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

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

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

Input Format

本題只有一筆測試資料。

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

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

Output Format

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

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

Sample Input 1

3
1 3
2 4
3 5

Sample Output 1

6

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1200 65536 262144 1
1 1200 65536 262144 2
2 1200 65536 262144 3
3 1200 65536 262144 4
4 1200 65536 262144 5
5 1200 65536 262144 6
6 1200 65536 262144 7
7 1200 65536 262144 8
8 1200 65536 262144 9
9 1200 65536 262144 10
10 1200 65536 262144 11