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

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>
            欧美日韩久久精品| 久久这里只精品最新地址| 欧美黑人国产人伦爽爽爽| 久久久久久久久岛国免费| 激情亚洲成人| 欧美成人午夜激情在线| 欧美电影资源| 亚洲在线中文字幕| 亚洲午夜久久久久久久久电影院| 国产精品www| 欧美一区二区三区免费视| 欧美在线视频在线播放完整版免费观看| 国产色视频一区| 欧美国产1区2区| 欧美三级乱码| 毛片一区二区| 欧美日韩1区| 久久手机精品视频| 欧美午夜电影网| 久久免费一区| 欧美日韩国产综合视频在线观看中文 | 亚洲高清免费| 日韩视频久久| 伊人成年综合电影网| 亚洲精品欧美专区| 国产亚洲精品高潮| 亚洲国产一区二区三区高清 | 亚洲一区精彩视频| 亚洲国产婷婷综合在线精品 | 欧美jizzhd精品欧美喷水| 欧美日韩综合在线免费观看| 麻豆精品精品国产自在97香蕉| 欧美日韩一区二| 免费在线看成人av| 国产精品久久激情| 亚洲精品综合久久中文字幕| 国语对白精品一区二区| 夜夜嗨av一区二区三区网站四季av| 国内精品久久久久影院色 | 欧美mv日韩mv亚洲| 国产日韩亚洲欧美综合| 一区二区三区精品视频在线观看| 亚洲丁香婷深爱综合| 午夜欧美精品久久久久久久| 99re6热只有精品免费观看| 久久久97精品| 欧美一区亚洲| 国产精品福利影院| 日韩视频中午一区| 亚洲人午夜精品| 久久久久国产精品www | 日韩视频在线播放| 免费成人黄色| 欧美xx视频| 精品999网站| 久久精品欧美日韩| 欧美中文字幕精品| 国产欧美日韩免费| 亚洲欧美日韩在线不卡| 午夜精品福利一区二区三区av| 欧美日本三区| 99re热这里只有精品免费视频| 亚洲精品小视频在线观看| 毛片av中文字幕一区二区| 狂野欧美激情性xxxx| 激情欧美一区二区三区在线观看 | 亚洲精品乱码| 一区二区三区av| 欧美日韩视频专区在线播放 | 在线一区二区三区四区五区| 亚洲一区黄色| 国产精品视频久久久| 亚洲在线视频一区| 久久免费高清| 亚洲第一伊人| 欧美剧在线免费观看网站| 亚洲美女视频| 久久爱www| 在线成人黄色| 欧美精品手机在线| 亚洲深夜福利在线| 久久久精品免费视频| 亚洲激情欧美激情| 欧美日韩一区二区欧美激情| 亚洲午夜伦理| 男女激情久久| 亚洲视频在线一区| 国产日韩欧美一区二区| 久久夜色精品国产亚洲aⅴ| 亚洲国产视频一区| 亚洲欧美制服中文字幕| 国产在线观看一区| 欧美电影资源| 欧美在线一二三区| 亚洲精品久久在线| 久久久久久精| av成人免费在线观看| 国产目拍亚洲精品99久久精品 | 欧美亚洲在线视频| 亚洲国产精品一区二区第四页av| 亚洲一品av免费观看| 极品日韩av| 国产精品美女久久| 米奇777超碰欧美日韩亚洲| 一区二区冒白浆视频| 久久综合精品国产一区二区三区| 亚洲高清在线视频| 亚洲女人天堂av| 亚洲黄色免费网站| 国产日产精品一区二区三区四区的观看方式 | 99pao成人国产永久免费视频| 国产精品入口夜色视频大尺度 | 亚洲一二三区在线| 亚洲电影免费在线观看| 久久精品人人| 午夜精品久久久久久久| 亚洲精品国久久99热| 国产亚洲精品bt天堂精选| 欧美日韩国产一区| 欧美成人午夜激情视频| 欧美在线观看视频在线 | 你懂的国产精品| 亚洲欧美一区二区三区久久| 亚洲人午夜精品| 浪潮色综合久久天堂| 久久成人18免费观看| 亚洲午夜精品在线| 99精品免费视频| 亚洲国产精品一区二区久| 国产又爽又黄的激情精品视频| 国产精品www994| 欧美日韩在线播| 欧美日韩成人在线视频| 欧美电影在线观看| 欧美高清在线视频| 免费在线成人| 美腿丝袜亚洲色图| 免费亚洲一区二区| 另类av一区二区| 另类亚洲自拍| 免费人成网站在线观看欧美高清| 久久久久五月天| 久久久夜色精品亚洲| 久久久青草婷婷精品综合日韩 | 亚洲国产精品va| 欧美高清不卡| 亚洲国产精品久久91精品| 欧美激情精品| 亚洲国产日韩欧美在线动漫| 免费视频亚洲| 亚洲国产高清在线观看视频| 亚洲第一黄色| 亚洲精品日产精品乱码不卡| 亚洲精品免费一二三区| 99国产一区二区三精品乱码| 一本大道久久a久久综合婷婷 | 久久成人av少妇免费| 久久伊人精品天天| 亚洲电影免费在线观看| 日韩视频中文| 欧美在线日韩在线| 欧美 日韩 国产 一区| 欧美精品一区二区三| 欧美婷婷在线| 国产亚洲欧美色| 亚洲精品中文字| 亚洲女性裸体视频| 久久婷婷国产综合国色天香| 欧美大片一区二区| 一本久久青青| 久久精品人人做人人爽电影蜜月| 女生裸体视频一区二区三区| 国产精品极品美女粉嫩高清在线 | 国产精品普通话对白| 伊人成年综合电影网| 中文国产亚洲喷潮| 久久精品视频va| 亚洲国产精品久久| 欧美在线免费看| 欧美手机在线| 亚洲国产成人精品久久久国产成人一区 | 国产亚洲福利| 亚洲精品麻豆| 久久国产精品亚洲va麻豆| 亚洲国产成人porn| 久久er99精品| 国产精品wwwwww| 亚洲日本中文字幕免费在线不卡| 西西裸体人体做爰大胆久久久 | 一区二区三区久久| 免费不卡亚洲欧美| 亚洲免费视频网站| 欧美日韩高清一区| 在线观看视频一区二区| 午夜精品久久久久久久久久久久久 | 一区二区三区不卡视频在线观看| 久久久久久电影| 亚洲欧美国产精品va在线观看| 欧美国产精品va在线观看| 亚洲高清久久网|