Олимпиадная задачка - найти K минимально близкое ( разницей сумм делителей + разность самих чисел) к заданному числу N

[Serge_Bliznykov]

да, программа то есть, но она настолько корявая, что мне аж стыдно её показывать...
у меня в данный момент нет никакой IDE(Pascal/Delphi) под рукой, так я тоже на ideone пытался гонять код. Но не очень успешно, там ограничение на 5 секунд на выполнение кода стоит.
А для данной задачи это чрезвычайно мало.

впрочем, сделаем вид, что это не я писал, а нашёл где-то чей-то чужой кривой код

извольте код:

program testmax;

function sumdel( a : longint ):longint;
var sum, i : longint;
begin
  sum := 1;
  for i:=2 to (a div 2) do
    if (a mod i)=0 then sum := sum + i;
  sumdel := sum;
end;

var i, j, tmp1, tmp2, maxsum, imax, mindiff,
    maxlongj, diffj, diffi  : longint;
begin
   maxsum := -1;
   maxlongj := -1;
   for i:=1 to 200 do begin
     tmp1 := sumdel(i);
     mindiff := (i+tmp1)*10;
     for j:=1 to i*2 do 
       if i<>j then begin
         tmp2 := sumdel(j);
         if (abs(i-j)+abs(tmp1-tmp2)) < mindiff then 
               mindiff := (abs(i-j)+abs(tmp1-tmp2));
       end;
       if maxsum<mindiff then begin
         maxsum := mindiff; imax := i;
       end;
     Write(' N = ',i,' summa = ',tmp1, ' minimal diff = ',mindiff,' with K = '); 
     for j:=1 to i*2 do 
       if j<>i then begin
          tmp2 := sumdel(j);
          if (abs(i-j)+abs(tmp1-tmp2)) = mindiff then begin  Write(j,' ');  
                if abs(i-j)>maxlongj then begin maxlongj := abs(i-j);   diffj := j; diffi := i end;
          end;    
       end;
      WriteLn;   
   end;
   WriteLn('------------------------');
   WriteLn(' number N=',imax,' has maximal differ = ', maxsum);
   WriteLn(' max distance = ',maxlongj,' between N=',diffi,' K=', diffj );
end.

буду рад выслушать предложения/мнения по алгоритмам решения данной задачи!
я бы всё таки копал в сторону математической теории.
Очевидно, что минимальная разница сумм модулей не может быть меньше единицы.
И, на мой взгляд, решать задачу нужно двигаясь от N одновременно и в сторону уменьшения и в сторону увеличения. Вопрос только - с каким шагом (всегда ли движение с шагом 1 оправдано) и, главное, когда можно прерывать цикл.

[Poma][a]

Супер! Спасибо!
А я за такой вариант.. Заменять простые множители на большие\меньшие..

[Serge_Bliznykov]

Сообщение от Poma][a

Супер! Спасибо!

не за что...

Сообщение от Poma][a

А я за такой вариант.. Заменять простые множители на большие\меньшие..

я не уловил вашу идею. Поясните, пожалуйста.

[Аватар]

Не надо тут теории. Идем в цикле N-1,N-2,..,N-i,.. и вычисляем минимум пока i не станет больше или равен минимуму, дальше нет смысла, минимум в эту строну нашли. Аналогично N+1,N+2,...,N+i,.. То есть интервал не фиксированный какой-то формулой, а плавающий

[Poma][a]

N = 12
12 = 2*2*3
Ищем K
Давайте заменим 3-ку на новый простой делитель..
Это 5
2*2*5 = 20
Не очень..
А давайте замени на произведение двух простых делителей..
2*2*2*2 = 16..
Классно, да?
Давайте 71 : тут уже след. простое - 73..
Давайте 27 = 3*3*3
Снова
3*3*2*2=9*4=36 плохо..
Давайте в другую сторону
3*3*2 = 9*2 = 18 это 21+18 = 39. Ответ для 27 - 40..
Классно, да?

Давайте тест из примера :
900.. Sum = 1921 SN = 1921+900=2821..
Так.. 900=2*2*3*3*5*5
Наше любимое занятие - заменять одну тройку на две двойки..
2*2*2*2*3*5*5=1200
Summ 2644 .. Чет не ахти..
Давайте двойку на треху..
2*3*3*3*5*5 = 1350
Summ 2370.. Лучше.. Но
А давайте из 2*2*3*3*5*5 заберем 6-ку и добавим 7-ку..
2*3*5*5*7 = 1050.. Sum 1926
С ответом сошлось..
Давайте ради прикола след. пример :
2*2*2*2*3*3*5*7 = 5040 Sum 14304 SN = 19344
Давайте 2*2*3=12 -> 13
2*2*3*5*7*13 = 5460 Sum 13356
Ну хорошо..
Давайте еще побалуемся..
2*2*2*3*5*7*7 = 5880 Sum 14640
О! уже лучше..
Давайте еще.. Свернем 7-ку в 8-ку
2*2*2*2*2*2*2*3*3*5 = 5760 Sum 14130.. А теперь давайте прибавим.. SK = 14130 +5760 = 19890
Как-то так..

Правда как это все делать.. пока не понятно..

дальше нет смысла, минимум в эту строну нашли.

Да ладно?
32 SN = 63..
31 SN = 32
30 SN = 72
29 SN = 30
28 SN = 56

[Аватар]

Ромаха ты забыл про Abs(N-K)+Abs(SN-SK)

procedure TForm1.Button2Click(Sender: TObject);
var n,s,s0,i,m,t: Integer;
    u: Cardinal;
function SumDel(ak: Integer): Integer;
var ti: Integer;
begin
  Result:=1;
  for ti:=2 to ak div 2 do if ak mod ti=0 then Inc(Result,ti);
end;
begin
  u:=GetTickCount;
  n:=1000000;
  s:=SumDel(n);
  m:=n*10;
  i:=1;
  repeat
    s0:=Abs(s-SumDel(n-i))+i;
    if s0<m then begin m:=s0; t:=n-i; end;
    Inc(i);
  until (n=i) or (i>=m);
  i:=1;
  repeat
    s0:=Abs(s-SumDel(n+i))+i;
    if s0<m then begin m:=s0; t:=n+i; end;
    Inc(i);
  until i>=m;
  Label1.Caption:=Format('%d %d',[n,t]);
  Label2.Caption:=IntToStr(GetTickCount-u);
end;

[Poma][a]

Эт да.. Воистину печалька..
А для фанатов ideone можно маленький коммент?

[Аватар]

ideone чего это?

[Poma][a]

What is Ideone?
Ideone is an online compiler and debugging tool which allows you to compile source code and execute it online in more than 60 programming languages.

Если вкратце, то у меня нет дельфина, у Сержа нет дельфина.. Поэтому осознать всю божественность кода в посте 26 - малясь проблематично.. Поэтому было бы прекрасно, если бы Вы его шушуть прокомментировали..

[Аватар]

Дык в #24 вроде идея и описана, переведи на паскаль, на выходе t и есть искомое k. Все пять тестов из условия прошли, max время не помню, или 2, или 3 минуты, для предпоследнего. SumDel оптимизировать еще - цикл до корня квадратного