Thanks very much for the hints. 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 >>>> >>>> >>>> >>>> >>>> >>> >>> >>> >> >> >> >
-- Best regards 周游弋（Joel Zhou） --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
