Версия для печати темы

Автор: kumino 3.05.2012 22:16

Рассмотрим следующий алгоритм генерации последовательности чисел. Начнем с целого числа N. Если N четно, то поделим на 2. Если N нечетно, то умножим на 3 и добавим 1. Будем повторять процесс с новым полученным N, пока N не станет равным 1. Например, для N = 22 будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сведется к N = 1 для любого целого N. По крайней мере, это предположение верно для всех целых чисел до 1000000.

Для заданного N длиной цикла N будем называть чисор сгенерированных чисел до и включая 1. В примере, приведенном выше, длина цикла 22 равна 16. Для двух заданных чисел i и j вы должны определить максимальную длину цикла для всех чисел между i и j, включая обе конечные точки.

Технические условия

Входные данные

Входные даные будут состоять из серии пар целых чисел i и j, одна пара чисел в строке. Все целые числа будут меньше 1000000 и больше 0.

Выходные данные

Для каждой пары чисел i и j выведите числа i, j в том порядке, в каком они были введены, и после этого выведите максимальную длину цикла для всех целых чисел между i и j, включая сами i и j. Эти три числа должны быть разделены одним пробелом, все три числа в одной строке, и для каждой строки входных данных должна быть одна строка входных данных.

Задача которую я не смог решить. Почему-то ответ неправильный!!!

var a,b,max,leng,i,j,x:longint;
    k:int64;
    c:array[1..1000000] of integer;
    d:array[1..1000] of int64;
function maxi(d,e:longint):longint;
begin
if (d>e) then
begin
maxi:=d;
end
else
begin
maxi:=e;
end;

end;

function min(f,g:longint):longint;
begin
if (f>g) then
begin
min:=g;
end
else
begin
min:=f;
end;

end;

begin
for i:=2 to 1000000 do
c[i]:=0;
c[1]:=1;
for i:=2 to 1000000 do
begin
if (c[i]=0) then
begin
j:=1;
k:=i;

repeat
d[j]:=k;
if (k mod 2=0) then
begin
k:=k div 2;
end
else
begin
k:=k*3+1;
end;
inc(j,1);
until(k=1);

c[i]:=j;
for x:=2 to j do
begin
if ((d[x]<1000001) and (c[d[x]]=0)) then
c[d[x]]:=j-x+1;
end;
end;
end;
while not eof do
begin
read(a,b);
max:=c[min(a,b)];
for i:=min(a,b)+1 to maxi(a,b) do
if (c[i]>max) then
max:=c[i];
writeln(a,' ',b,' ',max);
end;
end.

Автор: IUnknown 4.05.2012 4:09

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

for x:=2 to j do
begin
   if ((d[x]<1000001) and (c[d[x]]=0)) then
      c[d[x]]:=j-x+1;
end;

if ((d[x]<1000001) and (d[x] > 0) and (c[d[x]]=0)) then
   c[d[x]]:=j-x+1;

Автор: kumino 4.05.2012 18:17

Цитата(IUnknown @ 4.05.2012 4:09)

if ((d[x]<1000001) and (d[x] > 0) and (c[d[x]]=0)) then
   c[d[x]]:=j-x+1;

Автор: IUnknown 4.05.2012 19:01

Автор: Гость 4.05.2012 19:48

выдаёт вердикт "Wrong Answer"...