How Many Equations Can You Find
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 714 Accepted Submission(s): 467
Problem Description
Now give you an string which only contains 0, 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9.You are asked to add the sign ‘+’ or ’-’ between the characters. Just like give you a string “12345”, you can work out a string “123+4-5”. Now give you an integer N, please tell me how many ways can you find to make the result of the string equal to N .You can only choose at most one sign between two adjacent characters.
Input
Each case contains a string s and a number N . You may be sure the length of the string will not exceed 12 and the absolute value of N will not exceed 999999999999.
Output
The output contains one line for each data set : the number of ways you can find to make the equation.
Sample Input
123456789 3
21 1
21 1
Sample Output
18 1
题解，在一串数字内加+或-，使其等于N的方法数，深搜；
代码：
#include<stdio.h>
#include<string.h>
__int64 ans,N;
int len;
char s[];
void dfs(int t,__int64 sum){
if(t==len){
//printf("%I64d\n",sum);
if(sum==N)ans++;
return;
}
__int64 k=;
for(int i=t;i<len;i++){
k=k*+s[i]-'';
dfs(i+,sum+k);
if(t!=)dfs(i+,sum-k);
}
}
int main(){
while(~scanf("%s%I64d",s,&N)){
len=strlen(s);
ans=;
dfs(,);
printf("%I64d\n",ans);
}
return ;
}
/*#include<stdio.h>
#include<string.h>
__int64 ans,N;
int len;
char s[15];
void dfs(int top,__int64 sum){
if(top==len){//写成N了错的心酸。。。
//printf("%I64d %d\n",sum,len);
if(sum==N)ans++;
return ;
}
__int64 x=0;
for(int i=top;i<len;i++){
x=x*10+s[i]-'0';
dfs(i+1,sum+x);
if(top!=0)dfs(i+1,sum-x);
}
}
int main(){
while(~scanf("%s%I64d",s,&N)){
len=strlen(s);
//printf("%d\n",len);
ans=0;
dfs(0,0);
printf("%I64d\n",ans);
}
return 0;
}*/