Cod sursa(job #1729427)

Utilizator mircea_marian.popaPopa Mircea-Marian mircea_marian.popa Data 14 iulie 2016 18:18:51
Problema Secventa 3 Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 7.57 kb
#include <stdio.h>
#include <stdlib.h>
#include<time.h>

unsigned short len, dim = 500;
unsigned int *sumDataC, *sumDataT;

void getValMem(unsigned short n, unsigned short data[2][n] , unsigned short i1 , unsigned short i2 , float *val ,
    unsigned short u ){
    unsigned short a = i2 - i1 + 1;
    if( a == u ) {
        //printf("i1=%d i2=%d\n" , i1, i2);
        /*unsigned short i;
        unsigned int sc = 0 , st = 0;
        for(i = i1 ; i <= i2 ; i++ ){
            sc += data[0][i];
            st += data[1][i];
            //printf("%d %d " , data[0][i], data[1][i]);
        }
        //printf("\n  ");
        float rez = ((float)sc)/st;
        //printf("(a==u): %d %d %.2f\n", i1, i2, rez);
        if( rez > *val )
            //{*val = rez;printf("(a==u): %d %d %.2f %d %d\n", i1, i2, rez, sc , st);}
            *val = rez;*/
        unsigned int sc = 0, st = 0;
        unsigned short i = i1;
        while( i % dim &&  i < i2 ){
            sc += data[0][i];
            st += data[1][i];
            i++;
        }
        while(i + dim <= i2 ){
            sc += sumDataC[i%dim];
            st += sumDataT[i%dim];
            i+=dim;
        }
        while(i < i2){
            sc += data[0][i];
            st += data[1][i];
            i++;
        }
        float rez = ((float)sc)/st;
        //printf("(a==u): %d %d %.2f\n", i1, i2, rez);
        if( rez > *val )
            *val = rez;
    } else if( a > u ) {
        unsigned short m = (i1 + i2)/2, i, k, start, stop;
        unsigned int sc , st;
        float rez;
        getValMem(n,data,i1,m,val,u);
        getValMem(n,data,m+1,i2,val,u);
        if( u != 1 ){
            stop = m + 1;
            sc = data[0][m] + data[0][stop];
            st = data[1][m] + data[1][stop];
            k = 2;
            start = m;
            /*while( k < u && stop < i2 ){
                stop ++;
                k ++;
                sc += data[0][stop];
                st += data[1][stop];
            }
            while(k < u && start > i1 ){
                start --;
                k ++;
                sc += data[0][start];
                st += data[1][start];
            }*/

            while( k < u && stop < i2 && stop % dim ){
                stop ++;
                k ++;
                sc += data[0][stop];
                st += data[1][stop];
            }
            while( k + dim <= u && stop + dim <= i2 ){
                sc +=  sumDataC[stop%dim];
                st +=  sumDataT[stop%dim];
                stop += dim;
                k+=dim;
            }
            while( k < u && stop < i2 ){
                stop ++;
                k ++;
                sc += data[0][stop];
                st += data[1][stop];
            }

            while(k < u && start > i1 && start % dim ){
                start --;
                k ++;
                sc += data[0][start];
                st += data[1][start];
            }
            while( k + dim <= u && start - dim >= i1 ){
                sc +=  sumDataC[start%dim];
                st +=  sumDataT[start%dim];
                start -= dim;
                k+=dim;
            }
            while(k < u && start > i1 ){
                start --;
                k ++;
                sc += data[0][start];
                st += data[1][start];
            }


            rez = (1.0 * sc)/st;
            //printf("(a>u): %d %d %.2f\n", m-c, b , rez);
            if( rez > *val )
                *val = rez;
            while( start > i1 ){
                start --;
                sc += data[0][start];
                st += data[1][start];
                sc -= data[0][stop];
                st -= data[1][stop];
                stop--;
                rez = (1.0 * sc)/st;
                //printf("(a>u): %d %d %.2f\n", m-c, b , rez);
                if( rez > *val )
                    *val = rez;
            }
        }
    }
}

void getVal(unsigned short n, unsigned short data[2][n] , unsigned short i1 , unsigned short i2 , float *val ,
    unsigned short u ){
    unsigned short a = i2 - i1 + 1;
    if( a == u ) {
        //printf("i1=%d i2=%d\n" , i1, i2);
        unsigned short i;
        unsigned int sc = 0 , st = 0;
        for(i = i1 ; i <= i2 ; i++ ){
            sc += data[0][i];
            st += data[1][i];
            //printf("%d %d " , data[0][i], data[1][i]);
        }
        //printf("\n  ");
        float rez = ((float)sc)/st;
        //printf("(a==u): %d %d %.2f\n", i1, i2, rez);
        if( rez > *val )
            //{*val = rez;printf("(a==u): %d %d %.2f %d %d\n", i1, i2, rez, sc , st);}
            *val = rez;
    } else if( a > u ) {
        unsigned short m = (i1 + i2)/2, i, k, start, stop;
        unsigned int sc , st;
        float rez;
        getVal(n,data,i1,m,val,u);
        getVal(n,data,m+1,i2,val,u);
        if( u != 1 ){
            stop = m + 1;
            sc = data[0][m] + data[0][stop];
            st = data[1][m] + data[1][stop];
            k = 2;
            start = m;
            while( k < u && stop < i2 ){
                stop ++;
                k ++;
                sc += data[0][stop];
                st += data[1][stop];
            }
            while(k < u && start > i1 ){
                start --;
                k ++;
                sc += data[0][start];
                st += data[1][start];
            }
            rez = (1.0 * sc)/st;
            //printf("(a>u): %d %d %.2f\n", m-c, b , rez);
            if( rez > *val )
                *val = rez;
            while( start > i1 ){
                start --;
                sc += data[0][start];
                st += data[1][start];
                sc -= data[0][stop];
                st -= data[1][stop];
                stop--;
                rez = (1.0 * sc)/st;
                //printf("(a>u): %d %d %.2f\n", m-c, b , rez);
                if( rez > *val )
                    *val = rez;
            }
        }
    }
}

int main(){
    FILE * fi = fopen("secv3.in","rt");
    unsigned short n, l, u, i;
    fscanf( fi , "%hd %hd %hd\n" , &n , &l , &u );
    unsigned short data[2][n];
    n--;
    for(i = 0 ; i < n ; i++ )
        fscanf( fi , "%hd " , &data[0][i] );
    fscanf( fi , "%hd\n" , &data[0][n] );
    for(i = 0 ; i < n ; i++ )
        fscanf( fi , "%hd " , &data[1][i] );
    fscanf( fi , "%hd" , &data[1][n] );
    n++;
    //for(i = 0 ; i < n ; i++ )
        //printf( "%hd " , data[1][i] );
    fclose(fi);
    clock_t t = clock();
    fi = fopen("secv3.out","wt");
    if( l == n ){
        unsigned int sc = 0 , st = 0;
        for(i = 0 ; i < n ; i++ ){
            sc += data[0][i];
            st += data[1][i];
        }
        fprintf(fi,"%.2f", (1.0 * sc) / st );
    } else if( u - l < 10000 ){
    //} else if( 1 ){
        float val = 0;
        for( i = l ; i <= u ; i++ )
            getVal(n,data,0,n-1,&val,i);
        fprintf(fi,"%.2f", val );
    //}
    } else {
        len = n / dim;
        if( n % dim != 0 )
            len ++;
        sumDataC = (unsigned int *)malloc(len * sizeof(unsigned int));
        sumDataT = (unsigned int *)malloc(len * sizeof(unsigned int));

        unsigned short k, a, b;

        for( i = 0 ; i < n ; i += dim ){
            a = i % dim;
            b = i + dim;
            sumDataC[a] = sumDataT[a] = 0;
            for( k = i ; k < b && k < n ; k++ ){
                sumDataC[a] += data[0][k];
                sumDataT[a] += data[1][k];
            }
        }

        float val = 0;
        for( i = l ; i <= u ; i++ )
            getValMem(n,data,0,n-1,&val,i);
        fprintf(fi,"%.2f", val );

        free(sumDataC);
        free(sumDataT);
    }
    fclose(fi);
    //printf("%f\n",( (float)clock() - t ) / CLOCKS_PER_SEC );
    return 0;
}