D2308

//////////////////////////////
package d2308;

import java.util.Scanner;

public class HoDen {
	static int t, n, ux, uy, sx, sy;
	static int[][] hoden = new int[n][5];
	static int res = 99999999;
	static int[] visit = new int[n];

	public static int kc(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}

	public static void Try(int k, int sum, int prevx, int prevy) {
		if (k == n) {
			if (sum + kc(sx, sy, prevx, prevy) < res) {
				res = sum + kc(sx, sy, prevx, prevy);
			}
			return;
		}
		for (int i = 0; i < n; i++) {
			if(visit[i] == 0){
				for (int j = 0; j < 3; j++) {
					if (j == 0) {
						// khong vao
						Try(k + 1, sum, prevx, prevy);
					} else if (j == 1) {
						// vao dau ra dit
						visit[i] = 1;
						Try(k + 1, sum + kc(prevx, prevy, hoden[i][0], hoden[i][1])
								+ hoden[i][4], hoden[i][2], hoden[i][3]);
						visit[i] = 0;
					} else if (j == 2) {
						// vao dit ra dau
						visit[i] = 1;
						Try(k + 1, sum + kc(prevx, prevy, hoden[i][2], hoden[i][3])
								+ hoden[i][4], hoden[i][0], hoden[i][1]);
						visit[i] = 0;
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			n = sc.nextInt();
			ux = sc.nextInt();
			uy = sc.nextInt();
			sx = sc.nextInt();
			sy = sc.nextInt();
			hoden = new int[n][5];
			visit = new int[n];
			res = kc(ux, uy, sx, sy);
			for (int i = 0; i < n; i++) {
				hoden[i][0] = sc.nextInt();
				hoden[i][1] = sc.nextInt();
				hoden[i][2] = sc.nextInt();
				hoden[i][3] = sc.nextInt();
				hoden[i][4] = sc.nextInt();
			}
			Try(0, 0, ux, uy);
			System.out.println("#"+tc+" "+res);
		}
	}

}
///////////////////////////////////
package luyentap2307;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class visitdepartment {
	static int N, E, K, T;
	static int len = 3000;
	static float[][] arr = new float[len][len];
	static float[][] timeXacSuat = new float[len][len];
	public static void reset() {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = 0;
				timeXacSuat[i][j] = 0;
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/luyentap2307/inputvisitdepartment.txt"));
		Scanner scanner = new Scanner(System.in);
		for (int tc = 1; tc <= 10; tc++) {
			N = scanner.nextInt();
			E = scanner.nextInt();
			K = scanner.nextInt();
			T = scanner.nextInt();
			reset();
			for (int i = 0; i < E; i++) {
				int dinh1 = scanner.nextInt();
				int dinh2 = scanner.nextInt();
				arr[dinh1][dinh2] = scanner.nextFloat();
			}
			//node
			timeXacSuat[1][0] = 1;
			for (int t = 1; t <= T; t++) {
				for (int i = 1; i <= N; i++) {
					if (timeXacSuat[i][t-1] != 0) {
						for (int j = 1; j <= N; j++) {
							timeXacSuat[j][t] += timeXacSuat[i][t-1]*arr[i][j];
						}
					}
				}
			}
			//Jang start tai 0, Kang tai K
			//10p di chuyen 1 lan
			int jangTime = T/10, kangTime = (T-K)/10;
			int jangD = 0, kangD = 0;
			float jangXS = 0, kangXS = 0;
			for (int i = 1; i <= N; i++) {
				if (timeXacSuat[i][jangTime] > jangXS) {
					jangXS = (float)timeXacSuat[i][jangTime];
					jangD = i;
				}
				if (timeXacSuat[i][kangTime] > kangXS) {
					kangXS = (float)timeXacSuat[i][kangTime];
					kangD = i;
				}
			}
			
			System.out.print("#" + tc + " ");
			System.out.println(String.format("%d %.6f %d %.6f", jangD, jangXS, kangD, kangXS));
		}
	}
}
////////////////////////////////
package luyentap2007;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class nangluongvutru {
	static int N, A, B, C;
	static double[][] map;
	static double mid;
	static double[][] haophi;
	final static double delta = 0.00000001; 
	static double[] key;
	static long[] parent;
	static boolean[] mstSet;
	final static int LONG_MAX = 10000000;
	public static int minKey() {
       double min = LONG_MAX;
       int min_index = 0;
       for (int v = 0; v < N; v++)
         if (mstSet[v] == false && key[v] < min) {
        	 min = key[v];
        	 min_index = v;
         }
       return min_index;
	}
	public static void primMST() {

	   for (int i = 0; i < N; i++) {
		   key[i] = LONG_MAX;
		   mstSet[i] = false;
	   }
	   key[0] = 0; 
	   parent[0] = -1;

	   for (int count = 0; count <= N-1; count++) {
	      int u = minKey();

	      mstSet[(int)u] = true;

		    for (int v = 0; v < N; v++)
				if (mstSet[v] == false && haophi[u][v] <  key[v]){
					parent[v]  = u;
					key[v] = haophi[u][v];
				}
	    }
	 }
	public static double Fx(double x, double K) {
		double scale = Math.pow(10, 6);
		double F = A*x*x*x + B*x*x + C - K;
		return Math.ceil(F*scale)/scale;
	}
	public static double timnghiem(double K) {
		double scale = Math.pow(10, 6);
		double left = 0;
		double right = 2097152;
		while (true) {
			if (right - left <= delta) {
				return Math.ceil(mid*scale)/scale;
			}
			mid = (left + right)/2;
			double temp = Fx(left, K)*Fx(mid, K);
			if (temp <= 0) {
				right = mid;
			} else if (temp > 0) {
				left = mid;
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/luyentap2007/inputnangluongvutru.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = scanner.nextInt();
			A = scanner.nextInt();
			B = scanner.nextInt();
			C = scanner.nextInt();
			map = new double[N][N];
			haophi = new double[N][N];
			key = new double[N];
			parent = new long[N];
			mstSet = new boolean[N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = scanner.nextDouble();
				}
			}
			for (int i = 0; i < N-1; i++) {
				for (int j = i + 1; j < N; j++) {
					if (map[i][j] != 0) {
						double k = map[i][j];
						haophi[i][j] = timnghiem(k);
						haophi[j][i] = haophi[i][j];
						map[i][j] = 0;
					}
				}
			}
			double sum = 0;
			primMST();
			for (int i = 0; i < N; i++) {
				sum += key[i];
			}
			System.out.println(String.format("#" + tc + " " + "%.3f", sum));
		}
	}
}
////////////////////////////
package training;

import java.util.Scanner;

public class Calculator3 {
	static char[] stack;
	static int n;
	static int top = -1;
	public static void push(char x){
		if(top >= n-1){
		}
		else{
			top++;
			stack[top] = x;
		}
	}
	public static void pop(){
		if(top <= 0){
		}
		else{
			top--;
		}
	}
	public static char peek(){
		return stack[top];
	}
	public static int uutien(char x){
		if(x == '+'){
			return 1;
		}
		else if(x == '*'){
			return 2;
		}
		else{
			return -1;
		}
	}
	public static boolean isEmpty(char[] stack, int top) {
		if (top == -1) {
			return true;
		} else {
			return false;
		}
	}
	static int[] stack1;
	static int n1;
	static int top1 = -1;
	public static void push1(int x){
		if(top1 >= n1-1){
		}
		else{
			top1++;
			stack1[top1] = x;
		}
	}
	public static void pop1(){
		if(top1 <= 0){
		}
		else{
			top1--;
		}
	}
	public static int peek1(){
		return stack1[top1];
	}
	
	public static boolean isEmpty1(int[] stack1, int top1) {
		if (top1 == -1) {
			return true;
		} else {
			return false;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		for(int t= 1;  t<= 10; t++){
			n = sc.nextInt();
			sc.nextLine();
			stack = new char[n];
			String s = sc.nextLine();
			int res = 0;
			String postfix = "";
			for(int i = 0 ; i < s.length() ; i++){
				if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
					postfix = postfix+s.charAt(i);
				}
				else if(s.charAt(i) == '('){
					push(s.charAt(i));
				}
				else if(s.charAt(i) == ')'){
					while(!isEmpty(stack, top) && peek() != '('){
						postfix = postfix+peek();
						pop();
					}
					pop();
				}
				else{
					while(!isEmpty(stack, top) && uutien(s.charAt(i)) < uutien(peek())){
						postfix = postfix+peek();
						pop();
					}
					push(s.charAt(i));
				}
				
			}
			n1 = postfix.length();
			stack1 = new int[n1];
			for(int i = 0 ; i < n1 ; i++){
				if(postfix.charAt(i) >= '0' && postfix.charAt(i) <= '9'){
					int tmp = postfix.charAt(i) - '0';
					push1(tmp);
 				}
				if(postfix.charAt(i) == '*'){
					int x = peek1();
					pop1();
					int y = peek1();
					pop1();
					push1(x*y);
				}
				if(postfix.charAt(i) == '+'){
					int x = peek1();
					pop1();
					int y = peek1();
					pop1();
					push1(x+y);
				}
			}
			System.out.println("#"+t+" "+peek1());
			top = -1;
			top1 = -1;
		}
	}

}
/////////////////////////
package training;

import java.util.Scanner;

public class CuttingPiece {
	static int tc,n;
	static int blue = 0,white = 0;
	static int[][] a = new int[n][n];
	
	public static boolean check(int x,int y , int len){
		int tmp = a[x][y];
		for(int i = 0 ; i < len ; i++){
			for(int j = 0 ; j < len ; j++){
				if(a[x+i][y+j] != tmp){
					return false;
				}
			}
		}
		return true;
	}
	
	public static void Try(int x , int y , int len){
		if(check(x, y, len)){
			if(a[x][y] == 1){
				blue++;
				return;
			}
			else{
				white++;
				return;
			}
		}
		else{
			int tmp = len/2;
			Try(x, y, tmp);
			Try(x+tmp, y, tmp);
			Try(x+tmp, y+tmp, tmp);
			Try(x, y+tmp, tmp);
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		tc = sc.nextInt();
		for(int t = 1 ; t <= tc ; t++){
			n = sc.nextInt();
			a = new int[n][n];
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			Try(0, 0, n);
			System.out.println("Case #"+t);
			System.out.println(white+" "+blue);
			white = 0;
			blue = 0;
		}
	}

}
////////////////
package training;

import java.util.Scanner;

public class DaoCot {
	static int t,n,m,k;
	static int[][] a = new int[n][m];
	
	public static boolean check(int[] a , int[] b){
		for(int i = 0 ; i < m ;i++){
			if(a[i] != b[i]){
				return false;
			}
		}
		return true;
	}
	public static int countZero(int[] a){
		int tmp = 0;
		for(int i = 0 ; i < m ; i++){
			if(a[i] == 0){
				tmp++;
			}
		}
		return tmp;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int tc = 1 ; tc <= t ; tc++){
			n = sc.nextInt();
			m = sc.nextInt();
			k = sc.nextInt();
			a = new int[n][m];
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < m ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			int res = 0;
			for(int i = 0 ; i < n ; i++){
				int dem = 1;
				for(int j = i+1 ; j < n ; j++){
					if(check(a[i], a[j])){
						dem++;
					}
				}
				int col = countZero(a[i]);
				if(col <= k && (k-col)%2 == 0){
					if(res < dem){
						res =dem;
					}
				}
			}
			System.out.println("Case #"+tc+" "+res);
		}
	}

}
///////////////////////////
package training;

import java.util.Scanner;

public class DiChuyenBo {
	static int t,n,m;
	static int[] a = new int[n];
	static int res =0 ;
	
	public static void Try(int k, int cnt){
		if( k == n ){
			if(res < cnt){
				res = cnt;
			}
			return;
		}
		for(int i = 0 ; i < 2 ; i++){
			if(i == 1 && cnt+ a[k] <= m){
				Try(k+1, cnt+a[k]);
			}
			else if( i == 0){
				Try(k+1, cnt);
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int tc = 1 ; tc <= t ; tc++){
			m = sc.nextInt();
			n = sc.nextInt();
			a = new int[n];
			for(int i = 0 ; i < n ;i++){
				a[i] = sc.nextInt();
			}
			res = 0;
			Try(0, 0);
			System.out.println("#"+tc+" "+res);
		}
	}

}
/////////////////////////////////////
package training;

import java.util.Scanner;

import javax.naming.InitialContext;

public class EarnMoney {
	static int t,n;
	static String s;
	static int N;
	static int[] a = new int[N];
	static int res = 0;
	public static int convert(int[] a){
		int tmp =  0;
		for(int i = 0 ; i < a.length; i++){
			tmp = tmp*10 +a[i];
		}
		return tmp;
	}
	public static void Try(int i,int ex){
		if(i == N){
			int hasswap = 0;
			if((n-ex)%2 == 1){
				swap(a,N-1, N-2);
				hasswap =  1;
			}
			int tmp = convert(a);
			if(tmp > res){
				res = tmp;
			}
			if(hasswap == 1){
				swap(a,N-1, N-2);
			}
			return;
		}
		if(ex < n){
			for(int j = i + 1 ; j < N ; j++){
				swap(a, i, j);
				Try(i+1, ex+1);
				swap(a, i, j);
			}
		}
		Try(i+1, ex);
	}
	
	public static void swap(int[] a,int x, int y){
		int tmp = a[x];
		a[x] = a[y];
		a[y] = tmp;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in );
		t = sc.nextInt();
		sc.nextLine();
		for(int tc = 1 ; tc <= t ; tc++){
			s = sc.next();
			n =sc.nextInt();
			N = s.length();
			a = new int[N];
			for(int i = 0 ; i < s.length() ; i++){
				a[i] = s.charAt(i) - '0';
			}
			Try(0, 0);
			System.out.println("Case #"+tc);
			System.out.println(res);
			res = 0;
		}
	}

}
////////////////////////////////
package training;

import java.util.Scanner;

public class FindMode {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int t = 10;
		for(int p = 0 ; p < t ; p++){
			int res = 0;
			int[] a = new int[201];
			for(int i = 0 ; i <= 200 ; i++){
				a[i] = 0;
			}
			for(int i = 0 ; i < 1000 ; i++){
				int x = sc.nextInt();
				a[x]++;
			}
			for(int i = 0 ; i <= 200 ; i++){
				if(a[i] >= a[res]){
					res = i;
				}
			}
			System.out.println("#"+(p+1)+" "+res);
		}
	}

}
/////////////////////////////////////
package training;

import java.util.Scanner;

public class GNS {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		sc.nextLine();
		for(int p = 0 ; p < t ; p++){
			String[] a = {"ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN"};
			String tc = sc.next();
			int n = sc.nextInt();
			sc.nextLine();
			String[] b = new String[10000];
			for(int i = 0 ; i < n ; i++){
				b[i] = sc.next();
			}
			System.out.println(tc);
			for(int i = 0 ; i < 10; i++){
				for(int j = 0 ; j < n ; j++){
					if(b[j].equals(a[i])){
						System.out.print(b[j] + " ");
					}
				}
			}
			System.out.println();
		}
	}

}