青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

USACO Section 3.2 Feed Ratios

Feed Ratios

1998 ACM Finals, Dan Adkins

Farmer John feeds his cows only the finest mixture of cow food, which has three components: Barley, Oats, and Wheat. While he knows the precise mixture of these easily mixable grains, he can not buy that mixture! He buys three other mixtures of the three grains and then combines them to form the perfect mixture.

Given a set of integer ratios barley:oats:wheat, find a way to combine them IN INTEGER MULTIPLES to form a mix with some goal ratio x:y:z.

For example, given the goal 3:4:5 and the ratios of three mixtures:

1:2:3
3:7:1
2:1:2
your program should find some minimum number of integer units (the `mixture') of the first, second, and third mixture that should be mixed together to achieve the goal ratio or print `NONE'. `Minimum number' means the sum of the three non-negative mixture integers is minimized.

For this example, you can combine eight units of mixture 1, one unit of mixture 2, and five units of mixture 3 to get seven units of the goal ratio:

    8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)

Integers in the goal ratio and mixture ratios are all non-negative and smaller than 100 in magnitude. The number of units of each type of feed in the mixture must be less than 100. The mixture ratios are not linear combinations of each other.

PROGRAM NAME: ratios

INPUT FORMAT

Line 1: Three space separated integers that represent the goal ratios
Line 2..4: Each contain three space separated integers that represent the ratios of the three mixtures purchased.

SAMPLE INPUT (file ratios.in)

3 4 5
1 2 3
3 7 1
2 1 2

OUTPUT FORMAT

The output file should contain one line containing four integers or the word `NONE'. The first three integers should represent the number of units of each mixture to use to obtain the goal ratio. The fourth number should be the multiple of the goal ratio obtained by mixing the initial feed using the first three integers as mixing ratios.

SAMPLE OUTPUT (file ratios.out)

8 1 5 7

Analysis

This problem seems to be a deoth search problem, which, as a matter of fact, is truly a mathematical problem. This problem can be represented in forms of matrix multiply or a linear equation set.

Initially, the first line is saved in an array called b[MAX](MAX here is 3, but generally, we can deal with more complicated situations in this way by change the value of MAX).

What the next MAX lines can do is also and may function better with a MAX-level matrix A[MAX][MAX](squred). Firstly, turn the description into equations:

\large \left\{\begin{matrix}
a_{00}x_{0}+a_{01}x_{1}+a_{02}x_{2}=b_{0}\\ 
a_{10}x_{0}+a_{11}x_{1}+a_{12}x_{2}=b_{1}\\ 
a_{20}x_{0}+a_{21}x_{1}+a_{22}x_{2}=b_{2}
\end{matrix}\right.
Later, using matrix to translate it:
 
\large \begin{pmatrix}
a_{00} & a_{01} & a_{02}\\ 
a_{10} & a_{11} & a_{12}\\ 
a_{20} & a_{21} & a_{22}
\end{pmatrix}.\begin{pmatrix}
x_{0}\\ 
x_{1}\\ 
x_{2}
\end{pmatrix}=\begin{pmatrix}
b_{0}\\ 
b_{1}\\ 
b_{2}
\end{pmatrix}
It is obvious to find the solution of the equation set by Cramer Law. But I nearly forget to tell you another important thing, which is as important as the mathematical method, is that if det(A) is 0 and not all of the elements in b[MAX] are 0, then the answer is NONE. What's more, as a practical problem, it is unbelievable to find the answer which is negative. Both are the edges to determine whether the answer is avaliable.

After this, you may be interested in find det(A), and I will describe it in another post.

Code
/*
ID:braytay1
PROG:ratios
LANG:C++
*/

#include 
<iostream>
#include 
<cmath>
#include 
<fstream>
#define MAX 3
#define eps 0.000001
using namespace std;

int det(int a[MAX][MAX]){
    
double s=1;
    
double tmp[MAX][MAX];
    
for (int i=0;i<MAX;i++){
        
for (int j=0;j<MAX;j++){
            tmp[i][j]
=double(a[i][j]);
        }

    }

    
for (int k=0;k<MAX-1;k++){
        
for (int i=k+1;i<MAX;i++){        
            
for (int j=k+1;j<MAX;j++){
                tmp[i][j]
-=tmp[i][k]*tmp[k][j]/tmp[k][k];
            }

        }

    }

    
for (int i=0;i<MAX;i++)
        s
*=tmp[i][i];
    
int res;
    res
=int(s);
    
if (fabs(s-res)<eps) return res;
    
else {
        
if (res>0return res+1;
        
else return res-1;
    }

}

int sp_gcd(int a,int b){
    a
=abs(a);
    b
=abs(b);
    
if (a<b) return a==0?b:sp_gcd(b%a,a);
    
else return b==0?a:sp_gcd(b,a%b);
}


int gcd(int a[MAX],int s){
    
int res;
    res
=sp_gcd(a[0],a[1]);
    
for (int i=2;i<MAX;i++){
        res
=sp_gcd(res,a[i]);
    }

    res
=sp_gcd(res,s);
    
return res;
}

int main(){
    ifstream fin(
"ratios.in");
    ofstream fout(
"ratios.out");
    
int A[MAX][MAX],b[MAX],x[MAX];
    
int k,flag_s=0;
    
for (int i=0;i<MAX;i++){
        fin
>>b[i];
        
if (b[i]) flag_s=1;
    }

    
for (int i=0;i<MAX;i++)
        
for (int j=0;j<MAX;j++) fin>>A[j][i];
    k
=det(A);
    
if (k==0&&flag_s) cout<<"NONE"<<endl;
    
else {
        
int k_sign;
        
if (k>0) k_sign=1;
        
else if (k==0) k_sign=0;
        
else k_sign=-1;
        
for (int i=0;i<MAX;i++){
            
int A_tmp[MAX][MAX];
            
for (int i1=0;i1<MAX;i1++){
                
for (int j1=0;j1<MAX;j1++){
                    
if (j1==i) A_tmp[i1][j1]=b[i1];
                    
else A_tmp[i1][j1]=A[i1][j1];
                }

            }

            x[i]
=det(A_tmp);
        }


        
int div;
        div
=gcd(x,k);
        
for (int i=0;i<MAX;i++){
            
if (x[i]*k_sign<0{
                fout
<<"NONE"<<endl;
                
return 0;
            }

        }

        
for (int i=0;i<MAX;i++){
            x[i]
=x[i]/div*k_sign;
            fout
<<x[i]<<" ";
        }

        k
=k/div*k_sign;
        fout
<<k<<endl;
    }

    
return 0;
}

posted on 2008-08-26 00:46 幻浪天空領(lǐng)主 閱讀(403) 評(píng)論(0)  編輯 收藏 引用 所屬分類: USACO

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(1)

隨筆檔案(2)

文章分類(23)

文章檔案(22)

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美一区二区视频观看视频| 中文有码久久| 美日韩精品视频免费看| 亚洲第一精品福利| 亚洲国产日韩精品| 欧美日本精品在线| 亚洲综合日韩| 欧美一级视频一区二区| 伊人成人开心激情综合网| 麻豆国产精品va在线观看不卡| 久久久久久久久久看片| 91久久精品一区二区三区| 亚洲人成在线播放| 国产精品人人爽人人做我的可爱 | 国产精品xxxxx| 欧美一区精品| 亚洲午夜在线| 亚洲欧美偷拍卡通变态| 亚洲高清资源| 一区二区三区久久网| 黄网站色欧美视频| 性色av一区二区三区红粉影视| 久久gogo国模啪啪人体图| 亚洲片国产一区一级在线观看| 一区二区三区三区在线| 亚洲成色777777女色窝| 在线一区二区三区做爰视频网站| 黄色成人免费观看| 一本色道久久综合狠狠躁篇的优点 | 老司机免费视频久久| 欧美精品久久一区| 久久一区二区三区超碰国产精品| 欧美日韩亚洲一区二区三区| 久久尤物视频| 国产精品永久免费| 亚洲欧洲在线看| 黄色成人在线观看| 亚洲一区二区三区国产| 亚洲美女精品成人在线视频| 久久精品国产一区二区电影| 亚洲综合日本| 欧美日韩在线不卡| 亚洲高清不卡| 一区二区在线观看视频| 午夜精品久久久久影视| 亚洲伊人伊色伊影伊综合网| 欧美91精品| 欧美成人一区在线| 极品尤物久久久av免费看| 亚洲欧美日韩在线高清直播| 亚洲一二三区在线| 欧美日韩国产色站一区二区三区| 欧美va天堂| 女生裸体视频一区二区三区| 久久婷婷国产综合尤物精品| 国产亚洲精品激情久久| 亚洲一区二区三区免费在线观看| 一区二区三区欧美在线| 欧美理论在线| 日韩午夜精品| 中文久久乱码一区二区| 欧美日本精品| 日韩网站在线| 亚洲一区二区三区乱码aⅴ蜜桃女| 欧美黄色小视频| 91久久午夜| 亚洲精品在线免费| 欧美日韩不卡合集视频| 亚洲精品影院| 亚洲一区观看| 国产欧美日韩精品丝袜高跟鞋 | 久久伊人精品天天| 极品少妇一区二区| 欧美岛国在线观看| 99精品久久免费看蜜臀剧情介绍| 亚洲午夜性刺激影院| 国产精品都在这里| 欧美一级视频一区二区| 免费在线看成人av| 日韩视频中文字幕| 国产精品极品美女粉嫩高清在线| 亚洲女人天堂av| 美女免费视频一区| 日韩午夜免费| 国产精品一区视频| 另类欧美日韩国产在线| 亚洲欧洲日本国产| 欧美一区二区三区四区夜夜大片| 国产一区二区久久| 欧美精品18videos性欧美| 亚洲一二区在线| 久久五月天婷婷| 一区二区成人精品| 国产综合婷婷| 欧美精品日韩一区| 欧美在线视频播放| 亚洲日韩欧美视频一区| 久久精品国产一区二区电影| 1024国产精品| 国产精品爽黄69| 免费国产一区二区| 亚洲永久视频| 亚洲国产精品第一区二区三区| 午夜精品视频| 国产精品免费在线| 久热国产精品| 亚洲欧美欧美一区二区三区| 亚洲第一页中文字幕| 午夜欧美电影在线观看| 亚洲日本中文字幕| 国内精品视频在线观看| 欧美日韩一区二区三区| 老司机一区二区三区| 亚洲免费网站| 91久久精品日日躁夜夜躁欧美| 久久成人精品无人区| 一区二区欧美在线| 亚洲国产女人aaa毛片在线| 国产精品一区二区黑丝| 欧美日韩在线免费观看| 欧美.www| 久热精品在线视频| 欧美中文字幕在线播放| 亚洲一区二区三区在线播放| 亚洲免费观看| 亚洲三级视频| 亚洲国产第一页| 欧美www在线| 久久综合久久综合久久| 久久aⅴ国产紧身牛仔裤| 一本大道久久a久久精二百| 亚洲高清av在线| 在线播放日韩| 在线观看欧美一区| 一区二区三区中文在线观看 | 在线观看国产成人av片| 韩国av一区二区| 国模套图日韩精品一区二区| 国产精品免费观看视频| 国产精品日韩专区| 国产精品视频男人的天堂| 国产精品免费在线| 国产欧美日韩精品专区| 国产日韩一区在线| 免费在线看成人av| 欧美福利专区| 欧美巨乳波霸| 国产精品扒开腿爽爽爽视频| 国产精品久久久久久久久久久久久| 欧美日韩在线三级| 国产精品羞羞答答xxdd| 国产欧美日本一区二区三区| 国产性猛交xxxx免费看久久| 国产午夜精品在线观看| 一区二区三区在线免费视频| 亚洲国产成人午夜在线一区 | 国产欧美精品一区二区色综合| 国产情人综合久久777777| 国产一区二区三区网站| 亚洲高清免费视频| 99国产一区| 欧美亚洲一区| 欧美不卡视频一区发布| 亚洲欧洲在线看| 亚洲欧美卡通另类91av| 久久久蜜桃精品| 欧美精品一区二区三区蜜臀| 国产精品九九久久久久久久| 韩国美女久久| 亚洲精选在线| 久久爱另类一区二区小说| 欧美freesex交免费视频| 亚洲六月丁香色婷婷综合久久| 亚洲视频日本| 美女国产精品| 国产精品久久国产愉拍 | 国产精品日韩欧美| 亚洲国产精品va在线观看黑人 | 国产视频一区在线观看一区免费| 伊人一区二区三区久久精品| 夜夜爽www精品| 久久久欧美精品sm网站| 亚洲美女中出| 久久久噜噜噜久久中文字幕色伊伊 | 美女性感视频久久久| 国产精品看片你懂得| 亚洲欧洲精品一区二区三区| 亚洲女性喷水在线观看一区| 欧美黑人在线播放| 亚洲欧美色一区| 欧美日韩国产小视频在线观看| 国内外成人免费激情在线视频| 在线视频日韩精品| 欧美成人免费在线| 香蕉视频成人在线观看| 欧美视频在线一区二区三区| 亚洲人成艺术| 美女主播一区| 久久精品女人的天堂av| 国产麻豆成人精品|