试题描述
|
给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示: 注意: 1)加号与等号各自需要两根火柴棍 2)如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C>=0) 3)n根火柴棍必须全部用上 |
输入
|
共一行,又一个整数n(n<=24)。
|
输出
|
共一行,表示能拼成的不同等式的数目。
|
输入示例
|
【输入样例1】14
【输入样例2】18 |
输出示例
|
【输出样例1】2
【输出样例2】9 |
其他说明
|
【输入输出样例1解释】2个等式为0+1=1和1+0=1。
【输入输出样例2解释】9个等式为:0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11 |
好在这道题数据范围不算大,不然肯定超限。其他的,就是要注意:如果A≠B,则A+B=C与B+A=C视为不同的等式。
这道题要是一个数字一个数字枚举的话就太麻烦了,需要很多循环,因为A、B、C均可以是三位数。所以我们干脆就直接枚举A、B,C可以直接通过A+B算出,因此可以省掉一个循环 (补记于2017.10)
1 #include <iostream> 2 3 using namespace std; 4 int a[15]; 5 int main() 6 { 7 int t1=0,hh,t2=0,t=0,k=0,ans=0,n,i,j,h=0; 8 scanf("%D",&n); 9 a[0]=6;a[1]=2;a[2]=5;a[3]=5;a[4]=4;a[5]=5;a[6]=6;a[7]=3;a[8]=7;a[9]=6; 10 n-=4; 11 for(i=0;i<999;i++) 12 { 13 h=i; 14 if(h==0)t+=a[0]; 15 while(h>0) 16 { 17 t+=a[h%10]; 18 h/=10; 19 } 20 for(j=0;j<999;j++) 21 { 22 k=j; 23 if(k==0) t1+=a[0]; 24 while(k>0) 25 { 26 t1+=a[k%10]; 27 k/=10; 28 } 29 hh=i+j; 30 if(hh==0) t2+=a[0]; 31 while(hh>0) 32 { 33 t2+=a[hh%10]; 34 hh/=10; 35 } 36 if(t+t1+t2==n) ans++; 37 t1=0;t2=0; 38 } 39 t=0; 40 } 41 cout<<ans; 42 return 0; 43 }