Расстояние между числами

Например, расстояние между 112 и 222 будет 2 потому что 2я цифра отличается. Расстояние между 112 и 212 будет 1 потому что 1я цифра отличается. Расстояние между 112 и 122 все равно будет 2 потому что 2-я цифра отличается (хоть первые и одинаковые).

Нужно упорядочить цифры так, чтоб сумма расстояний была минимальной. Для этой задачи подходит "жадный подход": после каждого шага стараешься чтоб расстояние было как можно меньше.

Допустим первая цифра 111. Будем ставить все цифры на расстоянии 1 от предыдущей.
211
311
411
511
611
711
811
911

Теперь, все цифры на расстоянии 1 от предыдущей исчерпанны; самая близкая цифра будет с расстоянием 2--- то есть, вторая цифра будет отличаться. Допустим:
921

Теперь, можно снова использовать цифры на расстоянии 1 от предыдущей.
821
721
621
521
421
321
221
121

Снова, тупик. Нужно еще раз использовать цифру на расстоянии 2. Ну, и так далее. Теперь, нужно посчитать какая выходит сумма расстояний.

В итоге, мы будем менять цифры на расстоянии 3 (т. е., менять последнюю цифру) девять раз (от 0 до 9).

Для каждой группы числ с определенной последней цифрой (скажем, все числа с последней цифрой 1; таких групп всего 10), будем менять вторую цифру 9 раз (с 0 до 9); поэтому количество цифр на расстоянии 2 будет 9*10 = 90.

Наконец, все остальные цифры будут на расстоянии 1. Это 899-90-9=800 цифр. Мы начинаем с 899 потому что нужно всего цифр 900, а так как мы начинаем с 1-й то переходить от одной до другой нужно 900-1 = 899 раз. Поэтому, общая сумма выходит: 800*1 + 90*2 + 9*3 = 1007.

Это задача из теории чисел.

в

Думай

Равно