Cod sursa(job #2429435)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 9 iunie 2019 17:01:52
Problema Perb Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int f[5],s[610];
vector <int> prim[610];
int solve (int l,int r,int len){
    int sol,i,j;
    sol=0;
    for (i=1;i<=len;i++){
        f[0]=f[1]=f[2]=f[3]=0;
        for (j=l+i-1;j<=r;j+=len)
            f[s[j]]++;
        sol = sol + f[0] + f[1] + f[2] + f[3] - max(max (f[0],f[1]),max(f[2],f[3]));
    }
    return sol;
}
int main()
{
    FILE *fin=fopen ("perb.in","r");
    FILE *fout=fopen ("perb.out","w");
    int n,q,i,st,dr,l,d,sol,x;
    char c;
    fscanf (fin,"%d%d\n",&n,&q);
    for (i=1;i<=n;i++){
        c= fgetc (fin);
        if (c=='A')
            s[i] = 0;
        else if (c=='C')
            s[i] = 1;
        else if (c=='G')
            s[i] = 2;
        else s[i] = 3;
    }
    for (i=1;i<=n;i++){
        l = i;
        d = 2;
        while (d*d<=l){
            if (l%d==0){
                prim[i].push_back(d);
                while (l%d==0)
                    l/=d;
            }
            d++;
        }
        if (l!=1 && l!=i)
            prim[i].push_back(l);
    }
    for (;q;q--){
        fscanf (fin,"%d%d",&st,&dr);
        l = dr - st + 1;

        if (prim[l].empty()){ /// l = prim
            sol = solve (st,dr,1);
        }
        else {
            sol = n;
            for (int j=0;j<prim[l].size();j++)
                sol = min ( sol , solve (st,dr,l/prim[l][j]));
        }
        fprintf (fout,"%d\n",sol);

    }
    return 0;
}