时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Ho：喂不得了啦，那边便利店的薯片半价了!

小Hi：啥?!

小Ho：那边的便利店在打折促销啊。

小Hi：走走走，赶紧去看看=v=

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

老板为了促销，推出了组合包的形式，将不同数量的各类商品打包成一个组合，顾客可以选择组合进行购买。比如2袋薯片，1听可乐的组合只要5元，而1袋薯片，2听可乐的组合只要4元。

通过询问老板，小Hi和小Ho知道：一共有N种不同的商品和M种不同的商品组合；每一个组合的价格等于组合内商品售价之和，一个组合内同一件商品不会超过10件。

小Hi：这样算下来的话，一听可乐就是1元，而一包薯片是2元。小Ho，如果你知道所有的组合情况，你能分别算出每一件商品单独的价格么？

小Ho：当然可以了，这样的小问题怎么能难到我呢？

   

 

输入

第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 22 1 51 2 4

样例输出

21

---

先贴代码

#include 
     
      using namespace std;const int N(505), M(1005);const double EPS=1e-6;typedef double mat[M][N];typedef double vec[N];void swap(mat a, int i, int j){    vec tmp;    memcpy(tmp, a[i], sizeof(tmp));    memcpy(a[i], a[j], sizeof(tmp));    memcpy(a[j], tmp, sizeof(tmp));    }//m>=nint gauss(mat a, int n, int m){    int res=1;    for(int i=0; i
      
       abs(a[pivot][i]))                pivot=j;        swap(a, i, pivot);       // cout<
       
        <
        
         EPS){            res=0;            break;        }    }    for(int i=n; i
         
          EPS){            res=0;            break;        }    return res;}int main(){    int n, m;    cin>>n>>m;    mat a;    for(int i=0; i
          
           >a[i][j]; int res=gauss(a, n, m); if(!res) puts("No solutions"); else if(!~res) puts("Many solutions"); else for(int i=0; i
          
         
        
       
      
     

 

这题有一个小坑：若结果中的某一项为0，由于增广矩阵为double类型，该项在实际结果中可能是一个绝对值很小的负数（比如-0.0001），此时如果用

printf("%.0f")，将输出

"-0"。由于这题输出为整数，就不会有对精度的特判，如此输出必然返

WA。 办法是

将结果加0.5再强制转换成int输出。

---

这里强调一下printf("%.0f")和printf("%d",(int)())的区别 前者是按 “（ 符号不变，绝对值 ）四舍五入”（ “四舍五入”确切地说是“小数部分>0.5则入，否则舍” ）输出，后者是将浮点数往（数轴上）零的方向截断后输出。

---

比如

double res=0.5;printf("%d %.0f\n", (int)res, res);

输出 0 0

double res=0.51;printf("%d %.0f\n", (int)res, res);

输出 0 1

double res=-0.5;printf("%d %.0f\n", (int)res, res);

输出 0 -0

double res=-0.51;printf("%d %.0f\n", (int)res, res);

输出 0 -1