Задача на свойства чисел

[Иллидан]

Задача, найти(за максимально короткое время) сколько чисел в диапазоне от a b(a,b ≤ 10 в 18) имеют хотя бы одну одинаковую противоположную цифру, то есть какое-нибудь Ki = Kn+1−i при i ≠ n+1−i. Наример в диапазоне от 10 до 99 таких чисел 9 (11,22...99) У кого какие предложения?

[alexBlack]

По моему можно рассуждать так:

берем число
x----------------x
Для крайних рахрядов этого числа, как уже было замечено, 9 вариантов

y--------------y
Берем внутреннюю последовательность. Для ее крайних разрядов уже 10 вариантов (добавляется 0). Эти варианты могут быть с любыми цифрами слева и справа (кроме левого нуля). Итого

9 (от предыдущей) + 9*10*10 (если не ошибаюсь).

И так далее для внутренних последовательностей.

[Иллидан]

Хм, а если у числа нечетное число цифр? А если необходимо посчитать от 11 например до 55671?

[alexBlack]

Сообщение от Иллидан

Хм, а если у числа нечетное число цифр?

В конце останется только один
А у этого разряда нет противоположного.

Сообщение от Иллидан

А если необходимо посчитать от 11 например до 55671?

Здесь нужно подумать, но ИМХО д.б. просто разница между количеством для 55671 и количеством для 11.

[Иллидан]

В конце останется только один
А у этого разряда нет противоположного.

Счиатем от 100 до 999. Получается:
101 111 ... 191. {итого 9}
202 212 ... 292. {итого 9}
...................................
909 919 ... 999. {итого 9}

9*9?

Здесь нужно подумать, но ИМХО д.б. просто разница между количеством для 55671 и количеством для 11.

В каком смысле разница?

[alexBlack]

М..да. Вы правы, при попытке реализации все оказалось сложнее чем я предполагал.

Вот функция, которая подсчитывает количество чисел для диапазона
от 00...00 до 99..99 с учетом незначащих нулей.

Z задает количество десятичных знаков.

function getCountNumber09(Z:integer):integer;
var i, k, k10:integer;
begin
   if Z <= 1     then result := 0
   else if Z = 2 then result := 10
   else if Z = 3 then result := 100
   else begin
      // Просто степень 10^(z-2)
      k10 := 1;
      for i:=1 to Z-2 do begin
         k10 := k10 * 10;
      end;

      k := getCountNumber09(Z-2);
      { Добавляем два разряда слева и справа
        Это значит, что все варианты внутреннего числа
        от 0<00..00>0
        до 0<99..99>0
        повторятся для каждого варианта добавленных разрядов
        Значит повторятся и уже вычисленные числа
      }
      result := k*10*10;
      { Далее добавятся новые варианты
        0 .. 0
        9 .. 9
        Эти варианты будут повторяться k10 раз
      }
      result := result + 10*k10;
      { Добавленные варианты продублируют варианты
        внутреннего числа
      }
      result := result - 10*k;
   end;
end;

getCountNumber09(3) - 100
getCountNumber09(4) - 1900
00000 - 99999 - 19000
000000-999999 - 271000

Думаю, идея понятна. Дальше нужно продумать как это применить для диапазона от
1 до некоторого числа.

А чтобы найти количество в диапазоне можно будет найти количество от 1 до числа b, от 1 до числа a и вычесть из первого второе.

[Иллидан]

Хм, Как подсчитать от 1 до 9, 99.... до любого кол-во девяток, кажется, понятно. Но, как подсчитать до какого-нибудь 67845 нет очень. Может быть, как-нибудь применить, то что, мы знаем количество от 1 до 99999?

[alexBlack]

Сообщение от Иллидан

Хм, Как подсчитать от 1 до 9, 99.... до любого кол-во девяток, кажется, понятно. Но, как подсчитать до какого-нибудь 67845 нет очень. Может быть, как-нибудь применить, то что, мы знаем количество от 1 до 99999?

Кажется добил. Тест проходит. Правда, код еще нужно дорабатывать - убрать все лишнее, заменить integer на что-то более подходящее для диапазона 10^18...