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();
}