「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
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";
}
*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";
}