ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1206. Sum of Digits of the Sum of Numbers

Posted by Noob 12 May 2012 03:16
I've solved it using bruteforce for small K and then guessing the formula. But I still don't know the proof. Can anybody write it?
Re: Proof
Posted by balandini 7 Jun 2012 18:20
S(A + B) = S(A) + S(B) is equal to that that for every pair of corresponding digits of A and B their sum is lower then 10 (1).
For example:
12 and 13 :1+1<10;2+3<10 it means S(A + B) = S(A) + S(B)
18 and 19: 8+9>10 it means S(A + B) = S(A) + S(B) is wrong here.
Then for every pair of digits from A and B you just count how many varints of pair suits (1) and multiply these quantities for all pairs.
Re: Proof
Posted by Dmitri Belous 2 Sep 2012 15:22
Re: Proof
Posted by Kuros 7 Feb 2014 01:51
Another way to go at it is to think of the number (A+B) as a bunch of stacked blocks, each stack representing a digit. Here is 43 for example:
|_| _

Now, to find all the A's and B's that can form S(A+B) = S(43), for example 12+31 or 22+21, etc, we can represent this as chopping each stack into two parts, for example in the case of 12+31:

|_| _
 _ |_|
|_| _

Now, if we take the general case of having two digits, if the first digit is 1, we can't split the first digit in two since the first digit of A or B can't be 0. However, if the first digit is 2, we can split it in one way (in the middle), and then we can split the second digit depending on what digit it is. If it is 2, we can split it in 3 different ways ( (0,2),(1,1),(2,0) ). If it is 3, we can split it in 4 different ways, etc. So, if the first digit of the two-digit number is 2, we can split the whole number in 1*(1+2+3+4+5+6+7+8+9+10)=1+(10*11/2) different ways. If the first digit is 3, we can split the whole number in 2*(1+2+3+4+5+6+7+8+9+10)=2*(10*11/2) different ways, etc. If we sum everything we get (8*9)/2*(10*11)/2 ways to split a two digit number. For an n digit number continuing the same way we get (8*9)/2*((10*11)/2)^(n-1).