#include #include typedef struct { int predchozi; int minci; } castka_t; #define INFINITY 0x4fffffff //Takto se pozná něco, co nejde zaplatit void pridej( castka_t castky[], int mince, int index, int limit ) { int nova = index + mince; if( nova < 0 || nova > limit ) //mimo rozsah return; if( castky[ index ].minci + 1 < castky[ nova ].minci ) { castky[ nova ].predchozi = index; castky[ nova ].minci = castky[ index ].minci + 1; } } int main( int argc, const char *argv[] ) { int n, m, p, vil_celkem, han_celkem; float prep; //Dočasné, na nehaléřové hodnoty scanf( "%d%d%f", &n, &m, &prep ); p = ( int ) ( prep * 100 ); //Převod na haléře int mince[ m + n ]; vil_celkem = han_celkem = 0; for( int i = 0; i < m + n; ++ i ) { float nova; scanf( "%f", &nova ); nova *= 100; //Převod na haléře mince[ i ] = ( int ) nova; if( i >= n ) { han_celkem += mince[ i ]; mince[ i ] *= -1; //Handléřovy mince "vracejí" } else { vil_celkem += mince[ i ]; } } int limit = han_celkem + p; //Vybrat vhodný rozsah pole if( vil_celkem < limit ) limit = vil_celkem; if( p > limit ) { printf( "Na to Vilda nemá\n" ); return 0; } if( p < 0 ) { printf( "Nepodporujeme záporné koně\n" ); return 0; } castka_t castky[ limit + 1 ]; for( int i = 1; i <= limit; ++ i ) { castky[ i ].minci = INFINITY; } castky[ 0 ].predchozi = 0; castky[ 0 ].minci = 0; for( int i = 0; i < n; ++ i ) //Opačně, abychom nenacházeli z této fáze for( int j = limit; j >= 0; -- j ) pridej( castky, mince[ i ], j, limit ); for( int i = n; i < n + m; ++ i ) //Záporné mince -> tímto směrem for( int j = 0; j <= limit; ++ j ) pridej( castky, mince[ i ], j, limit ); if( castky[ p ].minci == INFINITY ) { printf( "Koně zaplatit nelze\n" ); return 0; } while( p ) { printf( "%f\n", ( p - castky[ p ].predchozi ) / 100.0 ); p = castky[ p ].predchozi; } return 0; }