题目描述
给定一个如下乘法算式:
* * *
x * *
-------
* * *
* * *
-------
* * * *
现在,给定 N 个 1∼9 之间的数字,请你在这些数字中选取合适的数字填入算式,代替 * 号,使得算式成立。
所给的数字可以在算式中出现多次。
算式中不能出现没有给出的数字。
请问,共有多少种不同的填法?
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示给定的数字,数据保证这 N 个数字互不相同。
输出格式
输出一个整数,表示可以使得算式成立的总填法数量。
数据范围
1≤N≤9
输入样例:
5
2 3 4 6 8
输出样例:
1
样例解释
唯一的使得算式成立的填法如下:
2 2 2
x 2 2
------
4 4 4
4 4 4
---------
4 8 8 4
每个代替 * 号的数字均在给出数字之中,满足条件。
再看一组不满足条件的填法:
2 2 2 <-- OK: 三个数字均在 {2, 3, 4, 6, 8} 之中
x 2 3 <-- OK: 两个数字均在 {2, 3, 4, 6, 8} 之中
------
6 6 6 <-- OK: 三个数字均在 {2, 3, 4, 6, 8} 之中
4 4 4 <-- OK: 三个数字均在 {2, 3, 4, 6, 8} 之中
---------
5 1 0 6 <-- NOT OK: 5,1,0 均不在 {2, 3, 4, 6, 8} 之中
算法
枚举乘法的两个因数,再检查乘法中间两步和最后结果是否符合题目要求即可。
C++代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10;
int n;
bool st[N];//标记出现过的数字
bool check_in(int n)//检查是否是给定数字
{
while(n)//拆位,然后检查每一位是否是给定数字
{
if (!st[n % 10]) return false;
n /= 10;
}
return true;
}
bool check_len(int n, int k)//检查数字长度
{
return to_string(n).size() == k;//转换成字符串便于得到长度
}
bool check(int a, int b)
{
//c、d计算中间两步的值,e:结果积
int c = a * (b % 10), d = a * (b / 10), e = a * b;
if (!check_in(a) || !check_in(b) || !check_in(c) || !check_in(d) || !check_in(e))
return false;//是否都是给定数字
if (!check_len(c, 3) || !check_len(d, 3) || !check_len(e, 4))
return false;//是否都是指定长度
return true;
}
int main()
{
cin >> n;
for (int i = 0, x; i < n; ++i)
{
cin >> x;
st[x] = true;//记录给定数字
}
int res = 0;
for (int a = 100; a <= 999; ++a)//遍历乘法因数1
for (int b = 10; b <= 99; ++b)//遍历乘法因数2
if (check(a, b)) res ++;//统计符合条件的填法个数
cout << res << endl;
return 0;
}