// Problem : Inflation (NAIPC 2019) // Author : Darcy Best // Expected Result : WA // Complexity : O( (y*c)^3 ) // Because input data is not exact, this solution thinks that the system of equations is inconsistent. // Take log of all variables // Use Guassian Elimination to determine everything. #include #include #include #include #include using namespace std; const double EPS = 1e-10; vector solve(vector >& M){ int rows = M.size(), cols = M[0].size(); int rank = 0; for(int piv=0;piv= EPS){ M[rank].swap(M[i]); break; } if(abs(M[rank][piv]) < EPS) continue; double divide_me = M[rank][piv]; for(int j=rank;j ans(cols-1,-1); for(int i=0;i= EPS) break; for(;last>=0;last--) if(abs(M[i][last ]) >= EPS) break; if(first != last) continue; // Undetermined ans[first] = exp(M[i][cols-1]); } return ans; } int main(){ int y, c, q; cin >> y >> c >> q; vector r(y-1); for(auto& x : r) cin >> x; vector > A(y, vector(c)); for(auto& v : A) for(auto& x : v) cin >> x; vector > matrix; // pr(A,x) = // pr(A,last)*infl(last)*infl(last+1)* ... *infl(x-1) * modif(A)^(last-x) for(int i=1;i row(y*c+y+c+1); row[j*y + i] = -1; row[j*y + (i-1)] = 1; row[y*c + c + i-1] = 1; row[y*c + j] = 1; matrix.push_back(row); } // Add in the known information // ... First, the prices... for(int i=0;i= -0.5){ vector row(y*c+y+c+1); row[j*y + i] = 1; row.back() = log(A[i][j]); matrix.push_back(row); } // ... Second, the inflation rates for(int i=0;i= -0.5){ vector row(y*c+y+c+1); row[y*c + c + i] = 1; row.back() = log(r[i]); matrix.push_back(row); } vector ans = solve(matrix); while(q--){ int a, b; cin >> a >> b; a--; b--; cout << fixed << setprecision(10) << ans[a*y+b] << endl; } }