/**
 * Code for exercise 3
 * Lecture Series Informatik II D-BAUG ETH Zürich  
 * Felix Friedrich, Georg Ofenbeck, Lars Widmer
 */

class LCG { //this is the random number generator from last exercise
	static final long m = 2147483647;
	static final long b = 12345;
	static final long a = 1103515245;
	static long u = 0; //to use within the judge we fix the "seed", such that we always get the same random numbers	
	
	public static double Uniform(){
		u = (u * a + b) % m;
		return(double)u/m;
	}
}

// provide your modifications in this class only
class RandomSurfer{		
	
	// pre: non-empty matrix m
	// post: matrix printout on System.out
	public static void printMatrix(double[][] m) {
		// implement this
	}

	// pre: matrix data provided via scanner
	// post: returns matrix data
	public static double[][] readMatrix(java.util.Scanner scanner){		
		// implement this
		return null;
	}
	
	// pre: non-empty input vector of length N, matrix of size N times M
	// post: return vector-matrix product v * m. Vector of size M
	public static double[] multiplyVectorMatrix(double[] v, double[][] m) {
		// implement this
		return null;
	}

	// non-empty vector v and probability matrix m, precision > 0
	// returns if v * m is close at v
	public static boolean checkConvergence(double[] v, double[][] P, double precision){
		// implement this
		return true;
	}



	// single step simulation from the lecture
	public static int simulateLine(double[] prob)
	{
		int res=0;
		double r = LCG.Uniform(); 
		double sum = 0.0; 
		for (int j = 0; j < prob.length; j++) {
			sum += prob[j]; 
			if (r < sum) {res = j; break;}
		}
		return res;
	}
	
	// pre: non-empty probability matrix P 
	// post: return relative frequencies of visits in each point
	//	       after MCMC simulation until convergence reached
	public static double[] simulate(double[][] P, double precision) {					
		// implement this
		return null;
	}	
	

	
	
	// pre: non-empty vector v and n times n probability matrix 
	// post: vector v close at stationary distribution of m
	//	       returns number of vector-matrix multiplications required
	public static int calculateDirect(double[] v, double[][] m, double precision){
		// implement this
		return 0;
	}
	
	// pre: non-null vector
	// post: vector output to standard out
	public static void show(double[] v) {
		for (int i=0; i<v.length; ++i)
			System.out.printf("%7.5f ",v[i]);
		System.out.println();
	}
		
	// test program to test convergence speeds. 
	// Can be freely modified and does not have any impact on the result of the judge
	public static void main(String[] args) {
		double[][] m = { // transition probabilities 
				{0.1,0.3,0.2,0.1,0.3},
				{0.1,0.2,0.1,0.3,0.3},
				{0.3,0.1,0.3,0.2,0.1},
				// {0,0,0.0,0.0,0.0},
				{0.5,0.5,0.0,0.0,0.0},
				{0.9,0.0,0.0,0.1,0.0}};
		
		double precision = 0.0001;
		
		long before_sim = System.currentTimeMillis();
		show(simulate(m, precision));
		long after_sim = System.currentTimeMillis();		
		System.out.println("Simulation took " + (after_sim - before_sim) + " Milliseconds");
		System.out.println("---------------------------------------------------------------");
		
		long before_calculate = System.currentTimeMillis();
		double[] v = {1,0,0,0,0}; // starting state
		System.out.println(calculateDirect(v,m, precision));
		show(v);
		long after_calculate = System.currentTimeMillis();		
		System.out.println("Direct calculation took " + (after_calculate - before_calculate) + " Milliseconds");
		System.out.println("---------------------------------------------------------------");					
	}

}


//---------------------------------------------------------------------------------
// Unfortunately it is a restriction of the judge that we always have to have a public class Main in our file
// The code below is only used to validate your code with the judge - feel free to browse - but its not required for the exercise
//------------------------------------------------------------------------------------------------------------------------
class Main{ 
	
	public static double[] readV(java.util.Scanner scanner){		
		int n = scanner.nextInt();
		double[] res = new double[n];     
	  	for (int i = 0; i < n; i++)
	  		res[i] = scanner.nextDouble(); 
		return res;
	}
		
	public static void main(String[] args) {
		java.util.Scanner scanner = new java.util.Scanner(System.in);
		int choice = scanner.nextInt();
		
		if (choice == 1){
			double[][] o = {{1,2},{3,4},{5,6}};
			RandomSurfer.printMatrix(o);
		}
		if (choice == 2){
			double[][] m = RandomSurfer.readMatrix(scanner);
			RandomSurfer.printMatrix(m);
		}
		if (choice == 3) {
			double[] v = readV(scanner);
			double[][] m = RandomSurfer.readMatrix(scanner); 
			RandomSurfer.show(RandomSurfer.multiplyVectorMatrix(v,m));
		}
		if (choice == 4) {
			double[] v = readV(scanner);
			double[][] m = RandomSurfer.readMatrix(scanner); 
			double precision = scanner.nextDouble();
			System.out.println(RandomSurfer.checkConvergence(v, m, precision));			
		}
		if (choice == 5) {
			double[][] m = RandomSurfer.readMatrix(scanner); 
			double precision = scanner.nextDouble();			
			RandomSurfer.show(RandomSurfer.simulate(m, precision));
		}
		if (choice == 6) {
			double[] v = readV(scanner);
			double[][] m = RandomSurfer.readMatrix(scanner);
			double precision = scanner.nextDouble();
			System.out.println(RandomSurfer.calculateDirect(v, m, precision));
			RandomSurfer.show(v);
		}
	}
}

/*
data that can be used to check (use copy and paste to check)
1. PrintMatrix Input:
1

Expected output:
3 2
1.00000 2.00000 
3.00000 4.00000 
5.00000 6.00000

2. ReadMatrix Input:
2
2 3
1 2 3 4 5 6

Expected output:
2 3
1.00000 2.00000 3.00000 
4.00000 5.00000 6.00000

3. MutiplyVectorMatrix Input:
3
3
1 2 3
3 3 
1 2 3
4 5 6
7 8 9

Expected output:
30.00000 36.00000 42.00000 

4. CheckConvergence Input:
4
5
0.32518 0.22739 0.12541 0.14368 0.17834
5 5
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000
0.0001

Expected output:
true

5. Simulate Input:
5
5 5
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000 
0.0001 

Expected output:
0.32517 0.22769 0.12524 0.14370 0.17821

6. Calculate Direct Input:
6
5 
1 0 0 0 0
5 5 
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000 
0.0001

Expected output:
12
0.32518 0.22739 0.12541 0.14368 0.17834
*/