JEDNAKOS - JEDNAKOST

Tác giả: hieult

Ngôn ngữ: C++

#include <cstdio>
#include <ctype.h>
//#include <conio.h>

char a[1111];
int alen,sum;

void Enter()
{
     int c;
     while(!isdigit(c=getchar()));
     alen = 0;
     do a[alen++] = c; while(isdigit(c=getchar()));
     a[alen]='\0';
     while(!isdigit(c=getchar()));
     sum = 0;
     do sum=10*sum+c-'0';while(isdigit(c=getchar()));
}

int min[5555][1025];

int tinh(int tong,int vitri)
{
    int result = 1000000000;
    int i,num,t;
    if(min[tong][vitri]) return min[tong][vitri];
    if(vitri == alen)
    {
        if(tong==0) return 0;
        else return result;
    }
    if(a[vitri]=='0')
    {
        if(vitri == alen-1)
        {
            if(tong ==0) return 1;
            else return result;
        }
        else return tinh(tong,vitri+1);
    }
    for(num=0,i=vitri;i<alen;i++)
    {
        if((num=10*num+a[i]-'0')>tong) break;
        if((t=1+tinh(tong-num,i+1))<result) result = t;
    }
    return (min[tong][vitri] = result);
}

int main()
{
   // freopen("JEDNAKOS.in","r",stdin);
    Enter();
    printf("%d\n",tinh(sum,0)-1);
    //getch();
}

Download