UVa 944
From Algorithmist
Contents |
[edit] 944 - Happy Numbers
[edit] Summary
Read two positive integers between 1 and 99999 (inclusive) each; the first integer, L, is the low limit of the closed interval; the second one, H, is the high limit (L ≤ H). The output is composed of the happy numbers that lie in the interval [L,H], together with the number of iterations required for the corresponding sequences of squares to reach 1.
[edit] Explanation
Instructions are clear. If you start with S_{0} = 7
S_{0} = 7
S_{1} = 7^{2} = 49
S_{2} = 4^{2} + 9^{2} = 97
S_{3} = 9^{2} + 7^{2} = 130
S_{4} = 1^{2} + 3^{2} = 10
S_{5} = 1^{2} = 1
If you reach 1 then S_{0} is Happy else it's Unhappy!
[edit] Gotcha's
- S_{0} is unhappy when you meet a S_{i} again and it means a loop, so it never meets 1.
- ``if S_{0} is happy (unhappy), then any number in the sequence S_{1},S_{2},S_{3},... will also be happy (unhappy) , attention , if you know S_{i} is happy (unhappy) don’t waste time and terminate it because the rest of sequence will be happy (unhappy).
- the number of iterations for S_{0} ,if you meet a happy number in the sequence (S_{i}), simply add the size of current sequence to the number of iterations for S_{i} , then S_{1} = ( the number of iterations for S_{0}) - 1 and so on.
[edit] Input
7 10 1 7 10 4 10 10 1 1 99970 99999
[edit] Output
7 6 10 2 1 1 7 6 10 2 1 1 99971 7 99973 4 99978 8 99987 8