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;
}