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

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>
            久久露脸国产精品| 亚洲电影免费观看高清完整版在线观看 | 久久亚洲综合色| 狠狠久久亚洲欧美| 亚洲福利在线看| 欧美日韩成人综合在线一区二区| 亚洲美女91| 欧美一级片一区| 亚洲精品免费在线观看| 亚洲国产成人91精品| 欧美日韩成人在线观看| 久久成人在线| 欧美片在线播放| 美国成人直播| 国产精品日韩欧美一区| 亚洲国产日韩综合一区| 国产日韩欧美二区| 亚洲欧美视频在线观看视频| 欧美国产日韩在线| 一区二区三区在线看| 99v久久综合狠狠综合久久| 国产一区91精品张津瑜| 中日韩在线视频| 亚洲一区二区在线视频| 欧美精品一区二区高清在线观看| 欧美91精品| 亚洲国产精品999| 欧美日韩精品综合| 亚洲女同精品视频| 欧美 日韩 国产在线| 9i看片成人免费高清| 国产精品一区在线观看你懂的| 亚洲网站视频| 久久男人av资源网站| 亚洲精品国产精品国自产在线 | 亚久久调教视频| 国产精品久久看| 欧美一区中文字幕| 亚洲精品国久久99热| 99视频精品免费观看| 欧美日韩大片| 亚洲一区图片| 亚洲第一区色| 久久精品2019中文字幕| 最近中文字幕mv在线一区二区三区四区| 欧美日韩专区在线| 欧美呦呦网站| 亚洲精品久久7777| 亚洲国产精品久久精品怡红院| 亚洲欧美国产精品va在线观看 | 午夜欧美大尺度福利影院在线看| 美日韩精品视频| 久久国产精品99国产精| 亚洲高清免费视频| 亚洲成色777777在线观看影院| 欧美午夜不卡在线观看免费 | 国产欧美一区二区精品性| 欧美黄色视屏| 蜜臀a∨国产成人精品| 亚洲综合色在线| 欧美在线黄色| 久久精品最新地址| 暖暖成人免费视频| 欧美区一区二区三区| 欧美激情一区二区三区不卡| 欧美一区二区三区免费观看| 久久精品夜色噜噜亚洲a∨| 亚洲主播在线播放| 乱中年女人伦av一区二区| 国产精品美女久久久久久久| 欧美日韩一区二区欧美激情 | 欧美大片在线观看一区二区| 午夜精品电影| 香蕉久久夜色精品国产| 久久综合亚洲社区| 亚洲国产毛片完整版| 亚洲美女av在线播放| 国产农村妇女毛片精品久久麻豆 | 老司机亚洲精品| 久久久久久午夜| 亚洲欧洲一区二区三区在线观看| 一区二区三区成人| 乱码第一页成人| 国产主播喷水一区二区| 亚洲精品乱码| 蜜臀99久久精品久久久久久软件| 9l国产精品久久久久麻豆| 久久美女性网| 国产欧美精品一区二区色综合| 亚洲第一黄网| 欧美69wwwcom| 久久久久国内| 国产亚洲精品久久久久久| 99在线热播精品免费| 久久精品91| 亚洲永久免费精品| 欧美寡妇偷汉性猛交| 亚洲电影在线免费观看| 欧美成人亚洲成人| 午夜视频在线观看一区| 国产一级一区二区| 久久蜜桃资源一区二区老牛| 午夜精品久久久久久久男人的天堂| 国产精品一区二区a| 亚洲欧美日韩一区二区在线| 99视频热这里只有精品免费| 国产精品一区2区| 久久免费黄色| 麻豆国产精品777777在线| 韩国av一区| 亚洲精选在线| 狠狠狠色丁香婷婷综合激情| 亚洲人成在线观看| 一区二区三区无毛| 亚洲黄色av一区| 含羞草久久爱69一区| 亚洲一区欧美二区| 一区二区三区高清在线| 久久亚洲精品一区二区| 欧美在线视频a| 欧美日韩国产色综合一二三四| 国产欧美一区二区三区在线看蜜臀| 欧美三级电影大全| 免费成人高清视频| 狠狠色丁香婷婷综合| 亚洲精品乱码久久久久久久久 | 欧美母乳在线| 亚洲美女中出| 欧美一区二区视频在线| 欧美午夜电影在线| 99国产精品| 亚洲欧美在线aaa| 国产精品美女久久久| 亚洲一区二区三区免费视频| 夜夜夜久久久| 欧美性大战久久久久久久蜜臀| 麻豆av一区二区三区| 国产一区欧美日韩| 欧美一区二区成人6969| 欧美专区在线观看一区| 欧美日韩高清在线| 一区二区欧美在线| 久久精品导航| 亚洲国产经典视频| 欧美韩日精品| 久久国产直播| 一区二区三区成人| 亚洲主播在线播放| 国产亚洲欧美日韩精品| 欧美激情一区二区三区在线视频| 一本色道久久精品| 免费不卡在线观看| 亚洲欧美资源在线| 精品不卡视频| 国产日韩欧美一区| 欧美国产视频在线观看| 亚洲美女黄色| 久久九九99视频| 亚洲精品免费一二三区| 国产精品毛片大码女人| 久久精品国产久精国产思思| 另类天堂av| 久久成年人视频| 中国女人久久久| 亚洲精品国产精品乱码不99按摩| 国产精品一页| 国产精品国产馆在线真实露脸| 久久久蜜桃一区二区人| 欧美专区在线观看一区| 久久av最新网址| 久久亚洲捆绑美女| 免费成人毛片| 欧美日本高清视频| 国产欧美在线观看| 在线观看视频一区二区欧美日韩| 在线电影一区| 午夜久久福利| 亚洲国产精品ⅴa在线观看| 亚洲精选视频在线| 亚洲欧美日韩一区在线观看| 欧美成人午夜激情| 狂野欧美激情性xxxx| 久久久综合香蕉尹人综合网| 午夜精品福利一区二区三区av| 亚洲一区精彩视频| 欧美中文字幕第一页| 欧美一区二区三区的| 久久久水蜜桃av免费网站| 久久一日本道色综合久久| 欧美电影在线| 中文一区二区在线观看| 欧美在线视频不卡| 欧美福利影院| 国产欧美一区二区精品忘忧草 | 亚洲影院免费| 久久九九电影| 夜夜嗨av一区二区三区免费区 | 在线欧美影院| 亚洲视频精选| 免费成人性网站|