in that case, every time a number is verified along with its whole chain of numbers, they will be converted into "sorted digit" form (321 into 123, 130 into 13, 3001 into 13 as well), to ensure all permutation variants turn into an unique representation form. in the previous post, i mentioned 2 sets: one for clear numbers, another for non-clear numbers. Now before we store any number into the sets or even before we match it against the two sets, we convert them into the unique "sorted digit" format. So the entry of the number 13 in the clear-number-set will match all permutations of 1,3,0s (ie. 13, 31, 130, 310, 103, 1003, etc), this further reduce repetition of calculation arise from permutation of digits.
2009/7/23 Tim MacDonald <[email protected]> > That isn't an issue, because S(n,n) will still be much less than 10^18, and > fit into a 32-bit int. > > The real problem, however, is with the idea of counting S(n), S(n+1), etc. > If m is large, you'll be waiting a looooong time for this counting operation > to complete. > > You need to be more efficient, for instance, efficiently determining how > many numbers in the range [a,b] are "clear". This actually becomes a > combinatorics problem of sorts. Think about this, how many numbers in the > range [1000000,1999999] have sum of squares of their digits equal to say, > 19? Repeat for other possible sums that are "clear", and you know how many > numbers across the entire range are clear. Extend this basic idea into your > completed solution. > > -Tim MacDonald > > > > > > 2009/7/22 Iuri <[email protected]> > > Reading the question, I guess we can define n = 10^10 and m = 10^15 - 1, >> and it will broke this idea, because the maximum is not 10^15 - 1 anymore. >> >> 2009/7/23 Hawston LLH <[email protected]> >> >> "long long" arithmetic calculation (+ - x /) is fully supported by most >>> machines, so this should not be a problem. :) >>> >>> 2009/7/23 周游弋 <[email protected]> >>> >>> Because any number bigger than 162 can be eventually summed back to a >>>> value less than 162, 999 -> 243 -> 29, 9999 -> 324 -> 29 etc. Thus if we >>>> could find determine the clear numbers in [1,162], then all integers can be >>>> deducted eventually by (or “to”) these determined numbers. >>>> >>>> >>>> >>>> As for finding S(n), it is just a counting problem. Starting from n, try >>>> n+1, n+2, n+2 …. And for S(n, m), just start from n+m, try n+m+1, n+m+2… As >>>> I said, no matter how big the number is, it will eventually fall in between >>>> [1,162] in four or five steps. >>>> >>>> >>>> >>>> As for the concrete implementation, there is an issue. The data scale is >>>> too big for long integer. Though a “double” variable could do, there will >>>> be >>>> precision problems with “double” values. In GNU extension we could use a >>>> “long long” type but it destroy the portability of the solution. So, we >>>> may >>>> need to write a function to sum two big integers together, digit by digit, >>>> to compute n+m when n or m are rather large. >>>> >>>> >>>> >>>> For this specific problem, first build a look-up table T[i] (i = 1, 2, >>>> 3, … , 1215) using the method we discussed, T[i] denotes whether i is a >>>> clear number. Now compute n+m by the “big integer adding function”. >>>> Starting >>>> from n+m+1, sum all its digits up and look it up in T. >>>> >>>> >>>> ------------------------------ >>>> >>>> *发件人:* [email protected] [mailto: >>>> [email protected]] *代表 *Hawston LLH >>>> *发送时间:* 2009年7月22日 15:58 >>>> *收件人:* [email protected] >>>> *主题:* Re: 答复: Clear Numbers exercise >>>> >>>> >>>> >>>> i think either you misunderstood the S(n) which is the minimum clear >>>> number greater than n or i have misunderstood your purpose of "the largest >>>> possible sum of all digits". Could you elaborate your purpose to find >>>> "162"? >>>> >>>> >>>> >>>> >>>> >>>> On Wed, Jul 22, 2009 at 3: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 -~----------~----~----~----~------~----~------~--~---
