Помогите с задачей:
Положительное целое число хорошее, если сумма его цифр больше, чем их произведение. Например, числа 12, 11, 131, 9909 - хорошие, а 39, 546, 22 - нет. Необходимо вычислить количество хороших N-значных чисел (N<=18), у которых первая цифра не является нулём.
Ограничение по времени: 2 секунды.
Вопрос: реально ли уложиться при N>=8???
Добавлено спустя 17 минут 35 секунд:
Лучший вариант программы, который я получил:
Program goodnum;
var n,b,g: shortint;
a,c,p,t,d,i,f: longint;
k,e,s: integer;
begin
writeln ('vvedi n');
readln (n);
a:=1;
for i:=2 to n do
a:=a*10;
c:=a*10-1;
i:=a;
while i<=c do
begin
d:=i;
s:=0;
p:=1;
k:=0;
while d>0 do
begin
b:=d mod 10;
d:=d div 10;
s:=s+b;
p:=p*b;
k:=k+1;
if b=0 then d:=0;
end;
if b=o then
begin
f:=1; for e:=2 to k do
f:=f*10;
i:=i+f;
t:=t+f;
end
else begin if s>p then t:=t+1;
i:=i+1; end;
end;
writeln ('horoshih chisel - ',t);
readln;
end.
При N=8 время=4 секунды, при N=9 время=37 секунд.
динамическое программирование?), т.е.