随笔-141  评论-9  文章-3  trackbacks-0

其实就是解线性方程.

用克莱姆法则求解, 求解过程要判断是否是分数解或者负解。

Ax = k*B   枚举B, 从1到100.

/*
ID: lorelei3
TASK: ratios
LANG: C++
*/


#include 
<fstream>

using namespace std;

int A[4][4];
int B[4], b[4];
int x[4];
int D;

int det(){
    
return    A[1][1]*(A[2][2]*A[3][3]-A[3][2]*A[2][3])-
            A[
1][2]*(A[2][1]*A[3][3]-A[3][1]*A[2][3])+
            A[
1][3]*(A[2][1]*A[3][2]-A[3][1]*A[2][2]);
}



int Cramer(){
    
int i,j;
    
int tmp[4];
    
for(i=1; i<=3++i){

        
for(j=1; j<=3++j){
            tmp[j] 
= A[j][i];
            A[j][i] 
= B[j];
        }


        
int Di = det();

        
for(j=1; j<=3++j)
            A[j][i] 
= tmp[j];

        
if(Di%!= 0)
            
return -1;

        x[i] 
= Di/D;

        
if(x[i]<0)
            
return -1;        
    }

    
return 1;
}


int main(){
    
int i,j,k;

    ifstream fin(
"ratios.in");
    ofstream fout(
"ratios.out");

    
for(i=1; i<=3++i)
        fin
>>b[i];

    
for(i=1; i<=3++i)
        
for(j=1; j<=3++j)
            fin
>>A[j][i];

    D
=det();
    
    
for(k=1; k<=100++k){
        
for(i=1; i<=3++i)
            B[i] 
= k*b[i];

        
if(Cramer()==1){
            
for(i=1; i<=3++i)
                fout
<<x[i]<<" ";
            fout
<<k<<endl;
            
return 0;
        }

    }

    
    fout
<<"NONE"<<endl;
    
return 0;
}
posted on 2010-12-23 16:46 小阮 阅读(206) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理