/* * Solution for NAIPC 2019 Inflation * @author godmar */ import static java.lang.Math.*; import java.util.*; import java.io.*; public class Inflation_godmar_onebyone { static final boolean DEBUG = false; public static void main(String ...args) { Scanner s = new Scanner(); int y = s.nextInt(); int c = s.nextInt(); int q = s.nextInt(); double [] f = new double[y-1]; int equations = 1; for (int i = 0; i < y - 1; i++) { f[i] = s.nextDouble(); if (f[i] != -1) equations++; } double [][] p = new double[y][c]; for (int i = 0; i < y; i++) { for (int j = 0; j < c; j++) { p[i][j] = s.nextDouble(); if (p[i][j] != -1) equations++; } } /* * Variables are ordered like this: * * [0, c) price of commodity k in year 0. * [c, 2c) modifier for commodity k * [2c, 2c + y - 1) inflation rate for year 0 to 1, 1 to 2, * etc. * [2c + y - 1, 2c + y - 1 + q) variables that reflect linear combinations of the queries */ int pricebase = 0; int modbase = pricebase + c; int inflationbase = modbase + c; int querybase = inflationbase + y - 1; int rhs = querybase + 1; // one at a time if (DEBUG) System.err.printf("equations %d queries %d variables %d%n", equations, q, rhs); PrintWriter out = new PrintWriter(System.out, false); // process each query one by one for (int qn = 0; qn < q; qn++) { double [][] A = new double[equations][rhs + 1]; int eq = 0; for (int i = 0; i < y - 1; i++) { if (f[i] != -1) { // if an inflation rate is given, add its value A[eq][inflationbase + i] = 1; A[eq][rhs] = log(f[i]); eq++; } } for (int i = 0; i < y; i++) { for (int j = 0; j < c; j++) { if (p[i][j] != -1) { // sum of f[0...i] for (int k = 0; k < i; k++) A[eq][inflationbase+k] = 1; A[eq][pricebase+j] = 1; // year 0 price A[eq][modbase+j] = i; // modifier for j A[eq][rhs] = log(p[i][j]); // rhs eq++; } } } // add linear combinations for query int a = s.nextInt() - 1; // commodity, 1-based int b = s.nextInt() - 1; // year, 1-based A[eq][querybase] = 1; A[eq][modbase+a] = -b; A[eq][pricebase+a] = -1; for (int j = 0; j < b; j++) A[eq][inflationbase+j] = -1; eq++; if (eq != equations) throw new Error("you can't count, only " + eq + " out of " + equations); Solution sol = solvelinearsystem(A); if (DEBUG) System.err.printf("Solution is %s%n", sol); // I assume the problem guarantees consistent input if (sol == Solution.INCONSISTENT) throw new Error("Test case inconsistent, EPS " + EPSILON); // read out the solutions Map answers = new HashMap<>(); for (int i = 0; i < equations; i++) { int onepos = -1; for (int j = 0; j < rhs; j++) { if (abs(A[i][j] - 1.0) < EPSILON) if (onepos == -1) { onepos = j; } else { onepos = -1; break; } else if (abs(A[i][j]) > EPSILON) { onepos = -1; break; } } if (querybase <= onepos) { // yeah, we got an answer to a query! answers.put(onepos-querybase, exp(A[i][rhs])); } } out.println(answers.getOrDefault(0, -1.0)); } out.close(); } // Ported from C++ version originally at // http://stanford.edu/~liszt90/acm/notebook.html#file15 final static double EPSILON = 1e-8; // // Reduced row echelon form via Gauss-Jordan elimination // with partial pivoting. This can be used for computing // the rank of a matrix. // // Running time: O(n^3) // // INPUT: a[][] = an nxm matrix // // OUTPUT: rref[][] = an nxm matrix (stored in a[][]) // returns { rank of a[][], index of last pivot column } static double [][] a; static int [] rref(double [][]_a) { a = _a; int n = a.length; int m = a[0].length; int r = 0; int lastc = 0; // last pivot column for (int c = 0; c < m && r < n; c++) { int j = outlineInnerLoop2ForHotspot(r, c, m, n); if (abs(a[j][c]) < EPSILON) continue; lastc = c; double [] temp = a[r]; // swap(a[j], a[r]); a[r] = a[j]; a[j] = temp; double s = 1.0 / a[r][c]; for (int k = 0; k < m; k++) a[r][k] *= s; outlineInnerLoopForHotspot(r, c, m, n); r++; } return new int [] { r, lastc }; } static void outlineInnerLoopForHotspot(int r, int c, int m, int n) { for (int i = 0; i < n; i++) if (i != r) { double t = a[i][c]; for (int k = 0; k < m; k++) a[i][k] -= t * a[r][k]; } } static int outlineInnerLoop2ForHotspot(int r, int c, int m, int n) { int j = r; for (int i = r+1; i < n; i++) if (abs(a[i][c]) > abs(a[j][c])) j = i; return j; } /* * Linear Equation Solver for dummies (that's us). * * Solve a general system of linear equations with a single * rhs, given in augmented form A | b. * * rank(A) = rank(A|b) = n : unique solution * rank(A) = rank(A|b) < n : many solutions * rank(A) < rank(A|b) : no solutions */ enum Solution { UNIQUE, MANY, INCONSISTENT } static Solution solvelinearsystem(double [][]A) { /* Likely you will want to debug that you constructed * the system correctly during a contest. */ if (DEBUG) { System.err.println("Solving linear system:"); for (int i = 0; i < A.length; i++) System.err.println(java.util.Arrays.toString(A[i])); } int m = A.length; // number of equations, not used int n = A[0].length - 1; // number of variables int [] rc = rref(A); int rankAb = rc[0]; int lastpivotcol = rc[1]; boolean rankAEqualrankAb = lastpivotcol < n; if (DEBUG) { System.err.println("RREF is:"); for (int i = 0; i < A.length; i++) System.err.println(java.util.Arrays.toString(A[i])); } if (!rankAEqualrankAb) return Solution.INCONSISTENT; if (rankAb == n) return Solution.UNIQUE; if (rankAb < n) return Solution.MANY; throw new Error(); } //-----------Scanner class for faster input---------- /* Provides similar API as java.util.Scanner but does not * use regular expression engine. */ public static class Scanner { BufferedReader br; StringTokenizer st; public Scanner(Reader in) { br = new BufferedReader(in); } public Scanner() { this(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } // Slightly different from java.util.Scanner.nextLine(), // which returns any remaining characters in current line, // if any. String readNextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } //-------------------------------------------------------- }