D2308

package training;

import java.util.Scanner;

public class Ladder2 {
	static int n;
	static int[][] a = new int[100][100];
	public static int go(int col){
		int cnt = 0;
		int j = col;
		for(int i = 0 ; i < 100 ; i++){
			if(j - 1 >=0 && a[i][j-1] == 1){
				while(j-1 >= 0 && a[i][j-1] == 1){
					j--;
					cnt++;
				}
			}
			else if(j+1 <= 99 && a[i][j+1] == 1){
				while(j+1 <=  99 && a[i][j+1] == 1){
					j++;
					cnt++;
				}
			}
			cnt++;
		}
		
		return cnt;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		for(int t = 1 ; t <= 10  ; t++){
			n = scanner.nextInt();
			for(int i = 0 ; i < 100 ; i++){
				for(int j = 0 ; j < 100 ; j++){
					a[i][j] = scanner.nextInt();
				}
			}
			int res = 100000,min = 100000;
			for(int i = 0 ; i < 100 ;i++){
				if(a[0][i] == 1){
					int tmp = go(i);
					
					if(tmp < min ){
						min = tmp;
						res = i;
					}
				}
			}
			System.out.println("#"+t+" "+res);
		}
	}

}
////////////////////////////
	package training;
	
	import java.util.Scanner;
	
	public class Level5Game {
		static int t,n;
		static int[] a = new int[n];
		
		public static int easybot(int i , int j){
			if(i > j ){
				return 0;
			}
			int t1 = a[i] + easybot(i+1, j-1);
			int t2 = a[i] + easybot(i+2, j);
			int t3 = a[j] + easybot(i+1, j-1);
			int t4 = a[j] + easybot(i, j-2);
			int max = t1;
			if(t2 > t1){
				max = t2;
			}
			int max2 = t3;
			if(t3 < t4){
				max2 = t4;
			}
			if(max > max2){
				return max;
			}
			else{
				return max2;
			}
		}
		
		public static int hardbot(int i,int j){
			if(i > j ){
				return 0;
			}
			int t1 = a[i] + hardbot(i+1, j-1);
			int t2 = a[i] + hardbot(i+2, j);
			int t3 = a[j] + hardbot(i+1, j-1);
			int t4 = a[j] + hardbot(i, j-2);
			int min = t1;
			if(t2 < t1){
				min = t2;
			}
			int min2 = t3;
			if(t3 > t4){
				min2 = t4;
			}
			if(min > min2){
				return min;
			}
			else{
				return min2;
			}
		}
		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();
				a = new int[n];
				for(int i = 0 ; i < n ; i++){
					a[i] = sc.nextInt();
				}
				System.out.println("Case #"+tc);
				System.out.println(easybot(0,n-1)+ " "+ hardbot(0,n-1));
				
			}
		}
	
	}
/////////////
package training;

import java.util.Scanner;

public class Maze2 {
	static int[][] step = {{-1,0},{1,0},{0,-1},{0,1}};
	static int res = 0;
	static int[][] a = new int[100][100];
	static int nx,ny;
	public static void Try(int x,int y){
		for(int i = 0 ; i < 4 ; i++){
			int x1 = x + step[i][0];
			int y1 = y + step[i][1];
			if(x1 >= 0 && x1 <= 99 && y1 >= 0 && y1 <= 99 && a[x1][y1] == 3){
				res = 1;
				return;
			}
			if(x1 >= 0 && x1 <= 99 && y1 >= 0 && y1 <= 99 && a[x1][y1] == 0){
				a[x1][y1] = 1;
				Try(x1, y1);
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		for(int t = 1 ;t <= 10 ; t++){
			sc.nextInt();
			sc.nextLine();
			for(int i = 0 ; i < 100 ; i++){
				String s = sc.nextLine();
				for(int j = 0 ; j < 100 ; j++){
					int tmp = s.charAt(j) - '0';
					a[i][j] = tmp;
					if(a[i][j] == 2){
						nx = i;
						ny = j;
					}
				}
			}
			Try(nx, ny);
			System.out.println("#"+t+" "+res);
			res = 0;
		}
	}

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

import java.util.Scanner;

public class MeetingRoom {
	static int t,n;
	static int[][] a = new int[n][3];
	public static void swap(int[][] a , int i , int j ){
		int[] tmp = a[i];
		a[i] = a[j];
		a[j] = 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();
			a = new int[n][3];
			for(int i = 0 ; i < n ; i++){
				a[i][0] = sc.nextInt();
				a[i][1] = sc.nextInt();
				a[i][2] = sc.nextInt();
			}
			int res = 0;
			int finish = 0;
			for(int i = 0 ;  i < n ; i++){
				for(int j =  i + 1 ;  j < n ; j++){
					if(a[i][2] > a[j][2]){
						swap(a, i, j);
					}
				}
			}
			res = 1;
			finish = a[0][2];
			for(int i = 1 ; i < n ; i++){
				if(a[i][1] >= finish){
					res++;
					finish = a[i][2];
				}
			}
			System.out.println("Case #"+tc);
			System.out.println(res);
		}
	}

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

import java.awt.Checkbox;
import java.util.Scanner;

public class Palindrome2 {
	static char[][] a = new char[100][100];

	public static boolean checkRow(int r, int s, int len) {
		for (int i = 0; i <= len / 2; i++) {
			if (a[r][s + i] != a[r][s + len - 1 - i]) {
				return false;
			}
		}
		return true;
	}

	public static boolean checkCol(int r, int s, int len) {
		for (int i = 0; i <= len / 2; i++) {
			if (a[s + i][r] != a[s + len - 1 - i][r]) {
				return false;
			}
		}
		return true;
	}

	public static boolean isPalin(int h) {
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j <= 100 - h; j++) {
				if (checkRow(i, j, h)) {
					return true;
				}
				if (checkCol(i, j, h)) {
					return true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int t;
		for (int p = 0; p < 10; p++) {
			int res = 1;
			t = sc.nextInt();
			sc.nextLine();

			for (int i = 0; i < 100; i++) {
				String s = sc.nextLine();
				for (int j = 0; j < 100; j++) {
					char tmp = s.charAt(j);
					a[i][j] = tmp;
				}
			}
			for (int h = 100; h >= 1; h--) {
				if (isPalin(h)) {
					res = h;
					break;
				}
			}
			System.out.println("#" + t + " " + res);

		}
	}

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

import java.util.Scanner;

public class Partition2 {
	static int t,n;
	static int[] a = new int[n];
	static int[] b = new int[n];
	public static void swap(int[] a , int i , int j ){
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	public static void sort(int[] a , int n){
		for(int i = 0 ; i < n ; i++){
			for(int j  = i + 1 ; j <  n ; j++){
				if(a[i] > a[j]){
					swap(a, i, j);
				}
			}
		}
	}
	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();
			a = new int[n];
			b = new int[n];
			int dem = n;
			for(int i = 0 ; i < n ; i++){
				a[i] = sc.nextInt();
				b[i] = a[i];
			}
			int res = 0;
			sort(a,n);
			while(n > 1){
				res = res + a[0] +a[1];
				a[0] = a[0] +a[1];
				for(int i = 1 ; i < n-1 ; i++){
					a[i] = a[i+1];
				}
				n--;
				sort(a, n);
			}
			System.out.println("Case #"+tc);
			System.out.println(res);
		}
	}

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

import java.awt.image.RescaleOp;
import java.util.Scanner;

public class Password {
	static int N;
	static String s;
	static char[] stack;
	static int top = -1;
	public static void  push(char x) {
		if (top >= N-1) {
			//overflow
		}
		else {
			top++;
			stack[top] = x;
		}
	}
	public static void pop() {
		if (top <= 0) {
			//overflow
		} else {
			top--;
		}
	}
	public static boolean isEmpty(char[] stack, int top) {
		if (top == -1) {
			return true;
		} else {
			return false;
		}
	}
	public static char peek() {
		return stack[top];
	}
	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();
			int res = -1;
			sc.nextLine();
			stack = new char[N];
			s = sc.nextLine();
			for(int i = 0 ; i < N ; i++){
				if(s.charAt(i) == '(' 
						|| s.charAt(i) == '<' 
						|| s.charAt(i) == '{' 
						|| s.charAt(i) == '['){
					push(s.charAt(i));
				}
				else{
					if(isEmpty(stack, top)){
						res = 0;
						break;
					}
					else{
						char tmp = peek();
						if((s.charAt(i) == '>' && tmp == '<') 
								||(s.charAt(i) == ')' && tmp == '(')
								|| (s.charAt(i) == '}' && tmp == '{') 
								|| (s.charAt(i) == ']' && tmp == '[')){
							pop();
							continue;
						}
						else{
							res = 0;
							break;
						}
					}
				}
			}
			if(top == 0 && res != 0){
				res = 1;
			}
			else{
				res = 0;
			}
			System.out.println(top);
			top = -1;
			System.out.println("#"+t+" "+res);
		}
	}

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

import java.util.Scanner;

public class PasswordGen {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		for(int t = 1 ;t <= 10 ;t++){
			int n = sc.nextInt();
			int[] a = new int[8];
			for(int i = 0 ; i < 8 ; i++){
				a[i] = sc.nextInt();
			}
			int dem = 1;
			while(a[7] > 0){
				int tmp = a[0];
				tmp = tmp -dem;
				if(tmp < 0){
					tmp = 0;
				}
				dem++;
				if(dem > 5){
					dem = 1;
				}
				for(int i = 0 ; i < 7 ; i++){
					a[i] = a[i+1];
				}
				a[7] = tmp;
			}
			System.out.print("#"+t+" ");
			for(int i = 0 ; i < 8 ; i++){
				System.out.print(a[i] +" ");
			}
			System.out.println();
		}
	}

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

import java.util.Scanner;

public class SkyMap {
	static int t,n;
	static int[][] a = new int[n][n];
	static int[][] step = {{-1,0},{0,1},{1,0},{0,-1}};
	static int res = 0, max = 0, tmp = 0;
	public static void Try(int[][] a,int x , int y){
		a[x][y] = 0;
		for(int i = 0 ; i < 4 ; i++){
			int nx = x + step[i][0];
			int ny = y + step[i][1];
			if(nx >= 0 && nx < n && ny >=0 && ny < n && a[nx][ny] == 1){
				tmp++;
				Try(a,nx, ny);
			}
		}
	}
	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();
			a = new int[n][n];
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					if(a[i][j] == 1){
						res++;
						tmp = 1;
						Try(a,i, j);
						if(tmp > max){
							max = tmp;
						}
						tmp = 0;
					}
				}
			}
			
			System.out.println(res+" "+max);
			res = 0;
			max = 0;
		}
	}

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

import java.util.Scanner;

public class Stock {
	static int t,n;
	static int[] a = new int[n];
	
	public static boolean isBuy(int j){
		for(int i = j ; i < n ; i++){
			if(a[i] > a[j]){
				return true;
			}
		}
		return false;
	}
	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();
			a = new int[n];
			for(int i = 0 ; i < n ;i++){
				a[i] = sc.nextInt();
			}
			int res = 0,count = 0 , fee = 0;
			for(int i = 0 ; i < n ; i++){
				if(isBuy(i)){
					fee = fee + a[i];
					count++;
				}
				else{
					res = res + a[i]*count - fee;
					count = 0 ;
					fee = 0;
				}
			}
			System.out.println("#"+tc +" "+res);
		}
	}

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

import java.util.Scanner;

public class Sum {

	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;
			sc.nextInt();
			int[][] a = new int[100][100];
			for(int i = 0 ; i < 100 ; i++){
				for(int j = 0 ; j < 100 ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			int cheotrai = 0, cheophai = 0;
			for(int i = 0 ; i < 100 ; i++){
				int hang = 0, cot = 0;
				for(int j = 0 ; j < 100 ; j++){
					hang = hang+a[i][j];
					cot = cot +a[j][i];
					if(i == j){
						cheotrai = cheotrai +a[i][j];
					}
					if( i + j == 100){
						cheophai = cheophai +a[i][j];
					}
				}
				if(hang > res ){
					res = hang;
				}
				if(cot > res ){
					res = cot;
				}
			}
			if(cheophai > res ){
				res = cheophai;
			}
			if(cheotrai > res){
				res = cheotrai;
			}
			System.out.println("#"+(p+1)+" "+res);
		}
	}

}