ACPC10B - Sum the Square

no tags 

Take any positive number, find the sum of the squares of its digits, repeat! You’ll end up with an infinite sequence with an interesting property that we would like to investigate further. Starting with the number 5, the sequence is:
      (5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, . . .)
The interesting part is in what comes after 58: 52 + 82 = 89 which is a number that’s already been seen in the sequence. In other words, after 58, the sequence will fall into the repeating cycle:
      89, 145, 42, 20, 4, 16, 37, 58.
What’s amazing is that this cycle will appear for many other numbers: 3, 18, 36, and 64 just to name a few. (see figure on the following page.) For some numbers, the sequence will fall into another repeating cycle by reaching 1. (see second figure on the following page) For example, starting with 19, you’ll end up with the sequence:
      (19, 82, 68, 100, 1, . . .)
And that’s about it. Any number you choose will end up falling into a repeating cycle: Either the 89, 145, . . . cycle or the 1, . . . cycle.
Given two numbers, your objective is to generate as few numbers in their sequences for the two sequences to intersect at one common number. For example, given 61 and 29, we can achieve what’s required by generating the sequences: (61, 37, 58, 89) and (29, 85, 89). Similarly, for 19 and 100, the sequences would be (19, 82, 68, 100) and (100).

Input

Your program will be tested on one or more test cases. Each test case is specified on a single line having two integers (0 < A, B < 109 ).
The last case is followed by a dummy line made of two zeros.

Output

For each test case, print the following line:
A B S
Where A, B are as in the input and S is the (minimum) sum of the lengths of the two sequences.
If the sequences starting at A and B do not intersect, then S = 0.

Example

Input:
89 89
19 100
61 19
0 0

Output:
89 89 2
19 100 5
61 19 0

a

b


hide comments
Vipul Srivastava: 2016-08-10 16:56:48


Last edit: 2016-08-10 16:59:51
poojan : 2016-04-27 07:36:42

Amazing question! Lots of debugging and corner cases!
Some test cases that will help debugging:
30 11
85 20
20 89
145 16
19856 4029
0 0

output:
30 11 11
85 20 6
20 89 5
145 16 6
19856 4029 16

Good Luck.

Last edit: 2016-04-27 07:37:17
free mind ;): 2015-09-17 19:56:58

8 month ago i saw this question and today i solved it. Peace.
@eddy:- your friend is right.

Eddy Cael: 2015-09-04 03:49:49

This problem is a little suspicious. I challeged to my friend to solve this problem (because I couldn't solve it) He's got AC. Then, I compared the outputs for some test cases... . For example:
19856 4029
0 0
the numbers are:
19856 207 53 34 25 29 85 89 145 42 20 4 16 37 58 [89 145 ...]
4029 101 2 4 7 49 97 130 10 1 [1 1 ...]
His output is 16
And my code output 14
Can anyone tell me what happens here?
(Sorry for my poor english)

:.Mohib.:: 2015-08-01 19:55:55

Finally Done... :)

Mitch Schwartz: 2015-02-05 15:56:42

@Sunil Angadi: It's been years since I looked at this problem, so these comments are general:

1) Pay close attention to the difference between wrong test data and weak test data. Your use of the word "correct" is misleading/inaccurate, as it implies that the test data is wrong, while the rest of your comment is only enough to imply weakness.
2) When reporting weak test data, consider how severe the weakness that you found is. For example, if your code fails just for n<20 because of a bug with your precomputation, it might not be very significant as it doesn't concern the main algorithm. But if you can get AC with a wrong approach, or skipping an important step of an algorithm, or using a heuristic that doesn't always work, that could be more significant.
3) If you have thought about point (2), there could be various ways to communicate that in a comment without giving spoilers; please be thoughtful about that as well.

Last edit: 2015-02-05 16:58:37
Sunil: 2015-02-05 15:00:20

as per prob discussion, for 61 & 29, the answer should be 5 but a program generating ans as 7 gets accepted.

please correct it


Added by:Omar ElAzazy
Date:2010-11-30
Time limit:0.383s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACPC 2010