Poj Solution 2765

http://poj.org/problem?id=2765

#include <stdio.h>
#include <string.h>


struct product{
    char w[100];
    char name[110][100];
    int per[110];
    int most[110], least[110];
    int m;
}p[10];

int n;

void clac( product &a ) {
    int s = 0, r = 100, i, j, k, low[100], up[100], sum, sh, rh;

    for( i=a.m-1; i>=0; i-- ) {
        if( a.per[i] != -1 ) {
            s = a.per[i];        // be sure that per[i] >= s;
            a.most[i] = a.least[i] = a.per[i];
        }
        else if( s < 1 )
            s = 1;

        low[i] = s;
        r -= s;
    }

    s = 100;
    sum = 0;
    for( i=0; i<a.m; i++ ) {
        if( a.per[i] != -1 ) {
            s = a.per[i];        // be sure that per[i] <= s;
        }
        up[i] = s;
        sum += up[i] - low[i];
    }

    for( i=0; i<a.m; i++ ) 
    if( a.per[i] == -1 ){
        a.most[i] = low[i];
        a.least[i] = up[i];

        for( j=low[i]; j<=up[i]; j++ ) {
            sh = sum;
            rh = r;
            
            for( k=i; k<a.m && j < up[k]; k++ )
                sh -= up[k] - j;
            for( k=i; k>=0 && j > low[k]; k-- ) {
                sh -= j - low[k];
                rh -= j - low[k];
            }

            if( rh >= 0 && rh <= sh ) {
                if( a.least[i] > j )
                    a.least[i] = j;
                if( a.most[i] < j )
                    a.most[i] = j;
            }
        }//for
    }//if

}

int get_most( product &a, char *w ) {
    int i;
    for( i=0; i<a.m; i++ )
        if( strcmp( a.name[i], w ) == 0 )
            return a.most[i];
    return 0;
}

int get_least( product &a, char *w ) {
    int i;
    for( i=0; i<a.m; i++ )
        if( strcmp( a.name[i], w ) == 0 )
            return a.least[i];
    return 0;
}
void query_most( char *w ) {
    int i, l = -1, t;
    bool key = false;
    for( i=0; i<n; i++ ) {
        t = get_least( p[i], w );
        if( t > l )
            l = t;
    }

    for( i=0; i<n; i++ )
        if( get_most( p[i], w ) >= l ) {
            if( key ) printf( " " );
            printf( "%s", p[i].w );
            key = true;
        }
    printf( "n" );
}
        
void query_least( char *w ) {
    int i, l = 200, t;
    bool key = false;
    for( i=0; i<n; i++ ) {
        t = get_most( p[i], w );
        if( t < l )
            l = t;
    }

    for( i=0; i<n; i++ )
        if( get_least( p[i], w ) <= l ) {
            if( key ) printf( " " );
            printf( "%s", p[i].w );
            key = true;
        }
    printf( "n" );
}

bool input( ) {
    int i, j;
    char c;
    scanf( "%d", &n );
    if( n <= 0 )
        return false;

    for( i=0; i<n; i++ ) {
        scanf( "%s", p[i].w );
        scanf( "%d", &p[i].m );
        for( j=0; j<p[i].m; j++ ) {
            scanf( "%s", p[i].name[j] );
            c = getchar();
            if( c != 'n' )
                scanf( "%d%%", &p[i].per[j] );
            else
                p[i].per[j] = -1;
        }
    }

    for( i=0; i<n; i++ )
        clac( p[i] );
    return true;
}

int main( ) {
    int t;
    char w1[100], w2[100];
    while( input( ) ) {
        scanf( "%d", & t );
        while( t-- ) {
            scanf( "%s %s", w1, w2 );
            if( w1[0] == 'm' )
                query_most( w2 );
            else
                query_least( w2 );
        }
    }

    return 0;
}