BLGEN spoj – Chuỗi gen đặc trưng

#include<stdio.h> #include<math.h> #include<vector> #include<iostream> #include<string> #include<sstream> #include<map> using namespace std; typedef long long unsigned llu; bool check[2200000]={false}; int c[1001][1001]; map<llu,int> name; int main() { //freopen("test.inp.c","r",stdin); int n,m,i,j; string s; llu t,k; vector<llu> a,b; for(i=2;i<2154440;++i) if(!check[i]) { t=(llu)i; name[t*t*t]=1; for(j=2;j*i<2154440;++j) check[i*j]=true; } getline(cin,s); stringstream ss(s); while(ss>>k) { t=sqrt(k); if(k==(t*t)) a.push_back(k); else if(name.find(k)!=name.end()) a.push_back(k); } getline(cin,s); stringstream sss(s); while(sss>>k) { t=sqrt(k); if(k==t*t) b.push_back(k); else if(name.find(k)!=name.end()) b.push_back(k); } m=a.size(); n=b.size(); for(i=0;i<m;++i) c[i][0]=0; for(j=0;j<n;++j) c[0][j]=0; for(i=1;i<=m;++i) for(j=1;j<=n;++j) if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1]+1; else c[i][j]=max(c[i-1][j],c[i][j-1]); printf("%d",c[m][n]); }

uses math; const fi='; nmax=1000; maxsang=2154434; type data=longint; mang=array[0..nmax+1] of qword; var f:text; A,B:mang; n,m:data; SNT:array[0..maxsang] of boolean; C:array[0..nmax+1,0..nmax+1] of data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); n:=0; m:=0; while not seekeoln(f) do begin inc(n); read(f,a[n]); end; readln(f); while not seekeoln(f) do begin inc(m); read(f,b[m]); end; close(f); end; function cp(n:qword):boolean; begin exit(sqr(trunc(sqrt(n)))=n); end; function ktlpsnt(n:qword):boolean; var so:qword; begin so:=round(exp(ln(n)/3)); if so*so*so <> n then exit(false); if not snt[so] then exit(false); exit(true); end; procedure LOC(var A:mang; var n:data); var i,spt:data; begin spt:=0; for i:=1 to n do if cp(a[i]) or ktlpsnt(a[i]) then begin inc(spt); A[spt]:=a[i]; end; n:=spt; end; procedure sangnt; var i,j:data; begin fillchar(snt,sizeof(snt),true); snt[1]:=false; i:=2; while i<=trunc(sqrt(maxsang)) do begin while snt[i]=false do inc(i); for j:=2 to maxsang div i do snt[i*j]:=false; inc(i); end; end; procedure QHD; var i,j:data; begin for i:= 0 to n do c[i,0]:=0; for j:=0 to m do c[0,j]:=0; for i:=1 to n do for j:=1 to m do if a[i]=b[j] then c[i,j]:=c[i-1,j-1]+1 else c[i,j]:=max(c[i-1,j],c[i,j-1]); writeln(c[n,m]); end; begin docfile; sangnt; loc(a,n); loc(b,m); QHD; end.