MCIRGAME - Point Connection Game in a Circle


This is a small but ancient game. You are supposed to write down the 
numbers 1, 2, 3, . . . , 2n − 1, 2n consecutively in clockwise order
on the ground to form a circle, and then, to draw some straight line
segments to connect them into number pairs. Every number must be connected
to exactly one another.
And, no two segments are allowed to intersect. It’s still a simple game, isn’t it? 
But after you’ve written down the 2n numbers, can you tell me in how
many different ways can you connect the numbers into pairs? Life is harder, right!

Input

Each line of the input file will be a single positive number n, except 
the last line, which is a number −1.
You may assume that 1 ≤ n ≤ 150.

Sample Input
2
-1

Output

 
For each n, print in a single line the number of ways to connect the 2n
numbers into pairs.

Sample output
2
Note : Big num!

hide comments
phoemur: 2018-11-02 20:46:10

In C++ you'll need an integer with 512 bits to hold the result for the given range.
You could store it as an array and homebrew your own multiplication and division functions.
However it is much easier to use Boost::multiprecision.

babur: 2018-06-22 20:16:06

Done using Pyhton. Has anyone solved it using c++. If yes, please share your approach.

karthik_vg: 2018-02-04 05:35:43

catalan using java BigInts (y)

kshubham02: 2017-09-04 11:58:54

MOD should have been given :/

Anuva Agarwal: 2014-10-20 21:31:05

python made it pretty easy :D

nitesh kumar: 2014-07-25 14:07:14

simple dp plot the points on st line the try to solve subproblems!!

Anubhav Balodhi : 2014-03-30 15:34:17

One of the most famous sequences in Mathematics... great one ;-)

Nitish sharma: 2013-10-29 20:43:03

Getting runtime error..any reason??
How can blank spaces relate to runtime error

Last edit: 2013-10-29 20:43:46
@looser@: 2013-08-08 19:09:20

nice one

Codeblooded: 2013-08-08 14:15:18

does the answer require BigInt???


Added by:~!(*(@*!@^&
Date:2009-02-23
Time limit:0.170s-0.654s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Pre Shanghai 2004