Posted on 2008-08-07 19:36
Hero 閱讀(186)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
/*
ID: wangzha4
LANG: C++
TASK: cowcycle
*/
/*
Test 1: TEST OK [0.011 secs, 2724 KB]
Test 2: TEST OK [0.151 secs, 2720 KB]
Test 3: TEST OK [0.205 secs, 2720 KB]
Test 4: TEST OK [0.421 secs, 2720 KB]
Test 5: TEST OK [0.713 secs, 2720 KB]
Test 6: TEST OK [0.799 secs, 2720 KB]
Test 7: TEST OK [1.544 secs, 2724 KB]
Test 8: TEST OK [1.361 secs, 2720 KB]
*/
//1. 小數據用簡單排序，不要用qsort，會超時
//2. 在判斷的時候乘法比除法快
//3. DFS的時候在遞歸結束的時候一定不要忘了return
//4. 重復第三條
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
const int INF = 1000000 ;
const int size = 155 ;
int inf, inb ;
int fsn, fen, bsn, ben ;
int front[size], back[size] ;
double rate[160] ; int ct_rate ;
double data[160] ;
double best ;
int bfront[size], bback[size] ;
int cmp( const void *a, const void *b )
{
if( *(double *)a - *(double *)b > 0 ) return 1 ;
else return -1 ;
}
void DFS_back( int dep, int tdep, int sn )
{
if( sn > ben ) return ;
back[dep] = sn ;
if( dep == inb ) {
//if( front[inf]*1.0/back[1] - front[1]*1.0/back[inb] * 3.0 < 0 ) return ;
if( front[inf] * back[inb] < back[1] * front[1] * 3 ) return ;
ct_rate = 0 ;
for( int i=1; i<=inf; i++ ) {
for( int j=1; j<=inb; j++ ) {
rate[ct_rate++] = front[i]*1.0 / back[j] ;
}
}
//qsort( rate, ct_rate, sizeof(rate[0]), cmp ) ;
double temp ;
for( int i=ct_rate-1; i>0; i-- ) {
for( int j=0; j<i; j++ ) {
if( rate[j+1] < rate[j] ) {
temp = rate[j] ; rate[j] = rate[j+1]; rate[j+1] = temp ;
}
}
}
double fangcha = 0.0 ; double average = 0.0 ; double sum = 0.0 ;
for( int i=1; i<ct_rate; i++ ) {
data[i] = rate[i] - rate[i-1] ; sum += data[i] ;
}
average = sum / (ct_rate-1) ;
for( int i=1; i<ct_rate; i++ ) {
fangcha += (average-data[i]) * (average-data[i]) ;
}
fangcha = fangcha / (ct_rate-1) ;
if( fangcha < best ) {
for( int i=1; i<=inf; i++ ) bfront[i] = front[i] ;
for( int i=1; i<=inb; i++ ) bback[i] = back[i] ;
best = fangcha ;
}
return ;
}
int maxi = ben - inb + dep + 1 ;
for( int i=1; i+sn<=maxi; i++ ) {
DFS_back( dep+1, tdep, sn+i ) ;
}
}
void DFS_front( int dep, int tdep, int sn )
{
if( sn > fen ) return ;
front[dep] = sn ;
if( dep == inf ) {
for( int j=bsn; j<=ben-inb+1; j++ ) {
DFS_back( 1, inb, j ) ;
}
return ;
}
int maxi = fen - inf + dep + 1 ;
for( int i=1; i+sn<=maxi; i++ ) {
DFS_front( dep+1, tdep, sn+i ) ;
}
}
int main()
{
freopen( "cowcycle.in", "r", stdin ) ;
freopen( "cowcycle.out","w",stdout ) ;
scanf( "%d %d", &inf, &inb ) ;
scanf( "%d %d %d %d", &fsn, &fen, &bsn,&ben ) ;
best = (double)INF ;
for( int i=fsn; i<=fen-inf+1; i++ )
DFS_front( 1, inf, i ) ;
for( int i=1; i<inf; i++ ) printf( "%d ", bfront[i] ) ; printf( "%d\n", bfront[inf] ) ;
for( int i=1; i<inb; i++ ) printf( "%d ", bback[i] ) ; printf( "%d\n", bback[inb] ) ;
return 0 ;
}