2634 - 圈乘运算问题

关于整数的 2 元圈乘运算定义为

</p>
<p class="MsoNormal" align="left">
	（<span>X<img src="http://tk.hustoj.com:80/attached/image/20140503/20140503124035_11763.jpg" alt="" /></span>Y）<span>=10</span> 进制整数 X

的各位数字之和*10 进制整数 Y 的最大数字+Y 的最小数字。

</p>
<p class="MsoNormal" align="left">
	例如，（<span>9</span><img src="http://tk.hustoj.com:80/attached/image/20140503/20140503124112_80865.jpg" alt="" />30）<span>=9*3+0=27</span>。
</p>
<p class="MsoNormal" align="left">
	对于给定的 10 进制整数 X 和 K，由 X

和#运算可以组成各种不同的表达式。试设计一个

</p>
<p class="MsoNormal" align="left">
	算法，计算出由 X 和<img src="http://tk.hustoj.com:80/attached/image/20140503/20140503124127_47519.jpg" alt="" />运算组成的值为 K

的表达式最少需用多少个运算。

</p>

<p class="MsoNormal" align="left">
	<span>&nbsp;</span> 
</p>

<p class="MsoNormal" align="left">
	<b>«</b><b>编程任务： </b> 
</p>

<p class="MsoNormal" align="left">
	<br />
</p>

给定 <span>10</span> 进制整数 <span>X</span> 和 <span>K </span>&nbsp;<span>(1</span>≤<span>X,K</span>≤<span>10^20</span>

达式最少需用多少个<img src="http://tk.hustoj.com:80/attached/image/20140503/20140503124425_22258.jpg" alt="" />运算。&nbsp;

Input

每一行有 2 个 10 进制整数 X 和 K。

最后一行是 0 0。

Output

将找到的最少Ä运算个数输出

Examples

Input

3 12 
0 0

Output

Solution C++

#include <iostream>
#include<cmath>
using namespace std;
#define ll unsigned long long
ll X, K,L;
const int MAX = 0x3f3f33f;
ll **s; // 0:最小值  1:sum  2:max  3:min
//求s[K][0]
void cal(ll k,ll x)
{
    s[k][1] = 0, s[k][2] = 0, s[k][3] = MAX;
    while (x)
    {
        s[k][1] += x % 10;
        s[k][2] = max(s[k][2], x % 10);
        s[k][3] = min(s[k][3], x % 10);
        x /= 10;
    }
}
void init()
{
    int m=ceil(log(X+1)/log(10.0));
    L=m*81+9;
    if(L<171)
        L=171;
    s=new ll*[L+1];
    for(ll i=0; i<=L; i++)
    {
        s[i] = new ll[4];
        if(i==0)
        {
            s[0][0]=0;
            cal(0,X);
        }
        else
        {
            s[i][0] = MAX;
            cal(i,i);
        }
    }
}
void quancheng()
{
    init();
    if (X == K)
    {
        cout<<"0"<<endl;
        return;
    }
    else if (K > L)
    {
        cout<<"No answer"<<endl;
        return;
    }
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (int i = 0; i <= L; i++)
        {
            if (s[i][0] < MAX)
            {
                for (int j = 0; j <= L; j++)
                {
                    if (s[j][0] < MAX)
                    {
                        int a = s[i][1] * s[j][2] + s[j][3];
                        if (s[a][0] > s[i][0] + s[j][0] + 1)
                        {
                            s[a][0] = s[i][0] + s[j][0] + 1;
                            flag = true;
                        }
                    }
                }
            }
        }
    }
    if (s[K][0] < MAX)
        cout<<s[K][0]<<endl;
    else
        cout<<"No answer"<<endl;
}
int main()
{
    //freopen("input9.txt", "r", stdin);
    //freopen("output9.txt", "w", stdout);
    while (cin >> X >> K)
    {
        if (X == 0 && K == 0)
            break;
        quancheng();
    }
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题

2634 - 圈乘运 算问题

Input

Output

Examples

Input

Output

Solution C++

2634 - 圈乘运算问题