Shift Number
Submit: 659 Accepted:177
Time Limit: 1000MS Memory Limit: 65536K
Description
If a number is the sum of an integer’s several shifting forms, it is called the Shift Number.
For example, by shifting 123 four times and adding the four numbers together, we get 136653, which is a Shift Number.
However, a shift number may be the sum of more than one integer’s shifting forms. Such as, 45177 is a Shift Number, which could be generated from both 407 and 4107.
123+1230+12300+123000=136653
407+4070+40700=45177
4107+41070=45177
Given a Shift Number x , would you please help us find the least integer which could generate x by shifting.
Input
A shift number x.
Input ends with x=0.
Output
the least integer which could generate x by shifting.
Sample Input
136653
45177
0
Sample Output
123
407
Hint
If you are not familiar with “long long”, you can consult to FAQ.
Source
这个题目真的好郁闷,刚开始就是想对的,但是在草稿纸上写错了,于是这个题目崩溃了
于是出了一个很丑的算法,TLE
后来又顺着开始的思路,把主要的想法理清,很水的一个题目
但是用C++写的就是wrong 但是后来用java写的对的,后来比赛又用C++写过了。
看来会两种语言还是非常有必要的。。 呵呵。。
*/
#include <iostream>
#include <cstdio>
using namespace std;
inline long long sum(long long n)
{
long long s = 0;
while(n)
{
s = s * 10 + 1;
n /= 10;
}
return s;
}
int main()
{
long long a;
while(scanf("%lld", &a) != EOF && a)
{
long long b = a;
long long t;
while(true)
{
t = sum(b);
if(a % t == 0)
{
printf("%d/n", a / t);
break;
}
b /= 10;
}
}
return 0;
}
//System.out.println();
}
}
static long sum(long n)
{
long s = 0;
while(true)
{
s = 10 * s + 1;
n /= 10;
if(n == 0)
break;
}
return s;
}
}