[UVa] 10223 - How many nodes ?

題目網址: http://goo.gl/SqJzmO

題意:
(from luckycat)


解 法: google 卡塔蘭數。

TAG: Catalan Number, 

注意: 要用 long long 喔

程式碼:

	/**
	* Tittle: 10223 - How many nodes ?
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/21
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <map>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	typedef long long ll;
	typedef map<ll,int> MLLI;
	// declarations
	ll n;
	MLLI treeToNode;
	ll catalan[50];
	// functions
	// main function
	int main( void )
	{
	// init
	treeToNode.clear();
	catalan[0] = 1;
	treeToNode[catalan[0]] = 0;
	FOR( i, 0, 19 ) {
	catalan[i+1] = catalan[i]*(4*i+2)/(i+2);
	treeToNode[catalan[i+1]] = i+1;
	}
	// input
	while( scanf( "%lld", &n )==1 ) {
	// output
	printf( "%d\n", treeToNode[n] );
	}
	return 0;
	}

view raw 10223 - How many nodes.cpp hosted with ❤ by GitHub