内部存款和储蓄器限制,赶紧去探访=v=710官方网站

光阴限制:一千0ms

hihoCoder #1195 : 高斯消元·一,

时刻范围:一千0ms 单点时间限制:一千ms 内部存款和储蓄器限制:256MB

岁月范围:一千0ms单点时间限制:一千ms内存限制:256MB

单点时间限制:壹仟ms

描述

小Ho:喂不得了啊,那边便利店的薯片半价了!

小Hi:啥?!

小Ho:那边的便利店在减价巨惠啊。

小Hi:走走走,赶紧去探视=v=

于是乎小Hi和小Ho来到了便利店。

老总为了巨惠,推出了组合包的款型,将分化数量的各个货品打包成二个组合,顾客能够选取组合张开购买。比如2袋薯片,1听可乐的重组只要5元,而1袋薯片,2听可乐的三结合只要4元。

通过打听老董,小Hi和小Ho知道:一共有N种不相同的商品和M种区别的货物组合;每三个组成的标价相当于组合内商品贩卖价格之和,四个结缘内一样件货品不会超过10件。

小Hi:那样算下来的话,一听可乐即是1元,而一包薯片是2元。小Ho,倘让你知道全数的咬合情形,你能分别算出每一件商品单独的价格么?

小Ho:当然能够了,那样的小标题怎么能难到本人吗?

升迁:高斯消元

描述

小Ho:喂不得了啊,那边便利店的薯片半价了!

小Hi:啥?!

小Ho:这边的便利店在巨惠打折啊。

小Hi:走走走,赶紧去探访=v=

于是乎小Hi和小Ho来到了便利店。

业主为了降价,推出了组合包的款型,将分歧数额的每一样商品打包成多少个结合,顾客可以选取组合打开垦购。比方2袋薯片,1听可乐的构成只要5元,而1袋薯片,2听可乐的组成只要4元。

经过询问老总,小Hi和小Ho知道:一共有N种差异的物品和M种不一样的货物组合;每三个构成的价位相当于组合内商品贩卖价格之和,多个组成内一律件货色不会当先10件。

小Hi:那样算下来的话,一听可乐正是1元,而一包薯片是2元。小Ho,假如您了然全部的结合境况,你能分别算出每一件商品单独的价格么?

小Ho:当然能够了,那样的小标题怎么能难到自个儿呢?

晋升:高斯消元

内部存款和储蓄器限制:256MB

输入

第1行:2个正整数,N,M。表示商品的数目N,组合的数量M。1≤N≤500, N≤M≤2*N

第2..M+1行:N+1个非负整数,第i+1行第j列表示在第i个结合中,商品j的数据a[i][j]。第i+1行第N+1个数表示该组合的售卖价格c[i]。0≤a[i][j]≤10,
0≤c[i]≤10^9

输入

第1行:2个正整数,N,M。表示商品的多寡N,组合的数量M。1≤N≤500, N≤M≤2*N

第2..M+1行:N+1个非负整数,第i+1行第j列表示在第i个组成人中学,商品j的数额a[i][j]。第i+1行第N+1个数表示该结合的贩卖价格c[i]。0≤a[i][j]≤10,
0≤c[i]≤10^9

描述

小Ho:喂不得了啊,那边便利店的薯片半价了!

小Hi:啥?!

小Ho:那边的便利店在巨惠减价啊。

小Hi:走走走,赶紧去探视=v=

于是乎小Hi和小Ho来到了便利店。

CEO娘为了打折,推出了组合包的款式,将区别数额的每一类商品打包成四个结合,顾客能够采纳组合张开选购。比方2袋薯片,1听可乐的组成只要5元,而1袋薯片,2听可乐的结缘只要4元。

通过打听老董,小Hi和小Ho知道:一共有N种不一致的商品和M种不一致的物品组合;每三个构成的价位也就是组合内商品售卖价格之和,三个结缘内同样件货品不会超过10件。

小Hi:那样算下来的话,一听可乐便是1元,而一包薯片是2元。小Ho,若是你掌握全部的组合情形,你能分别算出每一件商品单独的价格么?

小Ho:当然可以了,那样的小标题怎么能难到本身吗?

   

晋升:高斯消元

 

输出

若未有办法总括出各类商品单独的价钱,输出”No solutions”

若大概存在七个例外的结果,输出”Many solutions”

若存在唯一恐怕的结果,输出N行,每行八个非负整数,第i行代表第i个商品单独的贩卖价格。数据保险借使存在唯一解,那么解一定恰好是非负整数解。

样例输入

2 2
2 1 5
1 2 4

样例输出

2

1

这坑爹oj没多少,害的自己拍了以中午,

题比较简单,高斯消元的模版题,

注意eps要开double类型的

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1001;
 7 const double eps =1e-7;
 8 typedef double Matrix[MAXN][MAXN] ;
 9 inline void read(int &n)
10 {
11     char c=getchar();bool flag=0;n=0;
12     while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();
14 }
15 int n,m;
16 Matrix a;
17 double t[MAXN];
18 void Gauss()
19 {
20     int r;
21     for(int i=1;i<=n;i++)// 枚举每一行 
22     {
23         r=i;
24         for(int j=m;j>=i+1;j--)// 枚举后面的行 
25             fabs(a[j][i])>fabs(a[r][i])?r=j:r=r;
26         if(r!=i)    swap(a[r],a[i]); 
27         if(r==i&&fabs(a[i][i])<eps)        printf("Many solutions"),exit(0);
28             
29         for(int j=i+1;j<=m;j++)// 行 
30         {
31             for(int k=n+1;k>i;k--)// 列 
32                 a[j][k]-=(a[j][i]/a[i][i])*a[i][k];
33             a[j][i]=0;
34         }
35     }
36     
37     for(int i=n,j;i<=m;i++)
38     {
39         for(j=1;j<=n;j++)        if(fabs(a[i][j])>eps)        break;
40         if(j==n+1&&fabs(a[i][n+1])>eps)        
41             printf("No solutions\n"),exit(0);
42     }// 是否有解 
43     
44     for(int i=n;i>=1;i--)// 枚举行 
45     {
46         for(int j=i+1;j<=n;j++)// 枚举列 
47             a[i][n+1]-=a[i][j]*a[j][n+1];
48         a[i][n+1]/=a[i][i];
49     }
50     for(int i=1;i<=n;i++)
51         printf("%d\n",(int)(a[i][n+1]+0.5));
52 }
53 int main()
54 {
55     freopen("a.in","r",stdin);
56     freopen("c.out","w",stdout);
57     read(n);read(m);
58     for(int i=1;i<=m;i++)
59         for(int j=1;j<=n+1;j++)
60             scanf("%lf",&a[i][j]);
61     Gauss();
62     
63     return 0;
64 }

 

    

http://www.bkjia.com/cjjc/1222801.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1222801.htmlTechArticlehihoCoder #1195 : 高斯消元一,
时限:一千0ms单点时间限制:一千ms内部存款和储蓄器限制:256MB 描述
小Ho:喂不得了啊,那边便利店的薯片半价了! 小Hi:啥?! 小…

输出

若未有办法总计出各样商品单独的价格,输出”No solutions”

若恐怕存在多少个例外的结果,输出”Many solutions”

若存在唯一大概的结果,输出N行,每行八个非负整数,第i行表示第i个商品单独的出售价格。数据保障假若存在唯一解,那么解一定恰好是非负整数解。

样例输入

2 22 1 51 2 4

样例输出

2

1

那坑爹oj十分的少,害的自家拍了以中午,

题相比较轻松,高斯消元的模版题,

注意eps要开double类型的

 1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=1001; 7 const double eps =1e-7; 8 typedef double Matrix[MAXN][MAXN] ; 9 inline void read(int &n)10 {11     char c=getchar();bool flag=0;n=0;12     while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar();13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();14 }15 int n,m;16 Matrix a;17 double t[MAXN];18 void Gauss()19 {20     int r;21     for(int i=1;i<=n;i++)// 枚举每一行 22     {23         r=i;24         for(int j=m;j>=i+1;j--)// 枚举后面的行 25             fabs>fabs?r=j:r=r;26         if(r!=i)    swap(a[r],a[i]); 27         if(r==i&&fabs<eps)        printf("Many solutions"),exit(0);28             29         for(int j=i+1;j<=m;j++)// 行 30         {31             for(int k=n+1;k>i;k--)// 列 32                 a[j][k]-=(a[j][i]/a[i][i])*a[i][k];33             a[j][i]=0;34         }35     }36     37     for(int i=n,j;i<=m;i++)38     {39         for(j=1;j<=n;j++)        if(fabs>eps)        break;40         if(j==n+1&&fabs(a[i][n+1])>eps)        41             printf("No solutions\n"),exit(0);42     }// 是否有解 43     44     for(int i=n;i>=1;i--)// 枚举行 45     {46         for(int j=i+1;j<=n;j++)// 枚举列 47             a[i][n+1]-=a[i][j]*a[j][n+1];48         a[i][n+1]/=a[i][i];49     }50     for(int i=1;i<=n;i++)51         printf("%d\n",(int)(a[i][n+1]+0.5));52 }53 int main()54 {55     freopen("a.in","r",stdin);56     freopen("c.out","w",stdout);57     read;read;58     for(int i=1;i<=m;i++)59         for(int j=1;j<=n+1;j++)60             scanf("%lf",&a[i][j]);61     Gauss();62     63     return 0;64 }




    

输入

第1行:2个正整数,N,M。表示商品的数量N,组合的数量M。1≤N≤500, N≤M≤2*N

第2..M+1行:N+1个非负整数,第i+1行第j列表示在第i个结合中,商品j的多寡a[i][j]。第i+1行第N+1个数表示该组合的出售价格c[i]。0≤a[i][j]≤10,
0≤c[i]≤10^9

输出

若没有办法总结出各种商品单独的价钱,输出”No solutions”

若恐怕存在四个不等的结果,输出”Many solutions”

若存在唯一或许的结果,输出N行,每行三个非负整数,第i行代表第i个商品单独的售卖价格。数据保险假设存在唯一解,那么解一定恰好是非负整数解。

样例输入

2 2
2 1 5
1 2 4

样例输出

2

1

那坑爹oj不多,害的本人拍了以中午,

题比较轻松,高斯消元的模版题,

注意eps要开double类型的

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1001;
 7 const double eps =1e-7;
 8 typedef double Matrix[MAXN][MAXN] ;
 9 inline void read(int &n)
10 {
11     char c=getchar();bool flag=0;n=0;
12     while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();
14 }
15 int n,m;
16 Matrix a;
17 double t[MAXN];
18 void Gauss()
19 {
20     int r;
21     for(int i=1;i<=n;i++)// 枚举每一行 
22     {
23         r=i;
24         for(int j=m;j>=i+1;j--)// 枚举后面的行 
25             fabs(a[j][i])>fabs(a[r][i])?r=j:r=r;
26         if(r!=i)    swap(a[r],a[i]); 
27         if(r==i&&fabs(a[i][i])<eps)        printf("Many solutions"),exit(0);
28             
29         for(int j=i+1;j<=m;j++)// 行 
30         {
31             for(int k=n+1;k>i;k--)// 列 
32                 a[j][k]-=(a[j][i]/a[i][i])*a[i][k];
33             a[j][i]=0;
34         }
35     }
36     
37     for(int i=n,j;i<=m;i++)
38     {
39         for(j=1;j<=n;j++)        if(fabs(a[i][j])>eps)        break;
40         if(j==n+1&&fabs(a[i][n+1])>eps)        
41             printf("No solutions\n"),exit(0);
42     }// 是否有解 
43     
44     for(int i=n;i>=1;i--)// 枚举行 
45     {
46         for(int j=i+1;j<=n;j++)// 枚举列 
47             a[i][n+1]-=a[i][j]*a[j][n+1];
48         a[i][n+1]/=a[i][i];
49     }
50     for(int i=1;i<=n;i++)
51         printf("%d\n",(int)(a[i][n+1]+0.5));
52 }
53 int main()
54 {
55     freopen("a.in","r",stdin);
56     freopen("c.out","w",stdout);
57     read(n);read(m);
58     for(int i=1;i<=m;i++)
59         for(int j=1;j<=n+1;j++)
60             scanf("%lf",&a[i][j]);
61     Gauss();
62     
63     return 0;
64 }

 

    

相关文章