CATALAN - Dãy số Catalan
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long LL;
#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)
#define INF 1000000000
#define N 20
#define F(i,j) (i >= 0 && i <= n+n && j >= 0 && j <= n ? f[i][j] : 0)
LL f[N+N][N]; int n;
int a[N+N], pos;
bool finish;
void dfs(int i, int lo, int hi) {
printf("%d %d %d\n", i, lo, hi);
if( lo > hi || lo > pos || hi < pos ) return;
if( i == n+n ) {
if( lo == hi && lo == pos ) {
printf("0");
fo(i,1,n+n) printf(" %d", a[i]); putchar(10);
finish = 1;
}
} else {
a[i] = a[i-1]-1; dfs(i+1, lo, F(i,a[i-1]-1));
if(finish) return;
a[i] = a[i-1]+1; dfs(i+1, F(i,a[i-1]-1), hi);
if(finish) return;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
#endif
scanf("%d",&n);
f[n+n][0] = 1;
repd(i,n+n) fo(j,0,n) f[i][j] = F(i+1,j+1) + F(i+1,j-1);
//fo(j,0,n) {fo(i,0,n+n) printf("%3lld ", f[i][j]); putchar(10);}
rep(i,n+n+1) scanf("%d",a+i);
pos = 0;
fo(i,1,n+n)
if(a[i] > a[i-1]) pos += F(i,a[i]-2);
else pos += F(i,a[i]-1);
printf("%d\n", pos+1);
scanf("%d",&pos);
a[0] = 0; a[1] = 1;
fo(i,2,n+n) {
if(pos <= F(i,a[i-1]-1)) {
a[i] = a[i-1]-1;
} else {
pos -= F(i,a[i-1]-1);
a[i] = a[i-1]+1;
}
}
printf("%d", a[0]);
fo(i,1,n+n) printf(" %d", a[i]); putchar(10);
return 0;
}