1. Write a function "bool IsClearNumber(int n)" to check whether n is a clear number. Keep doing the sum of digit square, until 1 is reached or repeat number encountered. 2. Write a function "int S(int n)" to find the minimum clear number greater than n, by using the first function. 3. Write a function "int S_m(int n, int m)" to find m-th order of S(n) using 2nd function. way to improve speed: Cache the verified numbers in 2 hash_sets: clear-number-set and non-clear-number-set. So in the IsClearNumber() function, you can first check the number against these 2 sets to skip repetition. e.g. 19 → 82 → 68 → 100 → 1 (so this whole chain of numbers 19, 82, 68, 100, 1 are clear numbers, store them in clear-number-set) 12 → 5 → 25 → 29 → 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 → 145 (similarly, this whole chain of numbers are stored in non-clear-number-set)
On Wed, Jul 22, 2009 at 3:00 PM, FameofLight <[email protected]> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
