ENG  RUSTimus Online Judge
Online Judge
О системе
Часто задаваемые вопросы
Новости сайта
Архив задач
Отправить на проверку
Состояние проверки
Исправить данные
Рейтинг авторов
Текущее соревнование
Прошедшие соревнования
вернуться в форум

Обсуждение задачи 1206. Сумма цифр суммы чисел

Послано Noob 12 май 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
Послано balandini 7 июн 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
Послано Dmitri Belous 2 сен 2012 15:22
Re: Proof
Послано Kuros 7 фев 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).