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

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

Proof
Послано 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
thanks
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).