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

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

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

導航

統計

常用鏈接

留言簿(1)

隨筆檔案(2)

文章分類(23)

文章檔案(22)

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美专区福利在线| 亚洲视频免费在线观看| 一区二区三区国产精华| 欧美精品v日韩精品v国产精品| 亚洲国产成人在线视频| 欧美大胆人体视频| 另类激情亚洲| 99热这里只有精品8| 日韩网站在线观看| 国产精品久久一区二区三区| 欧美一区二区日韩| 欧美一级欧美一级在线播放| 韩日精品中文字幕| 亚洲精品国久久99热| 欧美日韩国产成人| 欧美一级黄色网| 久久久99国产精品免费| 亚洲国产精品久久久久秋霞影院| 亚洲国产91| 国产精品大片免费观看| 午夜亚洲福利| 美女在线一区二区| 亚洲国产精品黑人久久久| 日韩一二在线观看| 国产亚洲综合在线| 亚洲精品看片| 国产日韩欧美亚洲一区| 欧美激情一区二区| 国产精品久久久久国产精品日日| 母乳一区在线观看| 国产精品福利在线观看| 欧美激情亚洲综合一区| 国产精品久久久久免费a∨| 久久riav二区三区| 欧美精品一区在线播放| 久久综合网色—综合色88| 欧美日韩日本国产亚洲在线| 美女主播精品视频一二三四| 国产精品一区免费观看| 久久久久久黄| 亚洲欧美中文日韩v在线观看| 亚洲免费视频网站| 免费亚洲电影在线| 亚洲大胆女人| 激情久久久久久久久久久久久久久久| 亚洲一区二区三区精品在线| 99国产精品久久| 欧美激情亚洲综合一区| 亚洲精品麻豆| 一区二区三区黄色| 欧美日韩精品一本二本三本| 亚洲一区二区精品在线观看| 一区二区高清| 国产毛片久久| 久久免费偷拍视频| 免费看亚洲片| 久久一综合视频| 欧美亚洲视频一区二区| 亚洲电影在线| 农夫在线精品视频免费观看| 欧美亚洲视频| 国产私拍一区| 一本久道久久综合婷婷鲸鱼| 影音先锋欧美精品| 午夜精品久久| 亚洲素人在线| 国产精品美女午夜av| 999在线观看精品免费不卡网站| 亚洲国产日韩精品| 麻豆成人在线播放| 欧美韩日高清| 99re66热这里只有精品3直播 | 国产精品网曝门| 亚洲图片在线观看| 亚洲欧美精品| 国产欧美在线观看一区| 欧美一区二区在线播放| 久久久久成人网| 在线观看视频欧美| 久久午夜影视| 91久久久久久久久久久久久| 夜夜嗨av一区二区三区免费区| 欧美日韩国产综合一区二区| 亚洲一区二区精品在线| 欧美在线亚洲综合一区| 伊人成年综合电影网| 欧美高清影院| 亚洲影院在线| 榴莲视频成人在线观看| 亚洲片在线资源| 国产精品久久9| 欧美一级淫片aaaaaaa视频| 蜜臀av在线播放一区二区三区| 亚洲精品国偷自产在线99热| 欧美性jizz18性欧美| 久久国产精品久久久久久电车| 亚洲电影天堂av| 午夜久久资源| 亚洲丁香婷深爱综合| 欧美午夜宅男影院| 久久久久久久国产| 一区二区不卡在线视频 午夜欧美不卡在 | 99国产精品久久久久久久久久 | 欧美一区二区三区在线看 | 欧美日韩精品国产| 午夜精品视频一区| 亚洲黄色在线| 久久九九热re6这里有精品| 亚洲精品久久视频| 国产伦精品一区二区三区四区免费| 久久午夜av| 亚洲永久免费视频| 亚洲精品国产精品国自产观看浪潮| 久久爱www久久做| 亚洲最新视频在线播放| 国产一区二区毛片| 欧美三日本三级少妇三2023| 久久尤物视频| 欧美影视一区| 亚洲天堂av图片| 亚洲激情校园春色| 美国成人直播| 亚洲字幕一区二区| 一本久道久久久| 亚洲电影免费观看高清完整版在线| 国产精品网站在线| 国产精品v欧美精品v日韩 | 亚洲视频自拍偷拍| 亚洲日本成人女熟在线观看| 蘑菇福利视频一区播放| 久久久久国内| 久久大逼视频| 午夜精品在线观看| 亚洲欧美国产毛片在线| 99国产精品国产精品毛片| 亚洲激情欧美激情| 在线观看中文字幕不卡| 国内精品嫩模av私拍在线观看| 国产毛片精品视频| 国产精品入口尤物| 国产精品日韩电影| 国产精品亚洲精品| 国产日韩欧美a| 国产午夜精品久久久久久免费视| 欧美亚州一区二区三区| 国产精品hd| 欧美午夜精品电影| 国产精品久久久久影院亚瑟| 国产精品va在线播放我和闺蜜| 欧美午夜激情视频| 国产日韩精品一区二区三区在线| 国产精品尤物| 国产在线观看一区| 狠狠做深爱婷婷久久综合一区 | 免费在线亚洲欧美| 欧美华人在线视频| 欧美午夜片欧美片在线观看| 国产精品久久久久久久久久直播 | 亚洲一区二区在线免费观看| 亚洲一区二区免费视频| 亚洲欧美在线一区二区| 欧美中文字幕视频| 麻豆久久婷婷| 亚洲日韩视频| 午夜精品在线观看| 久久精品国产亚洲精品| 久久天堂成人| 欧美日韩一区二区三区在线观看免| 欧美视频一区在线观看| 国产日韩欧美在线| 91久久精品国产91久久性色| 一本久道综合久久精品| 久久精品盗摄| 最新国产精品拍自在线播放| 亚洲视频精选在线| 久久精品成人一区二区三区蜜臀| 免费成人黄色片| 国产精品国产精品| 伊人久久婷婷色综合98网| 一区二区三区视频免费在线观看| 欧美一区二区三区在| 亚洲国产电影| 亚洲欧美美女| 欧美高清在线精品一区| 国产精品日韩在线观看| 亚洲激情网站| 午夜精品久久久久久久白皮肤 | 亚洲最快最全在线视频| 久久精品国产精品亚洲精品| 亚洲黄色免费网站| 欧美在线日韩在线| 欧美视频精品在线| 亚洲人成欧美中文字幕| 久久精品夜色噜噜亚洲a∨| 亚洲精选成人| 另类尿喷潮videofree| 国产精品永久免费| 亚洲图片欧洲图片日韩av| 欧美高清在线一区二区| 香蕉成人久久|