//Данный алгоритм использует большое количество системных ресурсов. Например, для 10000 результат вычислялся 2 минуты, ну Вы поняли. Приношу свои извинения. //PascalABC.NET 3.2 сборка 1318
Var ma:array of string; arr:array of integer; n,GroupCount,i,j,CountOfFails,k,mass:integer; b:boolean; s:string; begin GroupCount:=1; CountOfFails:=0; b:=true; read(n); setlength(ma,GroupCount); ma[0]:='1,'; for i:=2 to n do begin for j:=0 to GroupCount-1 do begin s:=ma[j]; mass:=0; while pos(',',s)<>0 do begin inc(mass); setlength(arr,mass); arr[mass-1]:=strtoint(copy(s,1,pos(',',s)-1)); delete(s,1,pos(',',s)); end; for k:=0 to mass-1 do if i mod arr[k]=0 then begin b:=false; inc(CountOfFails); break; end; if b=true then begin ma[j]+=inttostr(i)+','; break; end; if (b=false) and (CountOfFails=GroupCount) then begin inc(GroupCount); setlength(ma,GroupCount); ma[j+1]:=inttostr(i)+','; end; b:=true; end; CountOfFails:=0; b:=true; end; {writeln('End of main cycle reached'); //если хочется посмотреть разбивку for j:=0 to GroupCount-1 do writeln('Group #',j+1,':',ma[j]); writeln('---------------------');} writeln(GroupCount); end.
Answers & Comments
Verified answer
//Данный алгоритм использует большое количество системных ресурсов. Например, для 10000 результат вычислялся 2 минуты, ну Вы поняли. Приношу свои извинения.//PascalABC.NET 3.2 сборка 1318
Var
ma:array of string;
arr:array of integer;
n,GroupCount,i,j,CountOfFails,k,mass:integer;
b:boolean;
s:string;
begin
GroupCount:=1;
CountOfFails:=0;
b:=true;
read(n);
setlength(ma,GroupCount);
ma[0]:='1,';
for i:=2 to n do
begin
for j:=0 to GroupCount-1 do
begin
s:=ma[j];
mass:=0;
while pos(',',s)<>0 do
begin
inc(mass);
setlength(arr,mass);
arr[mass-1]:=strtoint(copy(s,1,pos(',',s)-1));
delete(s,1,pos(',',s));
end;
for k:=0 to mass-1 do
if i mod arr[k]=0 then
begin
b:=false;
inc(CountOfFails);
break;
end;
if b=true then
begin
ma[j]+=inttostr(i)+',';
break;
end;
if (b=false) and (CountOfFails=GroupCount) then
begin
inc(GroupCount);
setlength(ma,GroupCount);
ma[j+1]:=inttostr(i)+',';
end;
b:=true;
end;
CountOfFails:=0;
b:=true;
end;
{writeln('End of main cycle reached'); //если хочется посмотреть разбивку
for j:=0 to GroupCount-1 do
writeln('Group #',j+1,':',ma[j]);
writeln('---------------------');}
writeln(GroupCount);
end.
Пример ввода:
10000
Пример вывода:
14