• <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>

            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 幻浪天空領主 閱讀(387) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            武侠古典久久婷婷狼人伊人| 色88久久久久高潮综合影院 | 国产精品久久婷婷六月丁香| 国产69精品久久久久APP下载| 亚洲精品国产字幕久久不卡| 99久久99这里只有免费的精品| 精品国产青草久久久久福利 | 久久亚洲精品中文字幕| 欧美激情精品久久久久| 久久综合亚洲色一区二区三区| 久久国产精品无码一区二区三区| 99久久精品免费看国产免费| 久久久久久久久久久| 国产精品久久久99| 久久精品亚洲一区二区三区浴池| 欧美精品丝袜久久久中文字幕 | 亚洲色欲久久久久综合网| 久久精品国产亚洲AV嫖农村妇女| 天堂无码久久综合东京热| 94久久国产乱子伦精品免费 | 狠狠色丁香久久婷婷综合_中| 66精品综合久久久久久久| 久久久久久亚洲AV无码专区 | 色偷偷888欧美精品久久久| 超级97碰碰碰碰久久久久最新 | 91精品国产综合久久久久久| 久久经典免费视频| 无码任你躁久久久久久| 久久久无码精品亚洲日韩软件| www.久久精品| 日本福利片国产午夜久久| 国产成人精品白浆久久69| 丰满少妇高潮惨叫久久久| 老色鬼久久亚洲AV综合| 无码国产69精品久久久久网站| 久久亚洲AV无码精品色午夜麻豆| 久久久久久国产精品免费免费 | 久久亚洲精精品中文字幕| 亚洲精品乱码久久久久久久久久久久 | 日本精品久久久久中文字幕| 久久久国产精品网站|