※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

2350 A-B Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2350
A-Bで桁の繰り下がりを最大K回まで忘れた場合A-Bの最大値は幾らになるか?

解法
問題で指定されたとおりに実装します。
探索空間が狭いので全探索で答えが出ます。
この問題数万桁とかになったらどう解くか結構難しそうな問題になりそうです。

#include<stdio.h>
#include<string>
#include<iostream> 

std::string ans="";
int borrow[13]={0};
 
void saiki(char a[20],char b[20],char c[20],int k,int count,int p){
	if(p==0){
		std::string str1=c;
		if(ans<str1)ans=str1;
		return ;
	}
	if(a[p]-borrow[p]>=b[p]){
		c[p]=a[p]-b[p]-borrow[p]+'0';
		borrow[p-1]=0;
		saiki(a,b,c,k,count,p-1);
	}else{
		c[p]=(a[p]-borrow[p]-b[p]+10)+'0';
 		borrow[p-1]=1;
		saiki(a,b,c,k,count,p-1);
		borrow[p-1]=0;
		if(k>count)saiki(a,b,c,k,count+1,p-1);
	}
}

int main(){
	char t1[20],t2[20],a[20],b[20],c[20]="0123456789abc";
	int k;
	scanf("%s %s %d",t1,t2,&k);
	sprintf(a,"%13s",t1);
	sprintf(b,"%13s",t2);
	for(int i=0;a[i]!='\0';i++)if(a[i]==' ')a[i]='0';
	for(int i=0;b[i]!='\0';i++)if(b[i]==' ')b[i]='0';
	saiki(a,b,c,k,0,12);
	int i;
	for(i=0;ans[i]=='0';i++);
	std::cout<<ans.substr(i)<<"\n";
}