Hi First of all, sorry for my poor english.
I think that the stop test is isClearNumber (sum < 10) is not valid since there are clear numbers in [1,10]. For example, 7 : 7 -> 49 -> 97 -> 130 -> 10 -> 1 A valid stop test is to find a loop while checking for clear number. Miguel Fernandez 2009/7/22 poisonivy <[email protected]> > > 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) > { > 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 < MAXINSTANCE; i++) > { > long int m, n; > cin >> n >> m; > result[i] = findClearNumber(n, m); > } > for (int i=0; i<instances; i++); > cout << result[i]; > return 0; > } > > This is a very basic solution. we can further optimise it bu utilising > some array containing already scanned numbers. > > 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 -~----------~----~----~----~------~----~------~--~---
