「aoj2341～2350」の編集履歴（バックアップ）一覧に戻る

aoj2341～2350 - (2013/02/13 (水) 21:25:40) のソース

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

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

 #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";
 }