`
zhouxiaojie
  • 浏览: 8805 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
最近访客 更多访客>>
社区版块
存档分类
最新评论

spoj 11575. A Famous Equation

    博客分类:
  • spoj
阅读更多
https://www.spoj.pl/problems/EQ2/
我的做法在这个网站上能过,但是过不了杭电的,郁闷了很久。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[100],b[100],c[100];
char str[105];
int aa,bb,cc;
long long suma,sumb,sumc;
long long f[105][2];
int main()
{
    int i,j,k,t,cas=0,ss,tt;
    while(scanf("%s",str)!=EOF)
    {
        cas++;
        int len = strlen(str);
        aa=1;bb=1;cc=1;k=0;
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        suma=0,sumb=0,sumc=0;
        int ttt=0;
        for(i=len-1;i>=0;i--)
        {
            if(str[i]=='=')break;
            if(str[i]=='?')ttt=1,c[cc++]=-1;
            else
            c[cc++]=str[i]-'0';
        }i--;k=max(k,cc);
        for(;i>=0;i--)
        {
            if(str[i]=='+')break;
            if(str[i]=='?')ttt=1,b[bb++]=-1;
            else
            b[bb++]=str[i]-'0';
        }i--;k=max(k,bb);
        for(;i>=0;i--)
        {
            if(str[i]=='?')ttt=1,a[aa++]=-1;
            else
            a[aa++]=str[i]-'0';
        }
        k=max(k,aa);
        int sa,ea,sb,eb,sc,ec;
        int flag=0,state=0;
        for(int l=1;l<k;l++)
        {
            if(state)break;
            sa=a[l]<0?((l<aa-1||aa==2)?0:1):a[l];
            ea=a[l]<0?9:a[l];
            sb=b[l]<0?((l<bb-1||bb==2)?0:1):b[l];
            eb=b[l]<0?9:b[l];
            sc=c[l]<0?((l<cc-1||cc==2)?0:1):c[l];
            ec=c[l]<0?9:c[l];
            if(flag==0)
            {
                ss=f[l][0],tt=f[l][1];
                for(i=sa;i<=ea;i++)
                {
                    for(j=sb;j<=eb;j++)
                    {
                        for(t=sc;t<=ec;t++)
                        {
                            if(i+j==10+t&&f[l-1][1]==0)
                              f[l][1]++;
                            if(i+j==t&&f[l-1][1]==0)
                              f[l][0]++;
                            if(f[l-1][1]&&i+j+1==10+t)
                              f[l][1]++;
                            if(f[l-1][1]&&i+j+1==t)
                              f[l][0]++;
                            if(f[l][0]>ss)flag=1;
                            if(f[l][1]>tt)flag=1;
                        }
                    }
                }
                if(ss==f[l][0]&&tt==f[l][1])
                {
                    state=1;break;
                }
                continue;
            }
            ss=f[l][0],tt=f[l][1];
            for(i=sa;i<=ea;i++)
            {
                for(j=sb;j<=eb;j++)
                {
                    for(t=sc;t<=ec;t++)
                    {
                        if(i+j==10+t)
                          f[l][1]+=(f[l-1][0]);
                        if(i+j==9+t)
                          f[l][1]+=(f[l-1][1]);
                        if(i+j==t)
                          f[l][0]+=(f[l-1][0]);
                        if(i+j+1==t)
                          f[l][0]+=(f[l-1][1]);
                    }
                }
            }
            if(ss==f[l][0]&&tt==f[l][1])
            {
                state=1;break;
            }
        }
        if(state)
        printf("Case %d: 0\n",cas);
        else
        printf("Case %d: %lld\n",cas,f[k-1][0]);
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics