bool isClearNumber(long int x)
{
long int sum = 0;
do
{
sum += (x%10)*(x%10);
x /= 10;
} while (x > 0);
if (sum == 1)
return true;
else if (sum < 10)
return false;
else
return isClearNumber(sum);
}
long int findClearNumber(long int n, long int m)
{
clearNumbers.clear();
long int x=n, t=0;
while(t<m)
{
x++;
if (isClearNumber(x))
t++;
}
return x;
}
int main(int argc, char *argv[])
{
int instances;
cin >> instances;
long int result[instances];
for (int i=0; i<instances; i++)
{
long int m;
long int n;
cin >> n >> m;
result[i] = findClearNumber(n[i], m[i]);
}
for (int i=0; i<instances; i++);
cout << result[i];
return 0;
}
This is a very basic version with no variable used to keep already
processed data.
we can use a sorted array to reduce the number of recalculations. and
can use other optimized methods.
On Jul 22, 12:35 pm, 周游弋 <[email protected]> wrote:
> For the largest possible value is 10^15, thus the largest possible sum of all
> digits comes from 999999999999999, which gives 15*81 = 1215
> For 1215, the largest possible sum of all digits comes from 999 --> 243.
> For 243, the largest possible sum of all digits comes from 199 --> 163
> For 163, it's 162. And it ends here.
>
> Finding the clear numbers in [1,162] is trival.
>
> -----邮件原件-----
> 发件人: [email protected] [mailto:[email protected]] 代表
> FameofLight
> 发送时间: 2009年7月22日 15:00
> 收件人: google-codejam
> 主题: Re: Clear Numbers exercise
>
> Anybody please give me some clue on How to Solve this problem.
>
> On Jul 22, 5:26 am, khanh le <[email protected]> wrote:
>
> > Dear people,
> > i have a exercise, so i want to you solve it. you must code by C++ langguage
> > now, read the exercise below:
>
> > Peter has just found a definition of *clear numbers* as the following: for
> > each positive integer n, we form another number by summing the squares of
> > the digits of n. We repeat this procedure. If at some step, we obtain the
> > number 1 then n is called a *clear number*. For example, for n=19, we have:
>
> > 19 → 82 (= 12 +92) → 68 → 100 → 1
>
> > Thus, 19 is a clear number.
>
> > Not all numbers are clear numbers. For example, for n=12, we have:
>
> > 12 → 5 → 25 → 29 → 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 → 145
>
> > Peter is very interested in this definition of clear numbers. He issued a
> > challenge to the landlord: given a positive integer n, find S(n), the clear
> > number succeeding n, i.e. S(n) is the minimum clear number greater than n.
> > However, this question is so easy for the landlord that he challenged Peter
> > with another problem: given two positive integers n and m (1 ≤ n, m ≤ 1015),
> > find the number Sm(n)=S(S(…S(n) )) which is the mth clear number succeeding
> > n.
>
> > Please help Peter to solve the task!
> > Input
>
> > The first line contains t (0 < t ≤ 20) , the number of test cases.
>
> > Each line in the next t lines contains two positive integers n and m.
> > Output
>
> > Print t lines, each line contains the result of the corresponding test case.
> > Example
>
> > *Input*
> > 2
> > 18 1
> > 1 145674807
>
> > *Output*
> > 19
> > 1000000000
>
> > Notes
>
> > There are 50% of the test cases in which 1 ≤ n, m ≤ 107.
>
> > --
> > Regard!
> > Khanh
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
