题目描述
关于整数的2元圈乘运算
⊕
⊕
⊕ 定义为 X
⊕
⊕
⊕ Y = 十进制整数 X 的各位数字之和
×
\times
× 十进制整数 Y 的最大数字 + Y 的最小数字。例如,
9
⊕
30
=
9
×
3
+
0
=
27
9⊕30=9\times3+0=27
9⊕30=9×3+0=27。
对于给定的十进制整数 X 和 K,由 X 和
⊕
⊕
⊕ 运算可以组成各种不同的表达式。试设计一个算法,计算出由 X 和
⊕
⊕
⊕ 运算组成的值为 K 的表达式最少需用多少个
⊕
⊕
⊕ 运算。
算法设计:给定十进制整数 X 和 K (
1
≤
X
,
K
≤
1
0
20
1≤X,K≤10^{20}
1≤X,K≤1020) 。计算由 X
和
⊕
⊕
⊕ 运算组成的值为 K 的表达式最少需用多少个
⊕
⊕
⊕ 运算。
输入描述
每一行有两个十进制整数 X 和 K。
最后一行是 0 0
。
输出描述
将找到的最少
⊕
⊕
⊕ 运算个数输出,如果没有答案,输出No answer
。
思路分析
首先我们定义
c
n
t
x
,
s
u
m
x
,
m
x
x
,
m
i
x
,
n
u
m
x
cnt_x,sum_x,mx_x,mi_x,num_x
cntx,sumx,mxx,mix,numx 分别为
x
x
x 的位数,各位数字之和,各位数字中的最大值,各位数字中的最小值,进行
⊕
⊕
⊕ 运算能得到的最大值。
p
a
r
t
1
:
part 1:
part1:
当
c
n
t
x
≥
3
cnt_x \ge 3
cntx≥3 时,
X
⊕
X
≤
X
X⊕X\le X
X⊕X≤X 恒成立。证明如下:
∵
m
x
x
,
m
i
x
≤
9
,
x
各位数字
≤
9
\because mx_x,mi_x \le 9,x各位数字 \le 9
∵mxx,mix≤9,x各位数字≤9
∴
s
u
m
x
≤
c
n
t
x
×
9
×
9
+
9
→
c
n
t
x
×
81
+
9
\therefore sum_x \le cnt_x\times9\times9+9 \to cnt_x\times81+9
∴sumx≤cntx×9×9+9→cntx×81+9
∵
c
n
t
x
≥
3
,
m
i
x
≤
9
\because cnt_x\ge3,mi_x\le9
∵cntx≥3,mix≤9
∴
c
n
t
s
u
m
x
≤
c
n
t
x
\therefore cnt_{sum_x}\le cnt_x
∴cntsumx≤cntx
∴
X
⊕
X
≤
X
\therefore X⊕X\le X
∴X⊕X≤X
反之,
X
⊕
X
≥
X
X⊕X \ge X
X⊕X≥X 恒成立
p
a
r
t
2
:
part 2:
part2:
由
1
1
1 中结论我们可以很容易想到,每个数都有对应的
⊕
⊕
⊕ 运算最大值。当结果
k
≥
n
u
m
x
k\ge num_x
k≥numx时,这个
k
k
k 一定不能通过
x
x
x 的
⊕
⊕
⊕ 运算得到。需要注意的是,
c
n
t
x
≤
2
cnt_x\le 2
cntx≤2 时,我们需要保证
k
=
171
k = 171
k=171,因为一位和两位的数字在
⊕
⊕
⊕ 运算可以不断变大。
因此我们定义
f
i
f_i
fi 表示
⊕
⊕
⊕ 运算结果为
i
i
i 时的最小
⊕
⊕
⊕ 数。
那么对于每个
<
i
,
j
,
k
>
<i,j,k>
<i,j,k> 数对若
i
=
s
u
m
j
∗
m
x
k
+
m
i
k
i=sum_j*mx_k+mi_k
i=sumj∗mxk+mik,有转移方程如下:
f
i
=
m
i
n
(
f
i
,
f
j
+
f
k
+
1
)
f_i=min(f_i,f_j+f_k+1)
fi=min(fi,fj+fk+1)。
当我们依次匹配且此时不会对任意
f
i
f_i
fi 改变时,结果不会继续改变,此时我们输出
f
k
f_k
fk 即为答案。
代码
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
struct node
{
node() : mx(0), mi(9), s(0){};
node(ull num) : mx(0), mi(9), s(0)
{
ull tmp = num;
while (tmp)
{
ll t = tmp % 10;
mx = max(mx, t);
mi = min(mi, t);
s += t;
tmp /= 10;
}
};
ll s, mx, mi;
};
void solve()
{
ull m, k;//注意1e20超出了ll
while (cin >> m >> k && (m || k))//多组输入
{
if (m == k)//对于m==k的特判
{
cout << "0\n";
continue;
}
//求出最大结果
ll n = (log10(m) + 1) * 81 + 9; // 1629
//对于位数小于等于2的特判
if (n < 2 * 81 + 9)
n = 2 * 81 + 9; // 171
if (k > n)
{
cout << "No answer\n";
continue;
}//当k大于最大结果时,无效
vector<node> a(n + 10);
vector<ll> f(n + 10, inf);
for (int i = 1; i <= n; i++)
a[i] = node(i);//构造1-n各位的元素
a[0] = node(m);//将m放入位置0
f[0] = 0;
bool flag = true;
while (flag)
{
flag = false;
for (int i = 0; i <= n; i++)
{
if (f[i] == inf)
continue;
//找到可选择的i
for (int j = 0; j <= n; j++)
{
if (f[j] == inf)
continue;
//找到可选择的j
ll k = a[i].s * a[j].mx + a[j].mi;
//i⊕j
if (f[k] > f[i] + f[j] + 1)
{
f[k] = f[i] + f[j] + 1;
flag = true;
}
}
}
}
if (f[k] == inf)
cout << "No answer\n";//当结果仍为inf,说明k未被覆盖过,即无效
else
cout << f[k] << "\n";
}
}
int main()
{
int T = 1;
// cin>>T;
while (T--)
solve();
return 0;
}
/*
oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
x o
o _/_/_/_/ _/ x
x _/ o
o _/_/_/_/ _/ _/_/ _/_/ _/_/_/ _/_/ _/_/_/ _/_/ _/_/_/ _/ _/ _/ x
x _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ o
o _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/ x
x _/ _/ _/_/ _/ _/ _/ _/_/_/ _/_/ _/ _/ _/ _/ _/ o
o _/ _/ _/ x
x _/ _/_/ _/ o
o x
xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
*/