洛谷 P1149 火柴棒等式

洛谷 P1149 火柴棒等式

链接

https://www.luogu.org/problemnew/show/P1149

题目

题目描述

给你n根火柴棍,你可以拼出多少个形如”A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:

![](https://cdn.luogu.org/upload/pic/49.png)

注意:

  1. 加号与等号各自需要两根火柴棍

  2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A,B,C>=0)

  3. n根火柴棍必须全部用上

输入输出格式

输入格式:

一个整数n(n<=24)。

输出格式:

一个整数,能拼成的不同等式的数目。

输入输出样例

输入样例#1:

  14

输出样例#1:

  2

输入样例#2:

  18

输出样例#2:

  9

说明

【输入输出样例1解释】

2个等式为0+1=10+1=1和1+0=11+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  

思路

思路也挺清晰的,直接遍历,0-9的火车不一样,用数组记录,借助count函数寻找ABC需要的火柴,二重循环遍历找的所有合适的解。

1100:数字随手写的,因为上限只有24,只有20根可以组成数字,按照929分组,只能有四个大于1000的数:7111,1711,1171,1117,这四个数都无法得到等式,所以构成结果的ABC一定都小于1000,所以这里写1000即可。其实可以算出上限还要低一点,不过也没啥大问题,用1000就行。

(最近有点忙,所以没想啥骚操作)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>

using namespace std;

int num[10] = {6,2,5,5,4,5,6,3,7,6};

int count(int x)
{
if(x==0)
return num[0];
int res=0;
while(x)
{
res = res + num[x%10];
x = x / 10;
}
return res;
}

int main()
{
int n;
int sum=0;
cin>>n;
n=n-4;
if(n<=8)
{
cout<<"0";
return 0;
}

for(int i=0;i<1100;i++)
{
for(int j=0;j<1100;j++)
{
int k = i + j;
if(count(i)+count(j)+count(k)==n)
sum++;
}
}
cout<<sum<<endl;
return 0;
}
---本文结束,感谢阅读---