标签存档: SGU130

SGU 130 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=130

130. Circle

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

On a circle border there are 2k different points A1, A2, ..., A2k, located contiguously. These points connect k chords so that each of points A1, A2, ..., A2k is the end point of one chord. Chords divide the circle into parts. You have to find N - the number of different ways to connect the points so that the circle is broken into minimal possible amount of parts P.

在圆上有 2k 个不重合的点 A1, A2, ..., A2k, 通过这些点可以作k条弦,使得每个点都恰好属于一条弦。这样我们就把这个圆分成了很多区域,你要求出 N 个方案数,使这些弦将圆划分的区域数量最小。

Input

The first line contains the integer k (1 <= k <= 30).

输入 K.

Output

The first line should contain two numbers N and P delimited by space.

输出方案数量和最少的区域数量,用空格隔开。

继续阅读 »