UVa 944

From Algorithmist
Jump to: navigation, search

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 S0 = 7

S0 = 7

S1 = 72 = 49

S2 = 42 + 92 = 97

S3 = 92 + 72 = 130

S4 = 12 + 32 = 10

S5 = 12 = 1


If you reach 1 then S0 is Happy else it's Unhappy!

[edit] Gotcha's

  • S0 is unhappy when you meet a Si again and it means a loop, so it never meets 1.
  • ``if S0 is happy (unhappy), then any number in the sequence S1,S2,S3,... will also be happy (unhappy) , attention , if you know Si is happy (unhappy) don’t waste time and terminate it because the rest of sequence will be happy (unhappy).
  • the number of iterations for S0 ,if you meet a happy number in the sequence (Si), simply add the size of current sequence to the number of iterations for Si , then S1 = ( the number of iterations for S0) - 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
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox