Стоит задача - создать цепочку, в которой будут содержаться все числа от 0000 до 9999, причём длина этой цепочки должна быть минимальной. То есть например у нас есть цепочка из 40к символов - 000000010002...9999, нужно перестав...
Стоит задача - создать цепочку, в которой будут содержаться все числа от 0000 до 9999, причём длина этой цепочки должна быть минимальной. То есть например у нас есть цепочка из 40к символов - 000000010002...9999, нужно переставить цифры местами. По моим подсчётам длина цепочки минимальная равна 10003.
Создал я программку, которая в массив из 40к ячеей закидывает все это. Теперь ,видимо, нужно в цикле смотреть все возможное переборы... но как это реализовать хз... Понятно, что цикл будет while(len(A))>10003:
А что в самом цикле? как уменьшать длину строки? Если есть какие-то идеи, напишите пожалуйста. (Python/Pascal). Важен не сам код, а понимание того, что нужно делать
Гость
Ответ(ы) на вопрос:
Гость{
Если что, часть программы не нужна для построения цепочки. Она просто иллюстрирует, что полученный результат верен.
}
var
sq : array[0..999] of array[0..9] of boolean;
co : array[0..999] of integer;
ar : array[1..10003] of 0..9;
i,j: integer;
x: integer;
t : boolean;
begin
for i := 0 to 999 do
begin
for j := 0 to 9 do
sq[i][j] := false;
co[i] := 0;
end;
for i := 1 to 3 do
ar[i] := 0;
i := 3;
t := true;
{write('000');}
while t do
begin
i := i + 1;
x := ar[i-3]*100 + ar[i-2]*10 + ar[i-1];
if co[x] >= 10 then t := false
else
begin
j := 1;
while sq[x][j] do
j := (j + 1) mod 10;
ar[i] := j;
sq[x][j] := true;
co[x] := co[x] + 1;
{write(j)}
end;
end;
{writeln;}
writeln('Length: ',i - 1);
{просто чтобы убедиться}
for i := 0 to 999 do
for j := 0 to 9 do
sq[i][j] := false;
t := true;
j := 0;
i := 1;
while (i <= 10000) and t do
begin
x := ar[i] * 100 + ar[i+1] * 10 + ar[i+2];
if sq[x][ar[i+3]] then t := false
else
begin
sq[x][ar[i+3]] := true;
j := j + 1;
end;
i := i + 1
end;
if t and (j = 10000) then
write('Confirmed')
end.
Не нашли ответ?
Похожие вопросы