1 #include <cstdio> 2 #include <algorithm> 3 4 #define rep(i, l, r) for(int i=l; i<=r; i++) 5 6 using namespace std; 7 8 inline int read() 9 { 10 int x=0; bool f=0; char ch=getchar(); 11 while (ch<'0' || '9'<ch) f|=ch=='-', ch=getchar(); 12 while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar(); 13 return f?-x:x; 14 } 15 16 #define maxn 21 17 #define eps 1e-8 18 19 int n, m, op, tot, q[maxn], idx[maxn], idy[maxn]; double a[maxn][maxn], A[maxn]; 20 21 inline void Pivot(int x, int y) 22 { 23 swap(idy[x],idx[y]); 24 double tmp=a[x][y]; a[x][y]=1/a[x][y]; 25 rep(i, 0, n) if (y!=i) a[x][i]/=tmp; 26 tot=0; rep(i, 0, n) if (i!=y && (a[x][i]>eps || a[x][i]<-eps)) q[++tot]=i; 27 rep(i, 0, m) 28 { 29 if ((x==i) || (a[i][y]<eps && a[i][y]>-eps)) continue; 30 rep(j, 1, tot) a[i][q[j]]-=a[x][q[j]]*a[i][y]; 31 a[i][y]=-a[i][y]/tmp; 32 } 33 } 34 35 int main() 36 { 37 n=read(), m=read(), op=read(); 38 rep(i, 1, n) a[0][i]=read(); 39 rep(i, 1, m) 40 { 41 rep(j, 1, n) a[i][j]=read(); 42 a[i][0]=read(); 43 } 44 45 rep(i, 1, n) idx[i]=i; 46 rep(i, 1, m) idy[i]=i+n; 47 while (true) 48 { 49 int x=0, y=0; 50 rep(i, 1, m) if (a[i][0]<-eps && ((!x)||(rand()&1))) x=i; if (!x) break; 51 rep(i, 1, n) if (a[x][i]<-eps && ((!y)||(rand()&1))) y=i; if (!y) return puts("Infeasible"),0; 52 Pivot(x,y); 53 } 54 55 while (true) 56 { 57 int x=0, y=0; double mn=1e15; 58 rep(i, 1, n) if (a[0][i]>eps) {y=i; break;} if (!y) break; 59 rep(i, 1, m) if (a[i][y]>eps && a[i][0]/a[i][y]<mn) mn=a[i][0]/a[i][y], x=i; if (!x) return puts("Unbounded"),0; 60 Pivot(x,y); 61 } 62 63 printf("%.8lf ", -a[0][0]); if (!op) return 0; 64 rep(i, 1, m) if (idy[i]<=n) A[idy[i]]=a[i][0]; 65 rep(i, 1, n) printf("%.8lf%c", A[i], i==n?' ':' '); 66 67 return 0; 68 }