SNGNM2 - Number Magic II

num (> 9) be a positive integer. sum is defined as sum_of_digits_of_num. avg is defined as

    sum / digits_in_num

and avg takes only integer values (for example 34 / 5 is equal to 6, i.e. integer part of 6.8).

Now digits of num are rearranged by taking avg as pivoting element. Rearrangement is done according the following method:

[step 1]

    new_num = avg;
    read digits of num
    if (digit > avg)
        place digit at rightmost place in new_num
    else
        place digit at leftmost place in new_num

[step 2]

new_num is again rearranged into two numbers, eve_number (formed by taking digits of new_num at places 2, 4, 6, ...) and odd_number (formed by taking digits of new_num at places 1, 3, 5, ...).

Remember that counting of digit place starts from left-most digits as 1, 2, 3, 4...

[step 3]

    if (eve_number has < 3 digits)
        store the number
    else
        calculate avg and again start from process 1
    if (odd_number has < 3 digits)
        store the number
    else
        calculate avg and again start from step 1

Finally all desired numbers are stored and now we have to find two magical coefficients of num, named as alpha and beta.

[method digit_sum]

    number = num
    do {
        number = sum of digits of number
    } while (number >= 10)
    dig_sum = number

[alpha]

    digit_sum(summation_of_stored_numbers)

[beta]

    digit_sum(summation_of_digit_sum(stored_numbers))

we will say num is magic number if alpha, beta and |aplha - beta| are digits of num.

Input

First line of input is t (< 101), number of test cases. Each test case has n (< 501) as its first input and next n lines contains num (< 10101).

Output

For each test case, write exactly n lines containing value of alpha and beta; and yes or no according to whether or not num is magic number.

Example

Input:
1
1
9874

Output:
5 5 no

Explanation

  • num = 9874
  • avg = 7 (28 / 4)
  • rearrangement of num generates new_num = 47798.
  • thus eve_num = 79 and odd_num = 478.
  • now eve_num < 100, so 79 is stored.
  • but odd_num >= 100 so repeat the full process.
  • Finally stored numbers are N[] = 79, 68 and 47.

Make sure that you have to consider the total number of digits not the value of the number so you should not change the total number of digits of the number at any step.


Added by:AvmnuSng
Date:2013-09-15
Time limit:0.100s-1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Abhimanyu Singh
My Problems

hide comments
2019-10-05 17:23:24 Simes
Q: Is the "Process 1" referred to in step 3 the same as "Step 1"?
A: Yes

Q: Is this statement correct "you should not change the total number of digits of the number at any step"?
A: No, step 1 increases the number of digits by one, as shown in the worked example.

Q: Are alpha and beta always the same?
A: It looks that way. I've tested over 100,000 random numbers, and haven't found a single case where they're different.


Last edit: 2022-06-06 15:31:13
2014-06-24 20:29:05 anurag garg
@author: can you have a look at my submission:11820952 why I am getting TLE??
thanks

AC finally c++ strings are really slow try to avoid using inbuilt functions

Last edit: 2014-07-18 21:21:33
2013-11-16 11:22:27 AvmnuSng
@Decode : why don't you try to verify your code on few more test cases? may be there is problem with alpha (or) beta (or) avg value calculated in your code.
2013-11-16 11:22:27 Decode
@Abhimanyu.
Plz tell me.why am i getting wrong answer.
2013-11-16 11:22:27 AvmnuSng
@Mehmet Inal : my problems are easy but requires some work, and i'll keep adding such problems :)
by the way, i'll update the problem statement
2013-11-16 11:22:27 mehmetin
That is hard to guess from problem statement, although the additional note points in that direction. Maybe the condition
if number < 100 then store number
should be changed as
if number has less than three digits then store number
(leading zeros are significant).

Nice problem. Not too difficult, but requires some work.


Last edit: 2016-03-05 19:13:26
2013-11-16 11:22:27 AvmnuSng
As 098 Or 0098 has 3 and 4 digits and you should store any number when it has two digits and then it will fall under the condition num < 100 to store it.

For 098, avg = 5; so rearranged no. is 0598 and then eve_no = 58 and odd_no = 05 so stored no. are 5 and 58
2013-11-16 11:22:27 mehmetin
Thanks for extending time limit. Anyway, I removed all forms of STL and got accepted with a better time.

I think there might be some mistake in the input. If I'm not mistaken, a number like 98 is considered ok for storing, but 098 or 00098 is not. Can you check that?
2013-11-16 11:22:27 mehmetin
Yes, I got it, but this time I have TLE..
2013-11-16 11:22:27 AvmnuSng
@Mehmet Inal : Check your submission id 10404950 again but without the first function of your code, I hope you got, what i mean
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.