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
2013-11-16 11:22:27 AvmnuSng
All the time, you should not change the total number of digits of the number at any step
2013-11-16 11:22:27 mehmetin
"Make sure that you have to consider the total number of digits not the value of the number"

Are we doing this while calculating alpha or beta? Or avg?

Last edit: 2013-11-02 18:39:10
2013-11-16 11:22:27 AvmnuSng
@Mehmet Inal : That's very correct, sorry for that mistake. Regarding your wrong answer, I added a note in problem statement.

Last edit: 2013-11-02 18:18:53
2013-11-16 11:22:27 mehmetin
Is the input and problem description correct? I can't find my mistake. Can you provide a test case or give an idea about why my code fails? (last submission)

btw, I think the digit_sum method should be as follows, i.e. it shouldn't return 10:
number = num

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

dig_sum = number


Last edit: 2013-11-02 17:42:10
2013-11-16 11:22:27 AvmnuSng
every time u'll generate the desired num, it will be stored, doesn't matter whether it is already in the list of stored numbers or not
2013-11-16 11:22:27 mehmetin
Can a number be stored more than once?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.