UVa:11375 Matches

백서의 예제.대수 덧셈을 썼다.이것은 n개의 성냥으로 몇 개의 정수를 세울 수 있느냐는 것을 묻는다. 즉 n개의 성냥보다 적을 때도 가능하다는 것이다.또한 선도 0의 상황에 주의해야 한다.
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
#define INF 2139062143
#define MOD 20071027
#define MAXN 20005
using namespace std;
int v[]= {6,2,5,5,4,5,6,3,7,6};
int w[]= {0,0,1,1,1,2,3,1,0,0};
void BigAdd(char *a,char *b,char *back)
{
    char c[500]= {0};
    int p=0,up=0;
    for(int i=strlen(a)-1,j=strlen(b)-1; i>=0||j>=0; --i,--j)
    {
        int x,y,z;
        if(i<0) x=0;
        else x=a[i]-'0';
        if(j<0) y=0;
        else y=b[j]-'0';
        z=(x+y+up)%10;
        up=(x+y+up)/10;
        c[p++]=z+'0';
    }
    if(up) c[p++]='1';
    c[p]=0;
    int q=0;
    for(int i=p-1; i>=0; --i)
        back[q++]=c[i];
    if(q==0) back[q++]='0';
    back[q]=0;
}

char f[2010][500];
char d[2010][500];
char temp[500]= {0};
void Init()
{
    strcpy(d[0],"1");
    for(int i=1; i<=2000; ++i)strcpy(d[i],"0");
    for(int i=0; i<=2000; ++i)
        for(int j=0; j<10; ++j)
            if(!(i==0&&j==0))
            BigAdd(d[i+v[j]],d[i],d[i+v[j]]);
    BigAdd(d[6],"1",d[6]);
    strcpy(f[0],"0");
    for(int i=1; i<=2000; ++i)
        BigAdd(d[i],f[i-1],f[i]);

}
int main()
{
    Init();
    int n;
    while(scanf("%d",&n)!=EOF)
        puts(f[n]);
    return 0;
}