HDU Train Problem II

简介:

Train Problem II

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 138 Accepted Submission(s): 80
Problem Description
As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.
 
Input
The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.
 
Output

            For each test case, you should output how many ways that all the trains can get out of the railway.
 
Sample Input
1
2
3
10
 
Sample Output
1
2
5
16796
Hint
The result will be very large, so you may not process it by 32-bit integers.

#include"stdio.h"
#include"string.h"
int ch[101][200]={0};

int temp[200]={0};

int add(int* x,int* y)
{
    int i;
    for(i=0;x[i]!=0&&y[i]!=0;i++)
    {
        x[i]+=y[i]-'0';
    }
    for(i;y[i]!=0;i++)
        x[i]+=y[i];
    int t;
    for(t=0;x[t]!=0;t++)
    {
        if(x[t+1]!=0)
            x[t+1]+=(x[t]-'0')/10;
        else
        {
            if((x[t]-'0')/10!=0)
                x[t+1]+=(x[t]-'0')/10+'0';
            else
                x[t+1]=0;
        }
        x[t]=(x[t]-'0')%10+'0';   
    }
    return t;
}
int* mul(int* x,int* y)
{
    for(int i=0;i<200;i++)
        temp[i]=0;
   
    for(int i=0;x[i]!=0;i++)
        for(int j=0;y[j]!=0;j++)
        {
            if(temp[i+j]!=0)
                temp[i+j]+=(x[i]-'0')*(y[j]-'0');
            else
                temp[i+j]+=(x[i]-'0')*(y[j]-'0')+'0';
           
        }
    int length=0;
    while(temp[length]!=0)
        length++;
    for(int t=0;t<length;t++)
    {
        temp[t+1]+=(temp[t]-'0')/10;
        temp[t]=(temp[t]-'0')%10+'0';
    }
    if(temp[length]!=0)
        temp[length]+='0';
    while(temp[length]!=0)
    {
        if((temp[length]-'0')/10!=0)
            temp[length+1]+=temp[length]/10+'0';
        temp[length]=(temp[length]-'0')%10+'0';
        length++;
    }

    return temp;
}

int main()
{
    ch[0][0]='1';
    ch[1][0]='1';

    for(int i=2;i<=100;i++)
    {
        for(int j=0;j<i;j++)
        {
            add(ch[i],mul(ch[j],ch[i-j-1]));
        }
    }
   
    int n,t=199;
    while(scanf("%d",&n)>0)
    {
        t=199;
        while(t>=0)
        {
            if(ch[n][t]!=0)
                printf("%c",ch[n][t]);
            t--;
        }

        printf("\n");
    }
    return 0;
}








本文转自NewPanderKing51CTO博客,原文链接:http://www.cnblogs.com/newpanderking/archive/2011/07/29/2121146.html ,如需转载请自行联系原作者






相关文章
|
Java
hdu 1022 Train Problem I【模拟出入栈】
hdu 1022 Train Problem I【模拟出入栈】
47 0
hdu 1022 Train Problem I【模拟出入栈】
HDOJ/HDU 1022 Train Problem I(模拟栈)
HDOJ/HDU 1022 Train Problem I(模拟栈)
120 0
HDOJ/HDU 1022 Train Problem I(模拟栈)
|
Java
HDU - 2018 Multi-University Training Contest 2 - 1004: Game
HDU - 2018 Multi-University Training Contest 2 - 1004: Game
101 0
HDOJ(HDU) 1898 Sempr == The Best Problem Solver?(水题、、、)
HDOJ(HDU) 1898 Sempr == The Best Problem Solver?(水题、、、)
125 0
【HDU 5572 An Easy Physics Problem】计算几何基础
2015上海区域赛现场赛第5题。 题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5572 题意:在平面上,已知圆(O, R),点B、A(均在圆外),向量V。
1036 0
|
C++
leetcode 37. Sudoku Solver 36. Valid Sudoku 数独问题
三星机试也考了类似的题目,只不过是要针对给出的数独修改其中三个错误数字,总过10个测试用例只过了3个与世界500强无缘了 36. Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
1204 0