import java.io.PrintStream; import java.util.Arrays; import java.util.Scanner; /** * Solution to Inflation * * @author vanb & arcoleman */ public class inflation_vanb_arc { /** The Input. */ private static Scanner sc; /** The Output. */ private static PrintStream ps; /** * Is this value known? * * @param x Value to test * @return true, if x is known (not -1), otherwise false. */ private boolean known( double x ) { return x>-0.5; } /** * Transitive closure. * * @param a An array * @param i An index * @param j Another index * @param k A third index * @return true, if a[i][k] is previously unknown but can be computed from a[i][j] and a[j][k] */ private boolean transitive( double a[][], int i, int j, int k ) { boolean changed = false; if( !known(a[i][k]) && known(a[i][j]) && known(a[j][k]) ) { a[i][k] = a[i][j] * a[j][k]; a[k][i] = 1.0 / a[i][k]; changed = true; } return changed; } /** * Do It! */ private void doit() { int y = sc.nextInt(); int c = sc.nextInt(); int q = sc.nextInt(); // We get the inflation for year i to year i+1. // But, we can find the inflation rate between any two years. // So, inflation needs to be a 2D array. double inflation[][] = new double[y][y]; // Initialize inflation array for( int i=0; i -.5 && prices[k][j] > -.5) { if(a == -1) a = k; else b = k; } } // If two commodities share a year, then we can convert either of them to each other if(a != -1 && b != -1) { double r1 = prices[b][j] / prices[a][j]; double r2 = prices[b][i] / prices[a][i]; double rat = Math.pow(r1/r2, 1.0/(b-a)); for(int k=0;k -.5 && prices[k][j] < -.5) { double rate = prices[k][i] / prices[b][i] * Math.pow(rat, k-b); prices[k][j] = prices[b][j] * rate; changed = true; } else if(prices[k][i] < -.5 && prices[k][j] > -.5) { double rate = prices[k][j] / prices[b][j] * Math.pow(1/rat, k-b); prices[k][i] = prices[b][i] * rate; changed = true; } } } } } } while( changed ); // OK, now answer the queries by just looking in the prices[][] table. for( int i=0; i