首页 > 代码库 > usaco-3.2-ratios-pass

usaco-3.2-ratios-pass

这个配比问题,呵呵,线性代数知识,枚举吧,这个数量小。

/*ID: qq104801LANG: C++TASK: ratios*/#include <iostream>#include <fstream>#include <bitset>#include <cstdio>#include <algorithm>using namespace std;int goal[3];int ii[3][3];int ans[4];int minsum=100000;inline int asum(int in,int i,int j,int k){    return ii[0][in]*i+ii[1][in]*j+ii[2][in]*k;}inline int xsum(int i,int j,int k){    return asum(0,i,j,k)+asum(1,i,j,k)+asum(2,i,j,k);}void test(){        freopen("ratios.in","r",stdin);    freopen("ratios.out","w",stdout);    int isum=0;    for(int i=0;i<3;i++)    {        cin>>goal[i];        isum+=goal[i];    }    for(int i=0;i<3;i++)        for(int j=0;j<3;j++)            cin>>ii[i][j];    if(isum==0)    {        cout<<"0 0 0 0"<<endl;        return;    }    for(int i=0;i<100 && i<minsum;i++)        for(int j=0;j<100 && j<minsum;j++)            for(int k=0;k<100 && k<minsum;k++)            {                if(i+j+k==0)continue;                int cc[3];                for(int c=0;c<3;c++)                    cc[c]=asum(c,i,j,k);                if(cc[0]*goal[1]!=cc[1]*goal[0])continue;                if(cc[1]*goal[2]!=cc[2]*goal[1])continue;                if(cc[0]<goal[0] || cc[1]<goal[1]                     || cc[2]<goal[2]) continue;                minsum=i+j+k;            ans[0]=i;ans[1]=j;ans[2]=k;            ans[3]=xsum(i,j,k)/isum;            }            if(ans[0]+ans[1]+ans[2]==0)            {                cout<<"NONE"<<endl;                return;            }            cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;}int main () {            test();            return 0;}

test data:

USACO TrainingGrader Results     10 users onlineCHN/4 USA/6USER: cn tom [qq104801]TASK: ratiosLANG: C++Compiling...Compile: OKExecuting...   Test 1: TEST OK [0.008 secs, 3376 KB]   Test 2: TEST OK [0.011 secs, 3376 KB]   Test 3: TEST OK [0.008 secs, 3376 KB]   Test 4: TEST OK [0.022 secs, 3376 KB]   Test 5: TEST OK [0.027 secs, 3376 KB]   Test 6: TEST OK [0.011 secs, 3376 KB]All tests OK.YOUR PROGRAM (‘ratios‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----5 8 03 5 41 3 06 2 0------- test 2 ----3 4 51 2 33 7 12 1 2------- test 3 ----20 22 244 5 59 5 612 12 14------- test 4 ----80 85 8098 97 9689 87 8878 79 80------- test 5 ----99 99 991 0 00 1 00 0 1------- test 6 ----93 95 9798 0 00 98 00 0 98Keep up the good work!Thanks for your submission!

 

usaco-3.2-ratios-pass