首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7509

加号放哪里 给定任一个正整数 N,我们要从它开始,经过一系列操作得到一个个位数。操作方法是在 N 的各位数字之间放置一个加号,然后执行这个加法计算,得到一个新的…

加号放哪里

给定任一个正整数 N,我们要从它开始,经过一系列操作得到一个个位数。操作方法是在 N 的各位数字之间放置一个加号,然后执行这个加法计算,得到一个新的数字 N1,再对 N1 执行同样操作,得到 N2 …… 以此类推,直到最后得到的数字只有 1 位,则停止。

例如我们从 N=1234567890 出发,在 5 和 6 之间放置加号,计算 12345+67890=80235;然后在 0 和 2 之间放置加号,计算 80+235=315;然后在 1 和 5 之间放置加号,计算 31+5=36;最后在 3 和 6 之间放置加号,得到 3+6=9 而停止。这样我们通过 4 次计算得到了一个个位数 9。

本题就请你为任一给定的正整数计算:最少需要多少次加号放置可以得到个位数?

注意:加号必须放置在两个数字之间,不可放置在数字的首尾。

时间限制:7000

内存限制:65536

输入

输入在一行中给出一个正整数 n(≤ 1020)。

输出

在一行中首先输出将输入的整数变为个位数,需要放置加号的最少次数;随后输出最后得到的那个个位数。如果最后得到的个位数不唯一,输出最小的那个。 数字间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

1234567890

样例输出

3 9

提示

样例解释: 最优划分是: 1. 12345678+90=12345768 2. 1234+5768=7002 3. 7+002=9

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;stdlib.h&gt; long ansfqy = __LONG_MAX__; int ansnum = 10; void justdfs(long n, long frequency); void exceeddfs(char *n, long frequency); void justdfs(long n, long frequency) {     if (ansfqy &lt; frequency) {         return;     }     if (n &lt; 10 &amp;&amp; (n &lt; ansnum || frequency &lt; ansfqy)) {         ansnum = n;         ansfqy = frequency;         return;     }     long temp = 10;     while (n / temp &gt; 0) {         long nleft = n / temp;         long nright = n % temp;         temp *= 10;         justdfs(nleft + nright, frequency + 1);     } } void exceeddfs(char *n, long frequency) {     if (ansfqy &lt; frequency) {         return;     }     for (int i = 1; i &lt; strlen(n); i++) {         char BIleft[1025], BIright[1025];         strncpy(BIleft, n, i);         BIleft[i] = '\0';         strncpy(BIright, n + i, strlen(n) - i);         BIright[strlen(n) - i] = '\0';         long sum = atol(BIleft) + atol(BIright);         char temp[1025];         sprintf(temp, "%ld", sum);         if (strlen(temp) &lt; 19) {             justdfs(sum, frequency + 1);         } else {             exceeddfs(temp, frequency + 1);         }     } } int main() {     char n[1025];     scanf("%s", n);     if (strlen(n) &lt; 19) {         justdfs(atol(n), 0);     } else {         exceeddfs(n, 0);     }     printf("%ld %d\n", ansfqy, ansnum);     return 0; }</pre>
这道题暂未补解析。