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

Nguồn đề bài: http://vn.spoj.com/problems/BLGEN/

1. Đề thi olympic 30/4/2014 Môn tin học khối 10

Tế bào của một cá thể sinh vật ngoài hành tinh mới được phát hiện gồm rất nhiều gen, mỗi gen trong chuỗi gen của tế bào đều có số lượng nào đó các nucleotide (ký hiệu là nu). Các chuyên gia thường quan tâm chuỗi gen của mỗi cá thể dưới góc độ một chuỗi số lượng tương ứng các nu (gọi tắt là chuỗi nu), do đó chuỗi sẽ như là một dãy số nguyên dương đồng thời số số hạng của dãy này sẽ được gọi là độ dài của chuỗi. Mỗi gen được xem là đặc biệt nếu số nu của nó hoặc là bình phương của một số nguyên hoặc là lập phương của một số nguyên tố.

Để nghiên cứu khả năng biến đổi gen của loài sinh vật nói trên, các nhà khoa học xem xét hai mẫu chuỗi nu của hai cá thể và quan tâm đến mức độ “giống nhau” giữa chúng theo cách tìm ra chuỗi con chỉ gồm các gen đặc biệt mà cùng xuất hiện ở cả hai chuỗi nu (mỗi chuỗi con như vậy đều được gọi là chuỗi đặc trưng chung của hai chuỗi nu). Lưu ý rằng, chuỗi con của một chuỗi nu X, là chuỗi thu được từ X bằng cách giữ nguyên tất cả hoặc loại bỏ đi một số nào đó các gen mà vẫn giữ thứ tự xuất hiện trong chuỗi X.

Yêu cầu : Xác định độ dài lớn nhất L của chuỗi đặc trưng chung của hai chuỗi nu cho trước.

Dữ liệu vào

  – Dòng đầu ghi lần lượt các số hạng của chuỗi nu thứ nhất.

– Dòng tiếp theo ghi lần lượt các số hạng của chuỗi nu thứ hai.

– Tất cả các số hạng của hai chuỗi đều nguyên dương và không vượt quá 1019.

  -Độ dài của mỗi chuỗi nu đều không vượt quá 1000.

Kết quả

– Ghi ra  duy nhất một số nguyên L tìm được.

Ví dụ

Input :

2 9 8 4 1 27 4 6

5 6 9 1 8 2 6 27 1 4

Output :

4

(Giải thích: L = 4, một trong các chuỗi đăc trưng chung là: 9, 1, 27, 4)

Ràng buộc : 60% số test ứng với 60% số điểm của bài ứng với tình huống độ dài của hai chuỗi nu  không vượt

quá 255 và giá trị của mỗi số hạng đều không vượt quá 106

2. Thuật toán BLGEN spoj

– Từ mỗi dãy đã cho ta loại đi những số không phải là chính phương hoặc không phải là lập phượng của số nguyên tố, có thể dùng SÀNG SNT + (chặt NP hoặc công thức tính căn bậc 3).

– Tiếp theo dùng QHĐ tìm dãy con chung dài nhất thì sẽ thu được kết quả bài toán.

 

3. code tham khảo BLGEN spoj c++ và pascal

a. Code c++

#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]);
}

b. code pascal

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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *