freepascal.ru

Помогите с задачей:
Положительное целое число хорошее, если сумма его цифр больше, чем их произведение. Например, числа 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 секунд.

если хочешь уложиться в 2 секунды, то задача на комбинаторику

для разминки комбинаторых навыков, начни с того, что посчитаешь все N-значные числа (N<=18) в которых есть цифра 0 (не в начале числа)!
если решишь эту подзадачку, то и решишь всю задачу... и я так понимаю, гораздо быстрее 2х секунд ))

если решишь эту подзадачку, то и решишь всю задачу...

Интересно было бы послушать как

Вообще задачка на уровне олимпиад, для начала учтём, что порядок чисел - не важен - отпадает существенная часть комбинаций, останется N!, что 18!=6402373705728000, рассчёт необходимо производить по принципу наращивания - тогда получатся ветки значений с хорошими и отвратительными числами на разных концах ветки, что дает ~18!*0.3=1920712111718400 рассчётов, но на практике - можно использовать какой-то "корень", состоящий из определённой комбинации чисел, сумма и произведение которых уже известна и потом искать минимум в ветке, с которого начинаются отличные числа, а не считать всё сразу, тогда получим ~18!*0.3*0,01=19207121117184. Этого в принципе дожно хватить.

wavebvg писал(а):Вообще задачка на уровне олимпиад

Судя по ограничению времени и рассматриваемым им задачам, человек как раз на олимпиаду и готовится .

~18!*0.3*0,01=19207121117184. Этого в принципе дожно хватить.

Как показывает практика, 10^8 уже слишком много

На самом деле, если правильно всё реализовать может уложиться по времени... Тут главна проблема - правильно считать, а именно - со стороны БОООЛЬШИХ (ведь мы приняли, что цЫфры у нас все возрастающие в числе) т.е. к примеру
1123459 - перемножаем 5*9=45, дальше можно не считать (для 7-го числа максимум прироста 5+9+5*1, что явно меньше), таким образом придётся 19207121117184 сложить и перемножить по два числа - что вполне реально успеть сделать.

ещё раз повторюсь, что считать ВСЕ числа не нужно, нужно считать ПЕРЕСТАНОВКИ "хороших" цифр!

например для трёх значиных цифр, "хорошие" перестановки это
[1,1,2] (из них получаются цифры) 112, 121, 211
так же хорошая перестановки: [1,1,3]...[1,1,9], [1,2,2]. Из каждой из этих перестановок можно получить по 3 числа.
считаем, сколько это будет чисел всего?

для четырёх значных чисел, хорошие перестановки теже самые (+1 в начало) ( динамическое программирование?), т.е.
[1,1,1,2],[1,1,1,3]..[1,1,2,2] и ещё [1,1,2,3]... здесь больше перестановок получается...

в итоге "хорошие" перестановки можно подобрать и для N=18
[1,1,1,1...,1,2] - (считаем перестановки )
[1,1,1,1...,2,3]
[1,1,1,1...,2,9]
[1,1,1,1...,3,9]

т.к. для нахождения кол-ва перестановок есть специальная формула никакой "переборный" алгоритм по скорости не сравниться! удачи!

Надо ещё учесть, чтобы 0 не был в начале чисел, но был в конце, но сейчас мне перечитывать компбинаторику лень и некогда!!!