Игра с калькулятором, + Опции

[Учинек]

В калькулятор вводится натурально число К и нажимается клавиша "+". Калькулятор все еще показывает К. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для ее достижения можно производить только одно действие - нажимать на клавишу "=" (возможно, 0 раз). После первого нажатия получается результат К+К, после очередного нажатия результат увеличивается на К. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек - тоже.
Ограничения: 1<=K<=999, время 1с.
Вводится одно число - К.
Вывести если цели достичь невозможно "No", если возможно, вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.

Пример.
ввод№1
37
вывод№1
1 3

ввод№2
25
вывод
No




Я даже не знаю, что делать. Тупой перебор не пойдет потому как числа могут быть очень большие....как мне кажется должна быть формула, но вот только какая....

И еще по-моему числа которые заканчиваются на 0 не будут образовывать число с одинаковыми цифрами, сколько их не складывай.

Сообщение отредактировано: Учинек - 23.12.2008 20:31

[Lapp]

И еще по-моему числа которые заканчиваются на 0 не будут образовывать число с одинаковыми цифрами, сколько их не складывай.

Хорошее соображение - числа, большие нуля (по условию), не могут состоять из одних нулей . Это я, кстати, использую ниже.

Я даже не знаю, что делать. Тупой перебор не пойдет потому как числа могут быть очень большие....как мне кажется должна быть формула, но вот только какая....

Не думаю, чтоб была какая-то полезная формула на этот счет. Как грится, "трясти надо!" (с). Это тебе кажется, что числа будут очень большие: у страха глаза велики . Вот, смотри.

Многократное сложение есть на самом деле умножение. Исходное число не больше тысячи. После умножения его на 1000 комбинации низших трех разрядов начнут повторяться:
...
123 * 1000 = 123000
123 * 1000 + 123 = 123123
...
Поэтому достаточно рассмотреть не более чем тысячекратное сложение. А это значит, что числа будут не больше 999999. Таким образом, работаем с типом LongInt и забываем о проблеме "больших чисел" .


Подходов я вижу два: один прямой, другой "с заднего кирильца" (с). Первый - тупо в лоб складывать числа, как написано в условии, и проверять. Вот он:

function Digit(n: LongInt; p: byte): byte;
var
  i: integer;
  m: LongInt;
begin
  m:=1;
  for i:=2 to p do m:=m*10;
  Digit:=n div m mod 10
end;

var
  a,k: LongInt;
  i: integer;
  d,j,p,n: byte;

begin
  ReadLn(k);
  a:=0;
  for i:=1 to 999 do begin
    a:=a+k;
    j:=7;
    repeat
      Dec(j);
      d:=Digit(a,j)
    until d>0;
    n:=j;
    Dec(j);
    while (j>0)and(Digit(a,j)=d) do Dec(j);
    if j=0 then begin
      WriteLn(d,' ',n);
      exit
    end
  end;
  WriteLn('No')
end.

Выглядит громоздко даже с функцией.. А если не уложимся во время (хотя, 1 сек - не так и мало), то придется вставить вычисление цифры прямо в код.

Второй метод основан на том, что чисел, состоящих из одинаковых цифр в диапазоне до миллиона не так уж и много (а точнее, 6*9=54). Перебираем их все и делим на данное число. Если остаток равен нулю - нам повезло . Этот способ гораздо изящнее и заведомо укладывается в сотые доли секунды, полагаю..
Вот он:

var
  a,k: LongInt;
  i,j: byte;

begin
  ReadLn(k);
  a:=0;
  for i:=1 to 6 do begin
    a:=a*10+1;
    for j:=1 to 9 do if a*j mod k=0 then begin
      WriteLn(j,' ',i);
      exit
    end
  end;
  WriteLn('No')
end.

Вот и все.
Как грится - хорошо , но мало..

Добавлено через 10 мин.
Еще, вот это понравилось:

В калькулятор вводится натурально число К ...

Так и хочется добавить: "чисто конкретно" - и расставить пальцы..