Untitled
user_9638001
plain_text
2 years ago
194 kB
5
Indexable
//////////////////// 8 Queen
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static char number[];
static int visit[][];
static int T, exChange, leng, Anwser, value;
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
String cards = sc.next();
int exchange =sc.nextInt();
String c = sc.next();
exchange = sc.nextInt();
number = new char[c.length()];
visit = new int[11][1000000];
int maxValue = 1;
for (int i = 1; i <= leng; i++) {
maxValue *= 10;
}
for (int i = 0; i < exChange; i++) {
for (int j = 0; j < maxValue; j++) {
if (visit[i][j])
visit[i][j] = 0;
}
}
for (int i = 0; i < c.length(); i++) {
arr[i] = c.charAt(i);
ar[i] = Integer.parseInt(String.valueOf(arr[i]));
}
// for (int i = 0; i < c.length(); i++) {
// System.out.print(ar[i] +" ");
// }
System.out.println("Case #"+tc);
System.out.println(maxprize);
}
}
}
//////////////////// Assigning a meeting room
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static int stt[],st[],ft[];
static int T,N;
static int assMeeting(){
for (int i = 0; i < N-1; i++) {
for (int j = 0; j < N-i-1; j++) {
if (ft[j] > ft[j+1]) {
int temp = ft[j];
ft[j] = ft[j+1];
ft[j+1] = temp;
temp = st[j];
st[j] = st[j+1];
st[j+1] = temp;
}
}
}
// for (int i = 0; i < N; i++) {
// System.out.print(st[i] +" ");
// }
// System.out.println();
// for (int i = 0; i < N; i++) {
// System.out.print(ft[i] +" ");
// }
// System.out.println("--------");
int count = 1;
int lasttime = ft[0];
for (int i = 1; i < N; i++) {
// System.out.println("--------");
if (st[i] >= lasttime) {
count++;
lasttime = ft[i];
}
}
return count;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
stt = new int[N];
st = new int[N];
ft = new int[N];
for(int i = 0; i < N; i++) {
stt[i] = sc.nextInt();
st[i] = sc.nextInt();
ft[i] = sc.nextInt();
}
System.out.println("Case #"+tc);
System.out.println(assMeeting());
}
}
}
///////////////////// Backtracking nhi phan
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
public static void generate(int arr[],int index,int n){
if (index == n) {
for (int num : arr) {
System.out.print(num+" ");
}
System.out.println();
return;
}
arr[index] = 0;
generate(arr, index+1,n);
arr[index] = 1;
generate(arr, index+1,n);
}
public static void main(String[] args) throws FileNotFoundException {
// System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
int T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
int n = sc.nextInt();
int[] arr = new int[n];
generate(arr, 0,n);
}
}
}
//////////////////// Ban bong bay
import java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static int getmaxscore(int arr[], int l, int r, int n) {
int result = 0;
for (int i = l + 1; i < r; i++) {
int temp = getmaxscore(arr, l, i, n) + getmaxscore(arr, i, r, n);
if (l == 0 && r == n)
temp += arr[i];
else
temp += (arr[l] * arr[r]);
if (temp > result)
result = temp;
}
return result;
}
public static void main(String args[]) throws Exception {
Scanner scanner = new Scanner(System.in);
int testCase = scanner.nextInt();
for (int a = 1; a <= testCase; a++) {
int n = scanner.nextInt();
int arr[] = new int[n + 2];
arr[0] = 1;
arr[n + 1] = 1;
for (int i = 1; i < n + 1; i++) {
arr[i] = scanner.nextInt();
}
System.out.println("Case #" + a);
System.out.println(getmaxscore(arr, 0, n + 1, n + 1));
}
}
}
/////////////////////// Bao ve nong trang (dem so dinh)
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int T, N,M;
static int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
static int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rqueue = new Queue();
static Queue cqueue = new Queue();
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
M = sc.nextInt();
int [][]graph = new int[N][M];
boolean [][]visited = new boolean[N][graph[0].length];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
graph[i][j] = sc.nextInt();
visited[i][j] = false;
}
}
int count = 0;
int flag;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visited[i][j] == false) {
rqueue.reset();
cqueue.reset();
rqueue.enQueue(i);
cqueue.enQueue(j);
visited[i][j] = true;
flag = 0;
while (!rqueue.isEmpty()) {
int x = rqueue.deQueue();
int y = cqueue.deQueue();
for (int j2 = 0; j2 < 8; j2++) {
int newR = x + dx[j2];
int newC = y + dy[j2];
if (newR >= 0 && newR < N && newC >= 0 && newC < M) {
if (graph[newR][newC] > graph[x][y]) {
flag = 1;
}
if (graph[newR][newC] == graph[x][y] && visited[newR][newC] == false) {
rqueue.enQueue(newR);
cqueue.enQueue(newC);
visited[newR][newC] = true;
}
}
}
}
if (flag == 0) {
count++;
}
}
}
}
System.out.println("#"+tc+" "+count);
}
}
}
///////////////////// Battle City
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import javax.xml.crypto.dsig.spec.XSLTTransformParameterSpec;
public class Main {
static int dx[] = {0,0,1,-1};
static int dy[] = {1,-1,0,0};
static int T, N, M;
static char arr[][];
static int posX[];
static int posY[];
static int visited[][];
static int check[];
static int init[][];
int cnt;
static char map[][];
static int k;
static int ans, minA;
static int startx, starty, endx, endy;
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[10000000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rqueue = new Queue();
static Queue cqueue = new Queue();
static void BFS(int x, int y){
while (!rqueue.isEmpty()) {
int cr = rqueue.deQueue();
int cc = cqueue.deQueue();
for (int k = 0; k < 4; k++) {
int nr = cr + dx[k];
int nc = cc + dy[k];
if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0){
if(arr[nr][nc] == 'B'){
visited[nr][nc] = visited[cr][cc] + 2;
}
if(arr[nr][nc] == 'E' || arr[nr][nc] == 'T'){
visited[nr][nc] = visited[cr][cc] + 1;
}
rqueue.enQueue(nr);
cqueue.enQueue(nc);
}else if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] > 0){
if(arr[nr][nc] == 'B'){
if(visited[nr][nc] > visited[cr][cc] + 2){
visited[nr][nc] = visited[cr][cc] + 2;
rqueue.enQueue(nr);
cqueue.enQueue(nc);
}
}
if(arr[nr][nc] == 'E' || arr[nr][nc] == 'T'){
if(visited[nr][nc] > visited[cr][cc] + 1){
visited[nr][nc] = visited[cr][cc] + 1;
rqueue.enQueue(nr);
cqueue.enQueue(nc);
}
}
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // number of test cases
for (int t = 1; t <= T; t++) {
N = sc.nextInt(); // number of rows
M = sc.nextInt(); // number of columns
arr = new char[N][M];
visited = new int[N][M];
for (int i = 0; i < N; i++) {
String c = sc.next();
for (int j = 0; j < M; j++) {
arr[i][j] = c.charAt(j);
if (arr[i][j] == 'Y') {
startx = i;
starty = j;
visited[startx][starty] = 1;
}
if (arr[i][j] == 'T') {
endx = i;
endy = j;
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(arr[i][j] == 'S' || arr[i][j] == 'R'){
visited[i][j] = -1;
}
}
}
rqueue.reset();
cqueue.reset();
rqueue.enQueue(startx);
cqueue.enQueue(starty);
BFS(startx,starty);
System.out.println("Case #"+t);
System.out.println(visited[endx][endy]-1);
}
}
}
/////////////////////// Calculator 3
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
private static class Stack {
private char[] elements;
private int top;
public Stack(int size) {
elements = new char[size];
top = -1;
}
public void push(char element) {
elements[++top] = element;
}
public char pop() {
return elements[top--];
}
public boolean isEmpty() {
return top == -1;
}
public char peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return elements[top];
}
}
private static class Stack1{
private int[] elements;
private int top;
public Stack1(int size) {
elements = new int[size];
top = -1;
}
public void push(int element) {
elements[++top] = element;
}
public int pop() {
return elements[top--];
}
public boolean isEmpty() {
return top == -1;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return elements[top];
}
}
private static int priority(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return 0;
}
}
public static String infixToPostfix(String expression){
Stack stack = new Stack(expression.length());
StringBuilder output = new StringBuilder();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (Character.isDigit(c)) {
output.append(c);
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (stack.peek() != '(') {
output.append(stack.pop());
}
stack.pop();
} else {
while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
output.append(stack.pop());
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
output.append(stack.pop());
}
return output.toString();
}
static int evaluatePostfix(String exp){
//create a stack
Stack1 stack = new Stack1(exp.length());
// Scan all characters one by one
for(int i=0;i<exp.length();i++)
{
char c=exp.charAt(i);
// If the scanned character is an operand (number here),
// push it to the stack.
if(Character.isDigit(c))
stack.push(c - '0');
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = stack.pop();
int val2 = stack.pop();
switch(c)
{
case '+':
stack.push(val2+val1);
break;
case '-':
stack.push(val2- val1);
break;
case '/':
stack.push(val2/val1);
break;
case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
for (int tc = 1; tc <=10; tc++) {
int n = sc.nextInt();
String expression = sc.nextLine();
expression = sc.nextLine();
String s = infixToPostfix(expression);
System.out.println("#"+tc+" "+evaluatePostfix(s));
}
}
}
////////////////Capture Knight (Quan ma di chuyen)
import java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static int dx[] = {-2,-2,-1,1,2,2,1,-1};
static int dy[] = {-1,1,2,2,1,-1,-2,-2};
static int arr[][];
static int map[][];
static int T, N, M, R,C,S,K;
static boolean visited[][];
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000005];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rQueue = new Queue();
static Queue cQueue = new Queue();
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
M = sc.nextInt();
R = sc.nextInt();
C = sc.nextInt();
S = sc.nextInt();
K = sc.nextInt();
R--;
C--;
S--;
K--;
arr = new int[N][M];
visited = new boolean[N][M];
rQueue.reset();
cQueue.reset();
rQueue.enQueue(R);
cQueue.enQueue(C);
boolean check = false;
while (!rQueue.isEmpty()) {
int cr = rQueue.deQueue();
int cc = cQueue.deQueue();
for (int i = 0; i < 8; i++) {
int nr = cr + dx[i];
int nc = cc + dy[i];
if (nr == S && nc == K) {
check = true;
arr[nr][nc] = arr[cr][cc] + 1;
break;
}else if(nr >= 0 && nr < N && nc >= 0 && nc < M && arr[nr][nc] == 0){
arr[nr][nc] = arr[cr][cc] + 1;
rQueue.enQueue(nr);
cQueue.enQueue(nc);
}
}
if (check == true) {
break;
}
}
int res = arr[S][K];
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
System.out.println("Case #"+tc);
System.out.println(arr[S][K]);
}
}
}
//////////////////// Chess rook (quan xe)
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int n;
static char[][] a;
static int T, count,ans;
public static boolean check(int r, int c){
if (a[r][c] == 'X') {
return false;
}
for (int i = r; i >= 0; i--) {
if (a[i][c] == 'X') {
break;
}
if (a[i][c] == '2') {
return false;
}
}
for (int i = c; i >= 0; i--) {
if (a[r][i] == 'X') {
break;
}
if (a[r][i] == '2') {
return false;
}
}
return true;
}
public static void backtrack(int k){
if (k == n * n) {
if (count > ans) {
ans = count;
}
return;
}
int r = k/n;
int c = k%n;
if (check(r,c) && a[r][c] == '.') {
count++;
a[r][c] = '2';
backtrack(k+1);
count--;
a[r][c] = '.';
}
backtrack(k+1);
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// System.out.print(a[i][j]+" ");
// }
// System.out.println();
// }System.out.println("============");
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
int T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
n = sc.nextInt();
a = new char[n][n];
for (int i = 0; i < n; i++) {
String c = sc.next();
for (int j = 0; j < n; j++) {
a[i][j] = c.charAt(j);
}
}
ans =0;
count = 0;
backtrack(0);
System.out.println("Case #"+tc);
System.out.println(ans);
}
}
}
//////////////////////////////// Cleaning Robot
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int dx[] = {0,0,1,-1};
static int dy[] = {1,-1,0,0};
static int T, N, M;
static int arr[][];
static int posX[];
static int posY[];
static int visited[][];
static int check[];
static int init[][];
int cnt;
static int map[][];
static int k;
static int ans, minA;
static int x, y;
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rqueue = new Queue();
static Queue cqueue = new Queue();
public static void backtrack(int n, int tmp){
if(ans >= minA){
return;
}
if(tmp == k){
if(ans < minA)
minA = ans;
return;
}
for(int i = 1; i < k; i++){
if(map[n][i] != 0 && check[i] == 0 ){
ans += map[n][i];
check[i] = 1;
backtrack(i, tmp + 1);
ans -= map[n][i];
check[i] = 0;
}
}
}
static void BFS(int x, int y){
int a = posX[x];
int b = posY[x];
int c = posX[y];
int d = posY[y];
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
visited[i][j] = 0;
init[i][j] = arr[i][j];
}
}
rqueue.reset();
cqueue.reset();
init[a][b] = 0;
visited[a][b] = 1;
rqueue.enQueue(a);
cqueue.enQueue(b);
int flag;
while(rqueue.isEmpty() == false){
flag = 0;
int x1 = rqueue.deQueue();
int y1 = cqueue.deQueue();
for(int i = 0; i < 4; i++){
int row = x1 + dx[i];
int col = y1 + dy[i];
if(row >= 0 && row < N && col >= 0 && col < M && visited[row][col] == 0 && init[row][col] != 2){
if(row == c && col == d){
init[row][col] = init[x1][y1] + 1;
map[x][y] = init[row][col];
map[y][x] = init[row][col];
flag = 1;
break;
}else{
init[row][col] = init[x1][y1] + 1;
visited[row][col] = 1;
rqueue.enQueue(row);
cqueue.enQueue(col);
}
}
if(flag == 1){
break;
}
}
if(flag == 1){
break;
}
}
if(init[c][d] == -1 || init[c][d] == -3){
map[x][y] = 0;
map[y][x] = 0;
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt(); // number of test cases
for (int t = 1; t <= T; t++) {
N = scanner.nextInt(); // number of rows
M = scanner.nextInt(); // number of columns
arr = new int[N][M]; // room layout
visited = new int[105][105];
check = new int[11];
init = new int[105][105];
map = new int[11][11];
posX = new int[11];
posY = new int[11];
// Read room layout
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
arr[i][j] = scanner.nextInt();
if (arr[i][j] == 3) {
x = i;
y = j;
arr[i][j] = -3;
}
}
}
posX[0] = x;
posY[0] = y;
k = 1;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(arr[i][j] == 1){
arr[i][j] = -1;
posX[k] = i;
posY[k] = j;
k++;
}
}
}
for(int i = 0; i < k - 1; i++){
for(int j = i + 1; j < k; j++){
BFS(i, j);
}
}
for(int i = 0; i < k; i++){
check[i] = 0;
}
ans = 0;
minA = 1000000;
backtrack(0, 1);
System.out.println("Case #" + t);
if (minA == 1000000) {
System.out.println("-1");
}else
System.out.println(minA);
}
}
}
//////////////////////// Connect Processor
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
public class Main {
static int t,n,core,re,count;
static int[][] a;
static int[][] cores;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,1,-1};
public static void fun(int cnt, int sum,int cntScore){
if(cnt == n){
System.out.println("cnt" + cnt +" cntScore:" + cntScore);
print();
if(cntScore> count){
count = cntScore;
re = sum;
}else if(cntScore == count){
if(sum < re){
re = sum;
}
}
return;
}
int i = cores[0][cnt];
int j = cores[1][cnt];
System.out.println("cnt" + cnt +" cntScore:" + cntScore);
int[] tem = check(i,j);
if(tem != null){
int dem = 0;
for (int k = 0; k < tem.length; k++) {
if(tem[k] != 0){
dem++;
int points = visited(i, j, k);
fun(cnt+1, sum + points,cntScore+1);
unvisited(i, j, k);
}
}
if(dem == 0){
fun(cnt + 1, sum, cntScore);
}
}else{
fun(cnt + 1, sum, cntScore + 1);
}
}
public static int[] check(int i,int j){
if(i == 0 || i == n-1 || j == 0 || j == n-1){
return null;
}
int [] arr = new int [4];
arr[0] = i - 0;
arr[1] = j - 0;
arr[2] = n - 1 - i;
arr[3] = n - 1 - j;
int cnt = 4;
for (int k = 0; k < n; k++) {
if(cores[0][k] != i || cores[1][k] != j){
if(arr[3] != 0 && cores[0][k] == i && cores[1][k] > j){
arr[3] = 0;
cnt--;
}else if(arr[1] != 0 &&cores[0][k] == i && cores[1][k] < j){
cnt--;
arr[1] = 0;
}else if(arr[2] != 0 &&cores[1][k] == j && cores[0][k] > i){
cnt--;
arr[2] = 0;
}else if(arr[0] != 0 &&cores[1][k] == j && cores[0][k] < i){
cnt--;
arr[0] = 0;
}
}
}
if(cnt != 0){
for (int l = 0; l < arr.length; l++) {
if(arr[l] != 0){
if(l == 0){
for (int k = 0; k < i; k++) {
if(a[k][j] == 2){
arr[l] = 0;
cnt --;
break;
}
}
}else if(l == 1){
for (int k = 0; k < j; k++) {
if(a[i][k] == 2){
arr[l] = 0;
cnt --;
break;
}
}
}else if(l == 2){
for (int k = i+1; k < n; k++) {
if(a[k][j] == 2){
arr[l] = 0;
cnt --;
break;
}
}
}else if(l == 3){
for (int k = j+1; k < n; k++) {
if(a[i][k] == 2){
arr[l] = 0;
cnt --;
break;
}
}
}
}
}
}
return arr;
}
static int visited(int i, int j, int d){
int start,end;
if(d == 0){
for (int k = 0; k < i; k++) {
a[k][j] = 2;
}
return i;
}else if(d == 1){
for (int k = 0; k < j; k++) {
a[i][k] = 2;
}
return j;
}else if(d == 2){
for (int k = i+1; k < n; k++) {
a[k][j] = 2;
}
return n-1-i;
}else {
for (int k = j+1; k < n; k++) {
a[i][k] = 2;
}
return n-1-j;
}
}
static void unvisited(int i, int j, int d){
int start,end;
if(d == 0){
for (int k = 0; k < i; k++) {
a[k][j] = 0;
}
}else if(d == 1){
for (int k = 0; k < j; k++) {
a[i][k] = 0;
}
}else if(d == 2){
for (int k = i+1; k < n; k++) {
a[k][j] = 0;
}
}else if(d == 3){
for (int k = j+1; k < n; k++) {
a[i][k] = 0;
}
}
}
static void print(){
System.out.println("a:");
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int i = 0; i < t; i++) {
count = 0;
re = 150;
core = 0;
n = sc.nextInt();
a = new int[n][n];
cores = new int[2][n];
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
a[j][k] = sc.nextInt();
if(a[j][k] == 1){
cores[0][core] = j;
cores[1][core++] = k;
}
}
}
System.out.print("#" + (i+1) + " ");
fun(0, 0,0);
System.out.println(re);
// System.out.println(count);
// print();
//
// System.out.println(visited(5, 1, 3));
// print();
// int[] tem = check(1, 2);
// for (int j = 0; j < tem.length; j++) {
// System.out.print(tem[j] + " ");
//
// }
// System.out.println();
//System.out.println(check(1, 2));
}
}
}
/////////////////// Contact
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
public void display() {
int i;
if (isEmpty()) {
System.out.println("Empty Queue");
}
else {
// display the front of the queue
System.out.println("\nFront index-> " + front);
// display element of the queue
System.out.println("Items -> ");
for (i = front; i <= rear; i++)
System.out.print(Data[i] + " ");
// display the rear of the queue
System.out.println("\nRear index-> " + rear);
int s = rear - front;
System.out.println("rear"+ rear);
System.out.println("front"+ front);
}
}
}
static int a[][];
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
for (int tc = 1; tc <=10; tc++) {
int n = sc.nextInt();
int start = sc.nextInt();
int map[][] = new int[n][2];
boolean visited[] = new boolean[101];
Queue mQueue = new Queue();
for (int i = 0; i < n/2; i++) {
map[i][0] = sc.nextInt();
map[i][1] = sc.nextInt();
}
for (int i = 0; i < 100; i++) {
visited[i] = false;
}
mQueue.enQueue(start);
// mQueue.display();
// System.out.println(mQueue.isEmpty());
visited[start] = true;
int ans = start;
while (mQueue.isEmpty() == false) {
int res = 0;
int queusize = mQueue.rear - mQueue.front;
// System.out.println(queusize);
for (int i = 0; i < queusize; i++) {
int cpoint = mQueue.deQueue();
// System.out.println(res+" "+cpoint);
res = res > cpoint ? res : cpoint;
// System.out.println(res);
// System.out.println("---------------- ");
for (int j = 0; j < n/2; j++) {
if (cpoint == map[j][0] && visited[map[j][1]] == false) {
mQueue.enQueue(map[j][1]);
visited[map[j][1]] = true;
}
}
}
if (res != 0) {
ans = res;
}
}
System.out.println("#"+tc+" "+ans);
//
}
}
}
//////////////// Cover rectangle with dominos
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int arr[][];
static int N = 7, M = 8;
static int T;
static int cnt;
static int visited[][];
static int X[] = {0, 1};
static int Y[] = {1, 0};
static int check[][];
static int tmp;
public static void backtrack(int k){
if(k == 56){
cnt++;
return;
}
int x = k / 8;
int y = k % 8;
int a = arr[x][y];
if(check[x][y] == 0){
for(int i = 0; i < 2; i++){
int row = x + X[i];
int col = y + Y[i];
if(row >= 0 && row < N && col >= 0 && col < M && check[row][col] == 0){
int b = arr[row][col];
if(visited[a][b] == 0){
check[row][col] = 1;
visited[a][b] = 1;
visited[b][a] = 1;
backtrack(k + 1);
check[row][col] = 0;
visited[a][b] = 0;
visited[b][a] = 0;
}
}
}
}
else{
backtrack(k + 1);
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
T = sc.nextInt(); // number of test cases
for (int t = 1; t <= T; t++) {
arr = new int[8][9];
visited = new int[8][9];
check = new int[7][8];
cnt = 0;
tmp = 0;
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 8; j++) {
arr[i][j] = sc.nextInt();
}
}
backtrack(0);
System.out.println("Case #" + t);
// if (minA == 1000000) {
// System.out.println("-1");
// }else
System.out.println(cnt);
}
}
}
/////////////////////// Crazy King
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import javax.xml.crypto.dsig.spec.XSLTTransformParameterSpec;
public class Main {
static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
static int dxK[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
static int dyK[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
static int T, N, M;
static char arr[][];
static int posX[];
static int posY[];
static int visited[][];
static int check[];
static int init[][];
int cnt;
static char map[][];
static int k;
static int ans, minA;
static int startx, starty, endx, endy;
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rqueue = new Queue();
static Queue cqueue = new Queue();
static int BFS(int x, int y){
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
visited[i][j] = 0;
}
}
while (!rqueue.isEmpty()) {
int curX = rqueue.deQueue();
int curY = cqueue.deQueue();
for (int k = 0; k < 8; k++) {
int newX = curX + dxK[k];
int newY = curY + dyK[k];
if (newX >= 0 && newY >=0 && newX < N && newY < M && map[newX][newY] != 'Z' &&visited[newX][newY] == 0 ) {
rqueue.enQueue(newX);
cqueue.enQueue(newY);
visited[newX][newY] = visited[curX][curY] + 1;
if (newX == endx && newY == endy) {
return visited[newX][newY];
}
}
}
}
return -1;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // number of test cases
for (int t = 1; t <= T; t++) {
M = sc.nextInt(); // number of rows
N = sc.nextInt(); // number of columns
map = new char[N][M];
visited = new int[N][M];
arr = new char[N][M];
for (int i = 0; i < N; i++) {
String c = sc.next();
for (int j = 0; j < M; j++) {
map[i][j] = c.charAt(j);
arr[i][j] = c.charAt(j);
if (map[i][j] == 'A') {
startx = i;
starty = j;
}
if (map[i][j] == 'B') {
endx = i;
endy = j;
}
}
}
rqueue.reset();
cqueue.reset();
rqueue.enQueue(startx);
cqueue.enQueue(starty);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] == 'Z') {
for (int k = 0; k < 8; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
if (newX >= 0 && newY >=0 && newX < N && newY < M && map[newX][newY] == '.') {
map[newX][newY] = 'Z';
}
}
}
}
}
System.out.println(BFS(startx, startx));
}
}
}
///////////////////// Crytogram
import java.util.Scanner;
public class Solution {
static int N;
static int[] Num;
public static void main(String args[]) throws Exception {
Scanner sc =new Scanner(System.in);
for (int tc = 1; tc <= 10; tc++) {
int n = sc.nextInt();
int a[] = new int[10000];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int m = sc.nextInt();
for (int i = 0; i < m; i++) {
char c = sc.next().charAt(0);
int x = sc.nextInt();
int y = sc.nextInt();
int b[] = new int[y];
for (int j = 0; j < y; j++) {
b[j] = sc.nextInt();
}
for (int j = n-1; j >= x; j--) {
a[j+y] = a[j];
}
// System.out.print(c+" "+x+" "+y+" ");
for (int number : b) {
a[x++] = number;
}
// System.out.println();
}
System.out.print("#"+tc+" ");
for (int i = 0; i < 10; i++) {
System.out.print(a[i] +" ");
}
System.out.println();
}
}
}
////////////////// Crytogram 3
import java.util.Scanner;
public class Solution {
static int N;
static int[] Num;
public static int[] removeTheElement(int[] arr, int index)
{
if (arr == null || index < 0
|| index >= arr.length) {
return arr;
}
int[] anotherArray = new int[arr.length - 1];
for (int i = 0, k = 0; i < arr.length; i++) {
if (i == index) {
continue;
}
anotherArray[k++] = arr[i];
}
return anotherArray;
}
public static void main(String args[]) throws Exception {
Scanner sc =new Scanner(System.in);
Character c1 = 'I';
Character c2 = 'D';
Character c3 = 'A';
for (int tc = 1; tc <= 10; tc++) {
int n = sc.nextInt();
int a[] = new int[10000];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int m = sc.nextInt();
for (int i = 0; i < m; i++) {
Character c = sc.next().charAt(0);
if (c.equals(c1)) {
int x = sc.nextInt();
int y = sc.nextInt();
int b[] = new int[y];
for (int j = 0; j < y; j++) {
b[j] = sc.nextInt();
}
for (int j = n-1; j >= x; j--) {
a[j+y] = a[j];
}
// System.out.print(c+" "+x+" "+y+" ");
for (int number : b) {
a[x++] = number;
}
// System.out.println();
}
if(c.equals(c2)){
int x = sc.nextInt();
int y = sc.nextInt();
for (int j = 0; j < y; j++) {
a = removeTheElement(a, x+1);
n--;
}
}
if (c.equals(c3)){
int y = sc.nextInt();
int add[] = new int[y];
for (int j = 0; j < y; j++) {
add[j] = sc.nextInt();
a[n] = add[j];
n++;
}
}
}
System.out.print("#"+tc+" ");
for (int i = 0; i < 10; i++) {
System.out.print(a[i] +" ");
}
System.out.println();
}
}
}
/////////////////// Cutting a piece of colored paper
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
using namespace std;
#include <conio.h>
int blue, white;
int a[1000][1000];
int N;
bool isWhite (int x, int y, int n){
for(int i = x; i< x + n; i++){
for(int j = y; j< y+n; j++){
if (a[i][j]!=0){
return false;
}
}
}
return true;
}
bool isBlue (int x, int y, int n){
for(int i = x; i< x + n; i++){
for(int j = y; j< y+n; j++){
if (a[i][j]!=1){
return false;
}
}
}
return true;
}
void cut(int x, int y, int n){
//Stop
//if (n==0){
// return;
//}
if (isWhite(x,y,n)){
white++;
}
else if (isBlue(x,y,n)){
blue++;
}
else { // De quy
cut(x, y, n/2);
cut(x, y+n/2, n/2);
cut(x+n/2, y, n/2);
cut(x+n/2, y+n/2, n/2);
}
}
int main(void)
{
int test_case;
int T;
//int Answer;
freopen("input.txt", "r", stdin);
/*
If you remove the statement below, your program's output may not be recorded
when your program is aborted due to the time limit.
For safety, please use setbuf(stdout, NULL); statement.
*/
setbuf(stdout, NULL);
scanf("%d", &T);
/*
Read each test case from standard input.
*/
for (test_case = 1; test_case <= T; ++test_case)
{
//Answer = 0;
cin >> N;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cin >> a[i][j];
}
}
blue = 0;
white = 0;
cut(0,0,N);
/////////////////////////////////////////////////////////////////////////////////////////////
// Print the answer to standard output(screen).
cout << "Case #" << test_case << endl;
cout << white << " " << blue << endl;
}
_getch();
//while(1);
return 0; //Your program should return 0 on normal termination.
}
C2:////
#include<iostream>
using namespace std;
int a[129][129] ={0};
int N,W,B;
int checkMau(int hang, int cot, int n)
{
for(int i = 0; i< n; i++)
for(int j = 0; j<n; j++)
if(a[hang+i][cot+j] != a[hang][cot])
return 2;
return a[hang][cot];
}
void cat(int hang, int cot, int n)
{
int st = checkMau(hang,cot,n);
if(st==2)
{
cat(hang,cot,n/2);
cat(hang,cot+n/2,n/2);
cat(hang+n/2,cot,n/2);
cat(hang+n/2,cot+n/2,n/2);
}
else
{
if(st==0) W++;
else B++;
}
}
int main()
{
int T;
freopen("input.txt","r",stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++)
{
cin >> N;
for(int i = 0; i< 129; i++)
for(int j = 0; j< 129; j++)
a[i][j] = 0;
for(int i = 0; i< N; i++)
for(int j = 0; j< N; j++)
cin>>a[i][j] ;
W=0;B=0;
cat(0,0,N);
cout <<"Case #"<< tc<< endl<<W<<" "<< B<<endl;
}
return 0;
}
/////////////// Di an cuoi
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
public class Main {
static int T, n,m,kq,sum;
static int[][] a;
static int[] vis;
static int[] dem;
public static void backtrack(int k){
if(vis[2]!=1&&vis[k]==2) return;
if(vis[1]!=2&&vis[k]==3) return;
if(vis[1]>=2&&vis[2]==1){
if(kq>sum) kq=sum;
return;
}
if(sum>=kq) return;
for(int i=0; i<dem[k]; i++){
vis[a[k][i]]++;
if(vis[a[k][i]]==1) sum++;
backtrack(a[k][i]);
vis[a[k][i]]--;
if(vis[a[k][i]]==0) sum--;
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
int src, des;
for (int tc = 1; tc <= T; tc++) {
n = sc.nextInt();
m = sc.nextInt();
a = new int[21][20];
vis = new int[21];
dem = new int[21];
for(int i=0; i<n; i++){
dem[i]=0;
vis[i]=0;
}
// read map
int x,y;
for (int i = 0; i < m; i++) {
x = sc.nextInt();
y = sc.nextInt();
a[x][dem[x]]=y;
dem[x]++;
}
kq=10000;
sum=0;
vis[1]=1;
backtrack(1);
System.out.println(kq +1);
}
}
}
////////////////// Di chuyen bo
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
// TODO Auto-generated method stub
for (int tc = 1; tc <= T; tc++) {
int m = sc.nextInt();
int n = sc.nextInt();
int a[] = new int[n];
int max = 0;
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (int i = 0; i < (1 << n); i++) {
System.out.println(i);
int sum = 0;
for (int j = 0; j < n; j++) {
if ((i &(1 << j)) != 0) {
sum += a[j];
}
System.out.println("sum: "+sum+" j: "+j);
}
if (sum <= m && sum > max) {
max = sum;
}
}
System.out.println("#"+tc+" "+max);
}
}
}
//////C2
#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
int tc = 1;
while (t--){
int m, n;
cin >> m >> n;
int w[20];
for (int i = 1; i <= n; i++){
cin >> w[i];
}
bool possible[3000][16] = {false};
possible[0][0] = true;
for (int k = 1; k <= n; k++){
for (int x = 0; x <= m; x++){
if (x - w[k] >= 0){
possible[x][k] |= possible[x - w[k]][k - 1];
};
possible[x][k] |= possible[x][k - 1];
};
};
int res = 0;
for (int x = m; x >= 0; x--){
if (possible[x][n]){
res = x;
break;
};
}
printf("#%d %d\n", tc, res);
tc++;
};
return 0;
}
////////////////////// Diamond
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static int T,N;
static int arr[][];
static int cnt[];
static int visited[];
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000001];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue mQueue = new Queue();
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
// TODO Auto-generated method stub
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
arr = new int[1001][1001];
cnt = new int[1001];
visited = new int[1001];
for (int i = 1; i <= N; i++) {
cnt[i] = sc.nextInt();
for (int j = 0; j < cnt[i]; j++) {
arr[i][j] = sc.nextInt();
}
}
int ans = 0;
for (int i = 1; i <= N; i++) {
mQueue.reset();
for(int k = 1; k<= N; k++){
visited[k] = 0;
}
if(cnt[i] >= 2 && visited[i] == 0){
mQueue.enQueue(i);
visited[i]++;
while(mQueue.isEmpty() == false){
int tmp = mQueue.deQueue();
for(int j = 0; j < cnt[tmp]; j++){
mQueue.enQueue(arr[tmp][j]);
visited[arr[tmp][j]]++;
if(visited[arr[tmp][j]] >= 2){
ans = 1;
break;
}
}
if(ans == 1){
break;
}
}
}
}
System.out.println("Case #"+tc);
if (ans == 1) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
}
//////////////// Duong di ngan nhat noi cac dinh cua do thi
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int T, N,M;
public static int minDistance(int[] dist, boolean[] visited){
int minDist = Integer.MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < N; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
minIndex = i;
}
}
return minIndex;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
int [][]arr = new int[N][N];
boolean []visited = new boolean[N];
int dist[] = new int[N];
int parent[] = new int[N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
arr[i][j] = sc.nextInt();
}
visited[i] = false;
dist[i] = Integer.MAX_VALUE;
}
dist[0] = 0;
parent[0] = -1;
for (int i = 0; i < N-1; i++) {
int u = minDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < N; v++) {
if (!visited[v] && arr[u][v] >= 0 && arr[u][v] < dist[v]) {
parent[v] = u;
dist[v] = arr[u][v];
}
}
}
int ans = 0;
for (int i = 1; i < N; i++) {
// System.out.print(dist[i]+" ");
ans += dist[i];
}
// System.out.println();
System.out.println("Case #"+tc);
System.out.println(ans);
}
}
}
///////////// Earning Biggest prize money 2
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int T, exChange, leng, Anwser, value;
char number[10];
int visit[11][1000000];
void doChange(int ex, char* num) {
value = 0;
for (int l = 0; l< leng; l++) value = value * 10 + num[l] - 48;
if (visit[ex][value] == 1) {
return;
}
visit[ex][value] = 1;
char temp[10], c;
if (ex == exChange) {
Anwser = value > Anwser ? value : Anwser;
} else {
for (int i = 0; i < leng; i++) {
for (int j = i + 1; j < leng; j++) {
for (int l = 0; l < leng; l++) {
temp[l] = num[l];
}
c = temp[i];
temp[i] = temp[j];
temp[j] = c;
/*for (int l = 0; l < leng; l++) {
cout<<temp[l];
}
cout << endl;*/
doChange(ex+1, temp);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> number;
cin >> exChange;
leng = 0;
while (number[leng] != '\0') {
leng++;
}
int maxValue = 1;
for (int i = 1; i <= leng; i++) {
maxValue *= 10;
}
for (int i = 0; i < exChange; i++) {
for (int j = 0; j < maxValue; j++) {
if (visit[i][j])
visit[i][j] = 0;
}
}
Anwser = 0;
doChange(0, number);
cout << "Case #" << tc << endl;
cout << Anwser << endl;
}
while(1);
return 0;
}
// by C
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful.
//#include <stdio.h>
//int compose(char *a, int n) {
// int x = 0;
// int j = 1;
// int i;
// for (i = n-1; i >= 0; i--) {
// x = x + (a[i]-'0')*j;
// j = j*10;
// }
// return x;
//}
//int main(void)
//{
// int answer=0;
// int tc, T = 10;
// int x;
// int digit;
// int swit;
// int temp;
// //freopen("input.txt", "r", stdin);
// setbuf(stdout, NULL);
// scanf("%d", &T);
// for(tc = 0; tc < T; tc++)
// {
// int bb[11][10000];
// char arr[10];
// char a[10];
// int n = 0;
// int N = 0;
// answer = 0;
// int i,j,k,k2,m,l;
// scanf("%s%d", &arr, &swit);
// for (i = 0; i < 10; i++) {
// if(arr[i] >= '0' && arr[i] <= '9')
// N++;
// else if(arr[i] == '\0')
// break;
// }
//
//
// for(i = 0; i < 11; i++)
// for (j = 0; j < 10000; j++)
// bb[i][j] = -1;
// int flag = 0;
// m = 0, k=0,k2 = 0;
// bb[m][k] = compose(arr,N);
// for (i = 1; i <= swit; i++) {
// k = k2;
// k2 = 0;
// for (j = 0; j <=k; j++) {
// n = N-1;
// while ((bb[m][j]%10) > 0 || (bb[m][j]/10) > 0) {
// arr[n--] = (char)(bb[m][j] % 10 + 48);
// bb[m][j] = bb[m][j]/10;
// }
// if(n != -1)
// {
// for(l = 0; l <= n; l++)
// arr[l] = '0';
// }
// int u,v;
// for (u = 0; u < (N-1); u++)
// for (v = (u+1); v < N; v++) {
// for ( l = 0; l < N; l++)
// a[l] = arr[l];
// temp = a[v];
// a[v] = a[u];
// a[u] = temp;
// temp = compose(a,N);
// flag = 0;
// int z;
// for (z = 0; z < k2; z++)
// if (bb[m+1][z] == temp) {
// flag = 1;
// break;
// }
// if (flag == 0)
// bb[m+1][k2++] = temp;
// }
// }
// m++;
//
// }
//
// for (i = 0; i < k2; i++)
// if (answer < bb[m][i])
// answer = bb[m][i];
// // Print the answer to standard output(screen).
// printf("Case #%d\n", tc+1);
// printf("%d\n", answer);
// }
// return 0;//Your program should return 0 on normal termination.
//}
//
//Pham Van Phu
//#include<iostream>
//using namespace std;
//int T, exChange, leng, maxValue;
//char numberArr[9];
//int visit[11][1000009];
//
//void doChange(int ex, char* numArr) {
// int value = 0;
// for (int l = 0; l < leng; l++) {
// value = value * 10 + numArr[l] - 48;
// }
//
// if (ex == 0) {
// if (value > maxValue) {
// maxValue = value;
// }
// //cout << "Max Value: " << maxValue << endl;
// }
// else {
// char c, numTemp[9];
// for (int i = 0; i < leng - 1; i++) {
// for (int j = i + 1; j < leng; j++) {
// if (i != j) {
// for (int n = 0; n < leng; n++) {
// numTemp[n] = numArr[n];
// }
//
// c = numTemp[i];
// numTemp[i] = numTemp[j];
// numTemp[j] = c;
//
// /*for (int k = 0; k < leng; k++) {
// cout << numTemp[k];
// }
// cout << " " << ex << endl;*/
//
// value = 0;
// for (int l = 0; l < leng; l++) {
// value = value * 10 + numTemp[l] - 48;
// }
// if (visit[ex][value] == 0) {
// visit[ex][value] = 1;
// doChange(ex - 1, numTemp);
// }
//
//
// }
// }
// }
// }
//}
//
//int main() {
// ios::sync_with_stdio(false);
// //freopen("input.txt", "r", stdin);
// //freopen("output.txt", "w", stdout);
// cin >> T;
// for (int tc = 1; tc <= T; tc++) {
// cin >> numberArr;
// cin >> exChange;
//
// leng = 0;
// while (numberArr[leng] != '\0') {
// leng++;
// }
// maxValue = -1;
//
// int maxReset = 1;
// for (int i = 0; i < leng; i++) {
// maxReset = maxReset * 10;
// }
//
// for (int i = 0; i < exChange; i++) {
// for (int j = 0; j < maxReset; j++) {
// visit[i][j] = 0;
// }
// }
// /*char c, numTemp[9];
// for (int i = 0; i < leng - 1; i++) {
// for (int j = i+1; j < leng; j++) {
// if (i != j) {
// for (int n = 0; n < leng; n++) {
// numTemp[n] = numberArr[n];
// }
//
// c = numTemp[i];
// numTemp[i] = numTemp[j];
// numTemp[j] = c;
//
// for (int k = 0; k < leng; k++) {
// cout << numTemp[k];
// }
// cout << endl;
// }
// }
// }*/
// doChange(exChange, numberArr);
//
// cout << "Case #" << tc << endl << maxValue << endl;
// }
// return 0;
//}
////////////////// Fast robot
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
static int arr[][];
static int map[][];
static int T, N, M, xStart, yStart, xEnd, yEnd,cr, cc, nr, nc;
static boolean visited[][];
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[100000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rQueue = new Queue();
static Queue cQueue = new Queue();
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
M = sc.nextInt();
N = sc.nextInt();
yStart = sc.nextInt();
xStart = sc.nextInt();
yEnd = sc.nextInt();
xEnd = sc.nextInt();
yStart--;
xStart--;
yEnd--;
xEnd--;
// System.out.println(xEnd+"--"+yEnd);
char tmp[][] = new char[N][M];
arr = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
String c = sc.next();
for (int j = 0; j < M; j++) {
tmp[i][j] = c.charAt(j);
if (tmp[i][j] == '0') {
arr[i][j] = -1;
}
if(tmp[i][j] == '1'){
arr[i][j] = -2;
}
visited[i][j]= false;
}
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
// System.out.println("-----------");
visited[xStart][yStart] = true;
rQueue.reset();
cQueue.reset();
rQueue.enQueue(xStart);
cQueue.enQueue(yStart);
while(!rQueue.isEmpty()){
cr = rQueue.deQueue();
cc = cQueue.deQueue();
for(int i = cc; i >= 0; i--){
if(arr[cr][i] == -2){
break;
}else if(visited[cr][i] == false && arr[cr][i] == -1){
rQueue.enQueue(cr);
cQueue.enQueue(i);
arr[cr][i] = arr[cr][cc] + 1;
visited[cr][i] = true;
if(i == 0) break;
}
}
for(int i = cc; i < M; i++){
if(arr[cr][i] == -2){
break;
}else if(visited[cr][i] == false && arr[cr][i] == -1){
rQueue.enQueue(cr);
cQueue.enQueue(i);
arr[cr][i] = arr[cr][cc] + 1;
visited[cr][i] = true;
if(i == M -1) break;
}
}
for(int i = cr; i >= 0; i--){
if(arr[i][cc] == -2 )
break;
else if(visited[i][cc] == false && arr[i][cc] == -1){
rQueue.enQueue(i);
cQueue.enQueue(cc);
arr[i][cc] = arr[cr][cc] + 1;
visited[i][cc] = true;
if(i == 0) break;
}
}
for(int i = cr; i < N; i++){
if(arr[i][cc] == -2){
break;
}else if(visited[i][cc] == false && arr[i][cc] == -1){
rQueue.enQueue(i);
cQueue.enQueue(cc);
arr[i][cc] = arr[cr][cc] + 1;
visited[i][cc] = true;
if(i == N -1)
break;
}
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
// System.out.println("-----------");
}
System.out.println(arr[xEnd][yEnd]);
}
}
}
//////////////// Find Cycle
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.lang.annotation.Retention;
import java.util.Scanner;
public class Main {
public static class Graph{
static int V;
static int [][] adj;
public Graph(int V){
this.V = V;
adj = new int[V][V];
}
public void addEdge(int v, int w){
adj[v][w] = 1;
}
public static boolean isCyclic(){
boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V];
for (int i = 0; i < V; i++) {
if (isCyclicUntil(i, visited, recStack)) {
return true;
}
}
return false;
}
public static boolean isCyclicUntil(int v, boolean[] visited, boolean[] recStack){
if (recStack[v]) {
return true;
}
if (visited[v]) {
return false;
}
visited[v] = true;
recStack[v] = true;
for (int i = 0; i < V; i++) {
if (adj[v][i] == 1 && isCyclicUntil(i, visited, recStack)) {
return true;
}
}
recStack[v] = false;
return false;
}
}
public static void main(String args[]) throws Exception
{
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
int T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
int V = sc.nextInt();
int m = sc.nextInt();
Graph graph = new Graph(V);
for (int i = 0; i < m; i++) {
int s1 = sc.nextInt();
int s2 = sc.nextInt();
s1--;
s2--;
graph.addEdge(s1, s2);
}
System.out.println("Case #" + tc);
if (graph.isCyclic()) {
System.out.println("1");
}
else {
System.out.println("0");
}
}
}
}
/////////////// Find model
import java.util.Scanner;
/*
ì�¬ì�©í��ë�� í�´ë��ì�¤ëª�ì�´ Solution ì�´ì�´ì�¼ í��ë¯�ë¡�, ê°�ê¸�ì � Solution.java 를 ì�¬ì�©í� ê²�ì�� ê¶�ì�¥í�©ë��ë�¤.
ì�´ë�¬í�� ì��í�©ì��ì��ë�� ë��ì�¼í��ê²� java Solution ëª�ë ¹ì�¼ë¡� í��ë¡�ê·¸ë�¨ì�� ì��í��í�´ë³¼ ì�� ì��ì�µë��ë�¤.
*/
public class Solution {
static int N;
static int[] Num;
public static void main(String args[]) throws Exception {
Scanner sc =new Scanner(System.in);
for (int tc = 1; tc <=10; tc++) {
int T = sc.nextInt();
int mode = 0;
int max = 0;
int a[] = new int[1000];
for (int i = 0; i < a.length; i++) {
a[i] = sc.nextInt();
if (a[i] > max) {
max = a[i];
}
}
int temp[] = new int[max+1];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < temp.length; j++) {
if (a[i] == j) {
temp[j] += 1;
}
}
}
int ctn = -1;
for (int i = 0; i < temp.length; i++) {
System.out.println(i+" "+temp[i]);
if (temp[i] >= ctn) {
ctn = temp[i];
mode = i;
}
}
System.out.println("#"+tc+" "+mode);
}
}
}
/////////////////// GridAcid
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
static int N, M, T, x, y, cr, cc, nr, nc, emptyCell_r, emptyCell_c, nextEmptyCell_r, nextEmptyCell_c;
static int map[][];
static boolean visited[][];
static int dx[] = {0, -1, 0, 1};
static int dy[] = {-1, 0, 1, 0};
public static class Queue{
int Data[];
int front, rear;
public Queue() {
Data = new int[10000000];
this.front = this.rear = -1;
}
public void reset() {
this.front = this.rear = -1;
}
public void enQueue(int value) {
Data[++rear] = value;
}
public int deQueue() {
return Data[++front];
}
public boolean is_Empty() {
if(this.front == this.rear) return true;
return false;
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++) {
int countTimeEmpty = 0; // Time to count EmptyCell
int countTimeGrid = 0; // Time to count GridCell == 1
int countValue_1 = 0;
int max = 0; // Cell max = TimeGrid
int count = 0; // Count valueCell == 1 and Visited == 1
int check = 0; // Check 4 cell of Neighbor
Queue rQueue = new Queue();
Queue cQueue = new Queue();
N = scanner.nextInt();
M = scanner.nextInt();
// Input location of cell where acid is poured
x = scanner.nextInt();
y = scanner.nextInt();
rQueue.enQueue(x-1);
cQueue.enQueue(y-1);
map = new int[N][M];
visited = new boolean[N][M];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
// 0: stone, 1: metal, 2: empty cell
map[i][j] = scanner.nextInt();
if(map[i][j] == 1) countValue_1++; // Count numbers of cell == 1
if(map[i][j] == 2) {
emptyCell_r = i;
emptyCell_c = j;
}
}
}
while(!rQueue.is_Empty()) {
cr = rQueue.deQueue();
cc = cQueue.deQueue();
visited[cr][cc] = true;
for(int k = 0; k < 4; k++) {
nr = cr + dx[k];
nc = cc + dy[k];
if(0 <= nr && nr < N && 0 <= nc && nc < M && map[nr][nc] == 1 && visited[nr][nc] == false) {
rQueue.enQueue(nr);
cQueue.enQueue(nc);
visited[nr][nc] = true;
map[nr][nc] = map[cr][cc] + 1;
count++;
}
if(max < map[cr][cc]) max = map[cr][cc];
}
}
if(count == (countValue_1 - 1)) countTimeGrid = max;
if(count != (countValue_1 - 1)) countTimeGrid = -1;
// Check neighbor of Emptycell
for(int k = 0; k < 4; k++) {
nextEmptyCell_r = emptyCell_r + dx[k];
nextEmptyCell_c = emptyCell_c + dy[k];
if(0<= nextEmptyCell_r && nextEmptyCell_r < N && 0 <= nextEmptyCell_c && nextEmptyCell_c < M && visited[nextEmptyCell_r][nextEmptyCell_c]) {
countTimeEmpty = countTimeEmpty > map[nextEmptyCell_r][nextEmptyCell_c] ? countTimeEmpty : map[nextEmptyCell_r][nextEmptyCell_c];
check++;
}
}
if(check != 4) {
System.out.println("Case #" + tc);
System.out.println("-1" + " -1");
}
if(check == 4) {
System.out.println("Case #" + tc);
System.out.println(countTimeEmpty + " " + countTimeGrid);
}
}
}
}
//////////////////// He thong dien
import java.util.Scanner;
public class Solution {
static int M, N, H, MAX = 10000000;
static int[] power;
static int[] weakPoint;
static int[][] a;
static Queue q;
static class Queue {
int h, t, s;
int[] a;
Queue(int n) {
h = t = s = 0;
a = new int[n];
}
void enqueue(int x) {
a[t++] = x;
t %= a.length;
s++;
}
int dequeue() {
int x = a[h++];
h %= a.length;
s--;
return x;
}
boolean isEmpty() {
return s == 0;
}
}
static void solve() {
while (!q.isEmpty()) {
int x = q.dequeue();
for (int i = 0; i < N; i++) {
if (a[x][i] == 1 && weakPoint[i] > weakPoint[x] + 1) {
weakPoint[i] = weakPoint[x] + 1;
q.enqueue(i);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tcs = sc.nextInt();
for (int tc = 1; tc <= tcs; tc++) {
N = sc.nextInt();
M = sc.nextInt();
H = sc.nextInt();
power = new int[M];
weakPoint = new int[N];
for (int i = 0; i < N; i++) {
weakPoint[i] = MAX;
}
q = new Queue(N * N * 2);
for (int i = 0; i < M; i++) {
power[i] = sc.nextInt();
weakPoint[power[i]] = 0;
q.enqueue(power[i]);
}
a = new int[N][N];
for (int i = 0; i < H; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
a[x][y] = 1;
a[y][x] = 1;
}
solve();
int id = 0;
for (int i = 0; i < N; i++) {
if (weakPoint[id] < weakPoint[i]) {
id = i;
}
}
System.out.println(id);
}
}
}
////////////// Hugo chay rung
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction;
import javax.xml.crypto.dsig.spec.XSLTTransformParameterSpec;
public class Main {
static int dx[] = {-1,0,1,0};
static int dy[] = {0,1,0,-1};
static int T, N, M;
static int map[][];
static boolean visited[][];
static int diamond[][];
static int fire[][];
static boolean lake[][];
static boolean exit[][];
static int SR, SC;
static int maxcnt, ans;
static int nextTime;
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
public static void resetx(){
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = false;
fire[i][j] = Integer.MAX_VALUE;
exit[i][j] = false;
lake[i][j] = false;
}
}
}
public static void fire(){
while (!rqueue.isEmpty()) {
int curr = rqueue.deQueue();
int curc = cqueue.deQueue();
for (int i = 0; i < 4; i++) {
int newr = curr + dx[i];
int newc = curc + dy[i];
if (newr >= 0 && newr < N && newc >= 0 && newc < M && lake[newr][newc] != true && fire[newr][newc] == Integer.MAX_VALUE) {
rqueue.enQueue(newr);
cqueue.enQueue(newc);
fire[newr][newc] = fire[curr][curc] + 1;
}
}
}
}
static Queue rqueue = new Queue();
static Queue cqueue = new Queue();
public static void backtrack(int r, int c, int time){
if (exit[r][c] == true) {
if (ans > maxcnt) {
maxcnt = ans;
}
}
for (int i = 0; i < 4; i++) {
int nextR = r + dx[i];
int nextC = c + dy[i];
if (nextR >= 0 && nextR < N && nextC >= 0 && nextC < M && !visited[nextR][nextC]) {
nextTime = 0;
if(lake[nextR][nextC] == false){
nextTime = time + 1;
if(nextTime < fire[nextR][nextC]){
ans += diamond[nextR][nextC];
visited[nextR][nextC] = true;
backtrack(nextR, nextC, nextTime);
ans -= diamond[nextR][nextC];
visited[nextR][nextC] = false;
}
}else{
nextTime = time + 2;
if(nextTime < fire[nextR][nextC]){
ans += diamond[nextR][nextC];
visited[nextR][nextC] = true;
backtrack(nextR, nextC, nextTime);
ans -= diamond[nextR][nextC];
visited[nextR][nextC] = false;
}
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // number of test cases
for (int t = 1; t <= T; t++) {
N = sc.nextInt(); // number of rows
M = sc.nextInt(); // number of columns
map = new int[N][M];
diamond = new int[N][M];
visited = new boolean[N][M];
fire = new int[N][M];
lake = new boolean[N][M];
exit = new boolean[N][M];
resetx();
SR = sc.nextInt();
SC = sc.nextInt();
SR--;
SC--;
map[SR][SC] = -1;
rqueue.reset();
cqueue.reset();
int fire1 = sc.nextInt();
for (int j = 0; j < fire1; j++) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
x1--;
y1--;
rqueue.enQueue(x1);
cqueue.enQueue(y1);
fire[x1][y1] = 0;
}
int lake1 = sc.nextInt();
for (int j = 0; j < lake1; j++) {
int x2 = sc.nextInt();
int y2 = sc.nextInt();
x2--;
y2--;
lake[x2][y2] = true;
}
int exit1 = sc.nextInt();
for (int j = 0; j < exit1; j++) {
int x3 = sc.nextInt();
int y3 = sc.nextInt();
x3--;
y3--;
exit[x3][y3] = true;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
diamond[i][j] = sc.nextInt();
}
}
ans = diamond[SR][SC];
visited[SR][SC] = true;
fire();
maxcnt = -1;
nextTime = 0;
backtrack(SR, SC, 0);
System.out.println("Case #"+t);
System.out.println(maxcnt);
}
}
}
/////////////////// Hugo ban dau
import java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static class Node{
int r,c;
Node(int r, int c){
this.r = r;
this.c = c;
}
}
static class Queue{
int front,back;
Node[] queue;
public Queue(int N) {
queue = new Node[N];
back = -1;
front = -1;
}
void push(Node node){
queue[++back] = node;
if(front == -1)
front = 0;
}
Node pop(){
Node re = queue[front++];
if(front>back){
front = -1;
back = -1;
}
return re;
}
boolean isEmpty(){
if(front ==-1)
return true;
return false;
}
}
static int t,m,n;
static int[][] a;
static int[][] visited;
static Queue queue;
static int[] dx1 = {0,1,0,-1};
static int[] dy1 = {1,0,-1,0};
static int[] dx2 = {1,-1};
static int[] dy2 = {0,0};
static int[] dx3 = {0,0};
static int[] dy3 = {1,-1};
static int[] dx4 = {-1,0};
static int[] dy4 = {0,1};
static int[] dx5 = {1,0};
static int[] dy5 = {0,1};
static int[] dx6 = {1,0};
static int[] dy6 = {0,-1};
static int[] dx7 = {0,-1};
static int[] dy7 = {-1,0};
static int[][] dx = {dx1,dx2,dx3,dx4,dx5,dx6,dx7};
static int[][] dy = {dy1,dy2,dy3,dy4,dy5,dy6,dy7};
static int xs,ys;
static int pump;
static int re;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int i = 0; i < t; i++) {
re = 0;
m = sc.nextInt();
n = sc.nextInt();
a = new int[m][n];
xs = sc.nextInt();
ys = sc.nextInt();
//System.out.println("xs ys:" + xs + " " + ys);
queue = new Queue(m * n);
pump = sc.nextInt();
visited = new int[m][n];
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
a[j][k] = sc.nextInt();
}
}
queue.push(new Node(xs, ys));
visited[xs][ys] = 1;
fun();
System.out.println("Case #" + (i+1));
System.out.println(re);
}
}
static void fun(){
while(!queue.isEmpty()){
Node u = queue.pop();
if(visited[u.r][u.c] == pump + 1)
break;
re++;
//System.out.println("pop:" + u.r + " " + u.c);
//System.out.println("pump:" + pump);
if(pump == 0)
break;
//visited[u.r][u.c] = 1;
int[] dr = dx[a[u.r][u.c] - 1];
int[] dc = dy[a[u.r][u.c] - 1];
int x,y;
for (int i = 0; i < dc.length; i++) {
x = u.r + dr[i];
y = u.c + dc[i];
if(x >= 0 && y >= 0 && x < m && y < n && visited[x][y] == 0 && a[x][y] != 0){
if(check(a[x][y], dr[i], dc[i])){
queue.push(new Node(x, y));
visited[x][y] = visited[u.r][u.c] + 1;
//System.out.println("push:" + x + " " + y);
}
}
}
}
}
static boolean check(int pipeNum, int rD,int cD){
int[] dr = dx[pipeNum - 1];
int[] dc = dy[pipeNum - 1];
int x,y;
for (int i = 0; i < dc.length; i++) {
x = dr[i];
y = dc[i];
if(x == -rD && y == -cD)
return true;
}
return false;
}
}
////////////// Hugo dao vang 1
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
public static int n;
public static int g;
public static int[][] matrix;
public static int[][] weight;
public static Point[] gold;
public static Point[] queue = new Point[1000000];
public static int nearGold;
public static int step;
public static Point[] impossible = new Point[4];
public static int index;
public static int[] dx = {-1, 1, 0, 0};
public static int[] dy = {0, 0, 1, -1};
public static class Point {
private int x;
private int y;
public Point(int x, int y) {
this.setX(x);
this.setY(y);
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
public static boolean checkPossible() {
for (Point point : gold) {
int x = point.getX();
int y = point.getY();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] == 1) return true;
}
}
return false;
}
public static void setGoldTo2() {
for (Point point : gold) {
int x = point.getX();
int y = point.getY();
matrix[x][y] = 2;
}
}
public static void goldDig(int xi, int yj) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++){
weight[i][j] = -1;
}
}
// Set result
int count = 0;
int max = 0;
queue[0] = new Point(xi, yj);
weight[xi][yj] = 0;
int head = 0, tail = 1;
while (head < tail) {
int x = queue[head].getX();
int y = queue[head].getY();
int nextScore = weight[x][y] + 1;
head++;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] != 0 && weight[newX][newY] == -1) {
weight[newX][newY] = nextScore;
queue[tail] = new Point(newX, newY);
tail++;
if (matrix[newX][newY] == 2) {
if (nextScore > max) {
max = nextScore;
}
count++;
}
}
}
}
if (nearGold < count) {
nearGold = count;
step = max;
index = 0;
for (Point point : gold) {
int px = point.getX();
int py = point.getY();
if (weight[px][py] == -1) {
impossible[index] = new Point(px, py);
index++;
}
}
} else if (nearGold == count && step > max) {
step = max;
index = 0;
for (Point point : gold) {
int px = point.getX();
int py = point.getY();
if (weight[px][py] == -1) {
impossible[index] = new Point(px, py);
index++;
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
for (int t = 1; t <= test; t++) {
System.out.println("Case #" + t);
n = sc.nextInt();
g = sc.nextInt();
matrix = new int[n][n];
gold = new Point[g];
for (int i = 0; i < g; i++) {
gold[i] = new Point(sc.nextInt() - 1, sc.nextInt() - 1);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
setGoldTo2();
if (!checkPossible()) {
System.out.println("-1");
continue;
}
nearGold = 0;
step = Integer.MAX_VALUE;
weight = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0 || matrix[i][j] == 2) continue;
goldDig(i, j);
}
}
System.out.println(step);
for (int i = 0; i < index; i++) {
int x = impossible[i].getX() + 1;
int y = impossible[i].getY() + 1;
System.out.println(x + " " + y);
}
}
}
}
////////////////// Hugo dao vang 2
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static int n;
public static int g;
public static int[][] matrix;
public static int[][] weight;
public static Point[] gold;
public static Point[] queue = new Point[1000000];
public static int nearGold;
public static int step;
public static Point[] impossible = new Point[4];
public static int index;
public static int[] dx = {-1, 1, 0, 0};
public static int[] dy = {0, 0, 1, -1};
public static class Point {
private int x;
private int y;
public Point(int x, int y) {
this.setX(x);
this.setY(y);
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
public static boolean checkPossible() {
for (Point point : gold) {
int x = point.getX();
int y = point.getY();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] == 1) return true;
}
}
return false;
}
public static void setGoldTo2() {
for (Point point : gold) {
int x = point.getX();
int y = point.getY();
matrix[x][y] = 2;
}
}
public static void goldDig(int xi, int yj) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++){
weight[i][j] = -1;
}
}
// Set result
int count = 0;
int max = 0;
queue[0] = new Point(xi, yj);
weight[xi][yj] = 0;
int head = 0, tail = 1;
while (head < tail) {
int x = queue[head].getX();
int y = queue[head].getY();
int nextScore = weight[x][y] + 1;
head++;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] != 0 && weight[newX][newY] == -1) {
weight[newX][newY] = nextScore;
queue[tail] = new Point(newX, newY);
tail++;
if (matrix[newX][newY] == 2) {
if (nextScore > max) {
max = nextScore;
}
count++;
}
}
}
}
if (nearGold < count) {
nearGold = count;
step = max;
index = 0;
for (Point point : gold) {
int px = point.getX();
int py = point.getY();
if (weight[px][py] == -1) {
impossible[index] = new Point(px, py);
index++;
}
}
} else if (nearGold == count && step > max) {
step = max;
index = 0;
for (Point point : gold) {
int px = point.getX();
int py = point.getY();
if (weight[px][py] == -1) {
impossible[index] = new Point(px, py);
index++;
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
for (int t = 1; t <= test; t++) {
System.out.println("Case #" + t);
n = sc.nextInt();
g = sc.nextInt();
matrix = new int[n][n];
gold = new Point[g];
for (int i = 0; i < g; i++) {
gold[i] = new Point(sc.nextInt() - 1, sc.nextInt() - 1);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
setGoldTo2();
if (!checkPossible()) {
System.out.println("-1");
continue;
}
nearGold = 0;
step = Integer.MAX_VALUE;
weight = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0 || matrix[i][j] == 2) continue;
goldDig(i, j);
}
}
if (index > 0) {
System.out.println("-1");
}else {
System.out.println(step);
}
}
}
}
///////////////////////////// Hugo dem vung
import java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static int t,m;
static int[][] a;
static int[][] b;
static int[][] visited;
static int[] dx = {1,0,-1,0};
static int[] dy = {0,1,0,-1};
static int cnt,max;
static int[] count;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int i = 0; i < t; i++) {
m = sc.nextInt();
a = new int[m][m];
b = new int[m][m];
count = new int[m];
visited = new int[m][m];
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
a[j][k] = sc.nextInt();
b[j][k] = a[j][k];
}
}
// cnt(1,1);
// visited = new int[m][m];
// dfs0(1, 1);
// max = 0;
// count = new int[m];
// cnt(2,4);
// visited = new int[m][m];
//
// dfs0(2, 4);
for (int j = 0; j < m; j++) {
for (int k = 0; k < a.length; k++) {
if(b[j][k] == 0){
visited = new int[m][m];
max = 0;
count = new int[m];
cnt(j,k);
visited = new int[m][m];
dfs0(j, k);
}
}
}
// for (int j = 0; j < m; j++) {
// for (int k = 0; k < a.length; k++) {
// System.out.print(b[j][k] + " ");
// }
// System.out.println();
// }
visited = new int[m][m];
cnt = 0;
for (int j = 0; j < m; j++) {
for (int k = 0; k < a.length; k++) {
if(visited[j][k] == 0){
cnt++;
cntRegion(j, k);
}
}
}
System.out.println("Case #" + (i+1));
System.out.println(cnt);
}
}
static void dfs(int i, int j, int val){
if(visited[i][j] == 1)
return;
visited[i][j] = 1;
cnt ++;
int x,y;
for (int k = 0; k < 4; k++) {
x = i + dx[k];
y = j + dy[k];
if(x >= 0 && y >= 0 && x < m && y < m && a[x][y] == val){
dfs(x, y, val);
}
}
}
static void cnt(int i, int j){
if(visited[i][j] == 1)
return;
visited[i][j] = 1;
cnt ++;
int x,y;
for (int k = 0; k < 4; k++) {
x = i + dx[k];
y = j + dy[k];
if(x >= 0 && y >= 0 && x < m && y < m ){
if(a[x][y] == 0){
cnt(x, y);
}else if(a[x][y] != 0){
cnt = 0;
dfs(x, y, a[x][y]);
count[a[x][y] - 1] += cnt;
}
}
}
int Max = 0;
for (int k = 0; k < a.length; k++) {
if(count[k] >= Max){
max = k;
Max = count[k];
}
}
//System.out.println(i +" " + max);
}
static void dfs0(int i, int j){
if(visited[i][j] == 1)
return;
visited[i][j] = 1;
b[i][j] = max + 1;
int x,y;
for (int k = 0; k < 4; k++) {
x = i + dx[k];
y = j + dy[k];
if(x >= 0 && y >= 0 && x < m && y < m && a[x][y] == 0){
dfs0(x, y);
}
}
}
static void cntRegion(int i, int j){
if(visited[i][j] != 0)
return;
visited[i][j] = cnt;
int x,y;
for (int k = 0; k < 4; k++) {
x = i + dx[k];
y = j + dy[k];
if(x >= 0 && y >= 0 && x < m && y < m && b[x][y] == b[i][j]){
cntRegion(x, y);
}
}
}
}
////////////// Hugo giao hang
import java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static int T, Sx, Sy, Hx, Hy, N;
static int points[][];
static int pos[][];
static boolean visited[];
static int check[];
static int path[];
int cnt;
static int map[][];
static int ans, minA;
public static void backtrack(int k, int count) {
if(ans >= minA){
return;
}
if(count == N + 1){
ans += map[k][N + 1];
if(ans < minA){
minA = ans;
}
ans -= map[k][N + 1];
return;
}
for(int i = 1; i <= N; i++){
if(visited[i] == false && map[k][i] != 0){
visited[i] = true;
ans += map[k][i];
backtrack(i, count + 1);
ans -= map[k][i];
visited[i] = false;
}
}
}
public static void BFS(){
for (int i = 0; i < N+2; i++) {
for (int j = 0; j < N+2; j++) {
if (i == j) {
map[i][j] = 0;
}
else{
map[i][j] = Math.abs(pos[i][0]-pos[j][0]) + Math.abs(pos[i][1]-pos[j][1]);
map[j][i] = Math.abs(pos[i][0]-pos[j][0]) + Math.abs(pos[i][1]-pos[j][1]);
}
}
}
}
public static void reset(){
for (int i = 0; i < N+2; i++) {
visited[i] = false;
pos[i][0] = pos[i][1] = 0;
for (int j = 0; j < N+2; j++) {
map[i][j] = 0;
}
}
}
static int minDistance = Integer.MAX_VALUE;
public static void main(String args[]) throws Exception
{
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt(); // number of test cases
for (int t = 1; t <= T; t++) {
Sx = scanner.nextInt(); // T�a �� công ty (Sx, Sy)
Sy = scanner.nextInt();
Hx = scanner.nextInt(); // T�a �� nhà Hugo (Hx, Hy)
Hy = scanner.nextInt();
N = scanner.nextInt(); // S� lượng �i�m giao hà ng
points = new int[N][2]; // Mảng lưu t�a �� các �i�m giao hà ng
visited = new boolean[N+2];
map = new int[N+2][N+2];
pos = new int[N+2][2];
reset();
for (int i = 1; i < N+1; i++) {
pos[i][0] = scanner.nextInt();
pos[i][1] = scanner.nextInt();
}
pos[0][0] = Sx;
pos[0][1] = Sy;
pos[N+1][0] = Hx;
pos[N+1][1] = Hy;
BFS();
ans = 0;
minA = Integer.MAX_VALUE;
backtrack(0, 1);
System.out.println("Case #" + t+" "+minA);
}
}
}
///////////// Hugo quan ly tau
package Lesson_15;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Hugo_Di_Tau {
static int T, N, C;
static int spots[]; // Trang thai ghe ngoi tren tau
static boolean visited[]; // Status Gate �ã �c duy�t hay chưa
static int gates[][]; // So luong nguoi dang wait at Gate
static int answer;
//Ham kiem tra xem cong do da mo de nguoi vao het chua
// True: Open - False: Close
public static boolean isOpened(){
for(int i = 0; i < 3; i++){
if(!visited[i]) return false;
}
return true;
}
// Khoang cach tu cong do den vi tri ben phai gan nhat
// Neu khong con cho ngoi ben phai thi tra ve gia tri rat lon
public static int distanceToRightSpot(int start){
for(int i = start; i <= N; i++){
if(spots[i] == -1 ) return i - start;
}
return 1000000;
}
// Khoang cach tu cong do den vi tri ben trai gan nhat
public static int distanceToLeftSpot(int start){
for(int i = start; 1 <= i; i--){
if(spots[i] == -1 ) return start - i;
}
return 1000000;
}
public static void backTrack(int sum){
// Kiem tra cong da mo het chua ,neu da mo het tra ve gia tri
if(isOpened()){
if(answer > sum) answer = sum;
return;
}
for(int i = 0; i < 3; i++){
// Cong da dc mo thi bo qua
if(visited[i]) continue;
// Cong chua mo thi tham cong do va danh dau da tham
visited[i] = true;
int add = gates[i][1];
// Xep het nguoi tai cong do vao vi tri. De lai 1 nguoi cuoi cung de check
for(int j = 0; j < gates[i][1] - 1; j++){
int left = distanceToLeftSpot(gates[i][0]); // Kc cong do den trai
int right = distanceToRightSpot(gates[i][0]);
// Kiem tra khoang cach khi them vao trai/ phai. Ben nao nho hon thi lay
if(left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
}
// Tra ve khoang cach nguoi cuoi cung cua cong do so voi ben trai/ phai
int left = distanceToLeftSpot(gates[i][0]);
int right = distanceToRightSpot(gates[i][0]);
// Neu khoang cach do khac nhau thi check xem ben trai hay phai nho hon de ta xep
if(left != right)
{
if(left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
backTrack(sum + add);
}
// Neu khoang cach bang nhau thi can dat thu vao ca 2 ben trai va phai
else
{
add += left;
spots[gates[i][0] + right] = i;
backTrack(sum + add);
spots[gates[i][0] + right] = -1;
spots[gates[i][0] - left] = i;
backTrack(sum + add);
spots[gates[i][0] -left] = -1;
}
// Tra lai cong chua tham de backTrack lai
visited[i] = false;
// Tra lai vi tri cong do da ngoi
for(int j = 1; j <= N; j++){
if(spots[j] == i) spots[j] = -1;
}
}
}
public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Hugo_Di_Tau"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
N = scanner.nextInt();
gates = new int[3][2];
for(int i = 0; i < 3; i++){
gates[i][0] = scanner.nextInt(); // Vi tri cong
gates[i][1] = scanner.nextInt(); // So luong nguoi trc cong
}
spots = new int[N+1];
visited = new boolean[N+1];
for(int i = 1; i <= N; i++){
spots[i] = -1;
}
answer = 10000;
backTrack(0);
System.out.println("Case #"+ tc );
System.out.println(answer);
}
}
}
///////////////////// Hugo thi chay
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
public class Main {
static int M;// nang luong toi da
static int D;// chieu dai quang duong
static int second[];
static int energy[];
static int answer;
private static void backTrack(int type, int usedEnergy, int time, int dis) {
if (usedEnergy > M || time > answer)
return;
if (type == 5) {
if (dis == 0 && time < answer)
answer = time;
return;
}
backTrack(type + 1, usedEnergy, time, dis);
for (int i = 1; i <= dis; i++){
backTrack(type + 1, usedEnergy + i * energy[type], time + i * second[type], dis - i);
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
M = sc.nextInt();
D = sc.nextInt();
second = new int[5];
energy = new int[5];
for (int i = 0; i < 5; i++) {
int minute = sc.nextInt();
second[i] = sc.nextInt() + minute * 60;
energy[i] = sc.nextInt();
}
answer = Integer.MAX_VALUE;
backTrack(0, 0, 0, D);
if (answer == Integer.MAX_VALUE)
System.out.println("Case #" + tc + "\n" + "-1");
else
System.out.println("Case #" + tc + "\n" + answer / 60 + " "
+ answer % 60);
}
}
}
/////////////////// Hugo va chi ong nau
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static boolean position[][];
static int n, m, max;
static int dx1[] = { -1, -1, 0, 1, 0, -1 };// dx le
static int dy1[] = { 0, 1, 1, 0, -1, -1 };// dy le
static int dx2[] = { -1, 0, 1, 1, 1, 0 };// dx chan
static int dy2[] = { 0, 1, 1, 0, -1, -1 };// dy chan
static int matrix[][];
public static void main(String args[]) throws Exception {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
n = sc.nextInt();
m = sc.nextInt();
max = 0;
matrix = new int[m][n];
position = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sumT(i, j);
bt(i, j, 0, matrix[i][j]);
position[i][j] = false;
}
}
System.out.println("Case #" + test_case + "\n" + max * max);
}
}
static void sumT(int i, int j) {
int sum = 0;
if (j % 2 == 0) {
for (int t1 = 0; t1 < 4; t1++) {
int x1 = i + dx1[t1];
int y1 = j + dy1[t1];
if (!dk(x1, y1))
return;
for (int t2 = t1 + 1; t2 < 5; t2++) {
int x2 = i + dx1[t2];
int y2 = j + dy1[t2];
if (!dk(x2, y2))
return;
for (int t3 = t2 + 1; t3 < 6; t3++) {
int x3 = i + dx1[t3];
int y3 = j + dy1[t3];
if (dk(x3, y3)) {
sum = matrix[i][j]+matrix[x1][y1]+matrix[x2][y2]+matrix[x3][y3];
if(max<sum)
max=sum;
}
}
}
}
} else {
for (int t1 = 0; t1 < 4; t1++) {
int x1 = i + dx2[t1];
int y1 = j + dy2[t1];
if (!dk(x1, y1))
return;
for (int t2 = t1 + 1; t2 < 5; t2++) {
int x2 = i + dx2[t2];
int y2 = j + dy2[t2];
if (!dk(x2, y2))
return;
for (int t3 = t2 + 1; t3 < 6; t3++) {
int x3 = i + dx2[t3];
int y3 = j + dy2[t3];
if (dk(x3, y3)) {
sum = matrix[i][j]+matrix[x1][y1]+matrix[x2][y2]+matrix[x3][y3];
if(max<sum)
max=sum;
}
}
}
}
}
}
static void bt(int i, int j, int count, int sum) {
if (count == 3) {
if (max < sum) {
max = sum;
}
} else {
position[i][j] = true;
if (j % 2 == 0) {
for (int t = 0; t < 6; t++) {
int x = i + dx1[t];
int y = j + dy1[t];
if (dk(x, y)) {
bt(x, y, count + 1, sum + matrix[x][y]);
position[x][y] = false;
}
}
} else {
for (int t = 0; t < 6; t++) {
int x = i + dx2[t];
int y = j + dy2[t];
if (dk(x, y)) {
bt(x, y, count + 1, sum + matrix[x][y]);
position[x][y] = false;
}
}
}
}
}
static boolean dk(int i, int j) {
return i > -1 && i < m && j > -1 && j < n && !position[i][j];
}
}
///////////// Hugo ve nha
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.sql.Time;
import java.util.Scanner;
import javax.management.openmbean.OpenDataException;
import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction;
public class Main {
static int t, m;
static int[][] a;
static int[] visited;
static int[] aLinh;
static int re,soLinh;
static void fun(int i, int price) {
if(i == m) {
//System.out.println("minh" + price);
if(re > price) {
re = price;
}
return;
}
if(price >= re) {
return;
}
// 1pass 2:Hire 3: battle
for (int j = 1; j <= 3; j++) {
visited[i] = j;
//print();
//System.out.println("price:" + price);
if(j == 1) {
fun(i+1, price + a[1][i]);
}else if(j == 2) {
hire(a[0][i]);
fun(i+1, price + a[1][i] * 2);
unhire(a[0][i]);
}else {
if(a[0][i]<=soLinh) {
int tem0 = aLinh[0];
int tem1 = aLinh[1];
int tem2 = aLinh[2];
int temLinh = soLinh;
danh(a[0][i]);
fun(i+1, price);
soLinh = temLinh;
aLinh[0] = tem0;
aLinh[1] = tem1;
aLinh[2] = tem2;
}
}
visited[i] = 0;
}
}
static void hire(int linh) {
soLinh = 0;
aLinh[0] += linh;
for (int i = 2; i >= 0; i--) {
soLinh += aLinh[i];
}
}
static void unhire(int linh) {
soLinh = 0;
aLinh[0] -= linh;
for (int i = 2; i >= 0; i--) {
soLinh += aLinh[i];
}
}
static void danh(int dich) {
for (int i = 2; i >= 0; i--) {
if(aLinh[i] != 0) {
if(aLinh[i] >= dich) {
aLinh[i] -= dich;
break;
}
else {
//aLinh[i] = 0;
dich -=aLinh[i];
aLinh[i] = 0;
}
}
}
aLinh[2]= aLinh[1];
aLinh[1]= aLinh[0];
aLinh[0] = 0;
soLinh = aLinh[1] + aLinh[2];
}
public static void main(String args[]) throws Exception {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int i = 0; i < t; i++) {
aLinh = new int[3];
m = sc.nextInt();
visited = new int[m];
re = 300000;
a = new int[2][m];
for (int j = 0; j < m; j++) {
a[0][j] = sc.nextInt();
a[1][j] = sc.nextInt();
}
fun(0,0);
System.out.println("#"+(i+1) + " " +re);
}
//long end = Calendar.getInstance().getTimeInMillis();
//System.out.println(end - start);
}
}
//////////// Hugo xep lich quanimport java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static int t,n,l1,l2,l3,p1,p2,p3, max, min, re,maxElm;
static int[][] time;
static int[][] ads;
static int[] visited;
static int[][] vitri;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int i = 0; i < t; i++) {
maxElm = 0;
re = 0;
max = 0;
min = 50;
n = sc.nextInt();
ads = new int[2][3];
ads[0][0] = sc.nextInt();
ads[0][1] = sc.nextInt();
ads[0][2] = sc.nextInt();
ads[1][0] = sc.nextInt();
ads[1][1] = sc.nextInt();
ads[1][2] = sc.nextInt();
max = ads[0][0] + ads[0][1] + ads[0][2];
if(maxElm < ads[0][0]) {
maxElm = ads[0][0];
}
if(maxElm < ads[0][1]) {
maxElm = ads[0][1];
}
if(maxElm < ads[0][2]) {
maxElm = ads[0][2];
}
time = new int[2][n];
for (int j = 0; j < n; j++) {
time[0][j] = sc.nextInt();
time[1][j] = sc.nextInt();
int tem = time[0][j] + time[1][j];
if(tem > max){
max = tem;
}
if(min > time[0][j]){
min = time[0][j];
}
}
max +=maxElm;
visited = new int[max];
vitri = new int[3][3];
//System.out.println(check(10,2));
// visited(2,2,1);
// System.out.println(check(1, 1));
// for (int j = 0; j < max; j++) {
// System.out.print(j +":" + visited[j] + " ");
// }
// System.out.println();
fun(0);
System.out.println("Case #" + (i+1));
//System.out.println(max);
System.out.println(re);
}
}
static void fun(int ad){
if(ad == 3){
// for (int j = 0; j < max; j++) {
// System.out.print(j +":" + visited[j] + " ");
// }
// System.out.println();
int score = score();
if( score > re){
re = score;
}
return;
}
int len = ads[0][ad];
int point = ads[1][ad];
for (int j = 0; j < max; j++) {
if(check(j, len)){
visited(j,len,point);
vitri[0][ad] = j;
vitri[1][ad] = j + len -1;
vitri[2][ad] = point;
fun(ad + 1);
unvisited(j, len);
}
}
}
static boolean check(int i, int len){
if(i + len > max ) {
return false;
}
for (int j = i; j <= i + len -1; j++) {
if(visited[j] != 0)
return false;
}
return true;
}
static void visited(int i, int len, int vi){
int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
for (int j = i; j <= top; j++) {
visited[j] = vi;
}
for (int j = 0; j < ads.length; j++) {
}
}
static void unvisited(int i, int len){
int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
for (int j = i; j <= top; j++) {
visited[j] = 0;
}
}
static int score() {
int re = 0;
int[] arr = new int[n];
for (int i = 0; i < 3; i++) {
int a = vitri[0][i];
int b = vitri[1][i];
int point = vitri[2][i];
for (int j = 0; j < n; j++) {
if(a >= time[0][j] - 1 && b <= time[1][j] + time[0][j] - 2) {
if(point > arr[j]) {
arr[j] = point;
}
}
}
}
for (int i = 0; i < n; i++) {
re += arr[i];
}
return re;
}
}
/////////// Lang macg cao
import java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static int t,n,l1,l2,l3,p1,p2,p3, max, min, re,maxElm;
static int[][] time;
static int[][] ads;
static int[] visited;
static int[][] vitri;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int i = 0; i < t; i++) {
maxElm = 0;
re = 0;
max = 0;
min = 50;
n = sc.nextInt();
ads = new int[2][3];
ads[0][0] = sc.nextInt();
ads[0][1] = sc.nextInt();
ads[0][2] = sc.nextInt();
ads[1][0] = sc.nextInt();
ads[1][1] = sc.nextInt();
ads[1][2] = sc.nextInt();
max = ads[0][0] + ads[0][1] + ads[0][2];
if(maxElm < ads[0][0]) {
maxElm = ads[0][0];
}
if(maxElm < ads[0][1]) {
maxElm = ads[0][1];
}
if(maxElm < ads[0][2]) {
maxElm = ads[0][2];
}
time = new int[2][n];
for (int j = 0; j < n; j++) {
time[0][j] = sc.nextInt();
time[1][j] = sc.nextInt();
int tem = time[0][j] + time[1][j];
if(tem > max){
max = tem;
}
if(min > time[0][j]){
min = time[0][j];
}
}
max +=maxElm;
visited = new int[max];
vitri = new int[3][3];
//System.out.println(check(10,2));
// visited(2,2,1);
// System.out.println(check(1, 1));
// for (int j = 0; j < max; j++) {
// System.out.print(j +":" + visited[j] + " ");
// }
// System.out.println();
fun(0);
System.out.println("Case #" + (i+1));
//System.out.println(max);
System.out.println(re);
}
}
static void fun(int ad){
if(ad == 3){
// for (int j = 0; j < max; j++) {
// System.out.print(j +":" + visited[j] + " ");
// }
// System.out.println();
int score = score();
if( score > re){
re = score;
}
return;
}
int len = ads[0][ad];
int point = ads[1][ad];
for (int j = 0; j < max; j++) {
if(check(j, len)){
visited(j,len,point);
vitri[0][ad] = j;
vitri[1][ad] = j + len -1;
vitri[2][ad] = point;
fun(ad + 1);
unvisited(j, len);
}
}
}
static boolean check(int i, int len){
if(i + len > max ) {
return false;
}
for (int j = i; j <= i + len -1; j++) {
if(visited[j] != 0)
return false;
}
return true;
}
static void visited(int i, int len, int vi){
int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
for (int j = i; j <= top; j++) {
visited[j] = vi;
}
for (int j = 0; j < ads.length; j++) {
}
}
static void unvisited(int i, int len){
int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
for (int j = i; j <= top; j++) {
visited[j] = 0;
}
}
static int score() {
int re = 0;
int[] arr = new int[n];
for (int i = 0; i < 3; i++) {
int a = vitri[0][i];
int b = vitri[1][i];
int point = vitri[2][i];
for (int j = 0; j < n; j++) {
if(a >= time[0][j] - 1 && b <= time[1][j] + time[0][j] - 2) {
if(point > arr[j]) {
arr[j] = point;
}
}
}
}
for (int i = 0; i < n; i++) {
re += arr[i];
}
return re;
}
}
/////////// Lang mac
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static int T, N;
public static class TrafficNetwork{
private int graph[][];
private int visited[];
private int low[];
private int disc[];
private int parent[];
private int bridges;
private int time;
public TrafficNetwork(int[][] graph){
this.graph = graph;
this.visited = new int[graph.length];
this.low = new int[graph.length];
this.disc = new int[graph.length];
this.parent = new int[graph.length];
this.bridges = 0;
this.time = 0;
}
public int countRegions() {
int count = 0;
for (int i = 0; i < graph.length; i++) {
if (visited[i] == 0) {
dfs(i);
count++;
}
}
return count;
}
public int countIsolatedVillages() {
int count = 0;
for (int i = 0; i < graph.length; i++) {
boolean isolated = true;
for (int j = 0; j < graph.length; j++) {
if (graph[i][j] == 1) {
isolated = false;
break;
}
}
if (isolated) {
count++;
}
}
return count;
}
public int countBridges(){
int count = 0;
for (int i = 0; i < graph.length; i++) {
if (visited[i] == 0) {
dfsBridges(i);
}
}
return bridges;
}
public void dfs(int v){
visited[v] = 1;
disc[v] = low[v] = ++time;
for (int i = 0; i < graph.length; i++) {
if (graph[v][i] == 1) {
if (visited[i] == 0) {
parent[i] = v;
dfs(i);
low[v] = Math.min(low[v], low[i]);
if (low[i] > disc[v]) {
bridges++;
}
}
else if (i != parent[v]) {
low[v] = Math.min(low[v], disc[i]);
}
}
}
}
private void dfsBridges(int v) {
visited[v] = 1;
disc[v] = low[v] = ++time;
for (int i = 0; i < graph.length; i++) {
if (graph[v][i] == 1) {
if (visited[i] == 0) {
parent[i] = v;
dfsBridges(i);
low[v] = Math.min(low[v], low[i]);
if (low[i] > disc[v]) {
bridges++;
}
}
else if (i != parent[v]) {
low[v] = Math.min(low[v], disc[i]);
}
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
int graph[][] = new int[N][N];
boolean[] visited = new boolean[N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
graph[i][j] = sc.nextInt();
}
visited[i] = false;
}
TrafficNetwork traff = new TrafficNetwork(graph);
int regions = traff.countRegions();
int isolated = traff.countIsolatedVillages();
int bridges = traff.countBridges();
System.out.println(regions+" "+isolated+" "+bridges);
}
}
}
/// C2
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#define side 500
int A[side][side];
int visit[side], parent[side];
int N;
int bridge;
bool notBridge;
void reset(int R[side]){
for (int i = 1; i <= N; i++){
R[i] = 0;
}
}
void DFS(int i) {
//mark start
visit[i] = 1;
for (int j = 1;j<=N;j++){
if (A[i][j]==1){
if (visit[j]==0){
DFS(j);
}
}
}
}
void DFS2(int i, int j) {
//Stop
if (i == j){
notBridge = true;
return;
}
visit[i] = 1;
for (int d = 1;d<=N;d++){
if (A[i][d]==1){
if (visit[d]==0){
DFS2(d,j);
}
}
if (notBridge){
return;
}
}
}
int main(int argc, char** argv){
int test_case;
int T;
int i, j;
int group, villalone, lines, bridge;
ios::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case){
cin >> N;
for (i = 1; i <= N; i++){
for (j = 1; j<=N;j++){
cin >> A[i][j];
}
}
villalone=0;
for (i = 1; i <= N; i++){
bool alone = true;
for (j = 1; j<=N;j++){
if (A[i][j] == 1){
alone = false;
break;
}
}
if (alone) villalone++; //isolate villages
}
group = 0;
reset(visit);
for (i=1;i<=N;i++){
if (visit[i]==0){
group++; //number of village group
DFS(i);
}
}
bridge = 0;
for (i=1; i<=N;i++){
for (j=i+1;j<=N;j++){
if (A[i][j]==1){
notBridge = false;
A[i][j] = 0;
reset(visit);
DFS2(i,j);
if (!notBridge) bridge++;
A[i][j] = 1;
}
}
}
// Print the answer to standard output(screen).
cout << group << " " << villalone << " " << bridge << endl;
}
//while(1);
return 0;//Your program should return 0 on normal termination.
}
///////////////// Little Elephants
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int T, N, K, M;
static int R[];
static int ans, minans;
static int res;
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
for (int testCase = 1; testCase <= t; testCase++) {
N = scanner.nextInt();
K = scanner.nextInt();
M = scanner.nextInt();
R = new int[N];
for (int i = 0; i < N; i++) {
R[i] = scanner.nextInt();
}
minans = 1000000000;
ans = 0;
backtrack(0);
if(minans == 1000000000){
System.out.println("#" + testCase + " -1");
}else{
System.out.println("#" + testCase + " " + minans);
}
}
}
private static void backtrack(int k) {
if(minans <= ans){
return;
}
if(check() == false){
if(ans < minans){
minans = ans;
}
return;
}
if(k == N){
return;
}
R[k]++;
ans++;
backtrack(k + 1);
ans--;
R[k]--;
backtrack(k + 1);
}
private static boolean check() {
for(int i = 0; i <= N - K; i++){
int tmp = 0; int res = 0;
for(int j = i; j < i + K; j++){
if(res < R[j]){
res = R[j];
}
}
for(int j = i; j < i + K; j++){
if(R[j] == res){
tmp++;
}
}
if(tmp >= M){
return true;
}
}
return false;
}
}
//////////// Mario
import java.util.Scanner;
public class Solution {
static int map[][];
static int visited[][];
static int dx[] = { 0, 0, -1, 1 };
static int dy[] = { -1, 1, 0, 0 };
static Node stack[];
static int top;
static int min;
static class Node {
int r;
int c;
public Node(int x, int y) {
r = x;
c = y;
}
}
static void push(int x, int y) {
Node n = new Node(x, y);
top++;
stack[top] = n;
}
static Node pop() {
Node n = stack[top];
top--;
return n;
}
static Node peek() {
Node n = stack[top];
return n;
}
public static void main(String args[]) throws Exception{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
System.out.println("Case #" + tc);
int N = sc.nextInt();
int M = sc.nextInt();
int startX = 0;
int startY = 0;
top = -1;
stack = new Node[1000000];
map = new int[N][M];
visited = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
if (map[i][j] == 2) {
startX = i;
startY = j;
}
}
}
min = 0;
int h = 0;
boolean check = false;
while (true) {
push(startX, startY);
visited[startX][startY] = 1;
h++;
while (top >= 0) {
Node n = pop();
for (int i = 0; i < 4; i++) {
int newR = n.r + dx[i];
int newC = n.c + dy[i];
if (newR >= 0 && newR < N && newC >= 0 && newC < M
&& visited[newR][newC] == 0) {
if (dx[i] == 0 && map[newR][newC] == 1) {
push(newR, newC);
visited[newR][newC] = 1;
}
if (dy[i] == 0) {
if (map[newR][newC] == 1) {
push(newR, newC);
visited[newR][newC] = 1;
} else {
int ori = newR;
int count = 1;
while (true) {
if (count == h) {
break;
}
newR += dx[i];
if (newR < 0 || newR >= N) {
break;
}
if (map[newR][newC] != 0
&& visited[newR][newC] == 0) {
if (map[newR][newC] == 3) {
check = true;
break;
}
push(newR, newC);
visited[newR][newC] = 1;
break;
} else {
count++;
}
}
newR = ori;
}
}
if (map[newR][newC] == 3) {
check = true;
}
if (check) {
min = h;
top = -1;
break;
}
}
}
}
if (check) {
break;
}
visited = new int[N][M];
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// System.out.print(visited[i][j]);
// }
// System.out.println();
// }
System.out.println(min);
}
}
}
/////////// Matrix Product
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static long a[][];
static int T,n,m;
static long mod = 100000007;
public static long[][] multiplymatic(long [][] matrix1, long [][] matrix2){
int rows1 = matrix1.length;
int cols1 = matrix1[0].length;
int cols2 = matrix2[0].length;
long[][] result = new long[rows1][cols2];
for (int i = 0; i < rows1; i++) {
for (int j = 0; j < cols2; j++) {
for (int k = 0; k < cols1; k++) {
result[i][j] = (result[i][j] + matrix1[i][k]*matrix2[k][j]) % mod;
}
}
}
return result;
}
public static long[][] power(long[][] matrix, long exponent) {
if (exponent == 1) {
return matrix;
}
else if (exponent%2 == 0) {
long[][] halfpower = power(matrix, exponent/2);
return multiplymatic(halfpower, halfpower);
}
else{
long[][] halfpower = power(matrix, (exponent -1)/2);
long[][] squaredhalfpower = multiplymatic(halfpower, halfpower);
return multiplymatic(squaredhalfpower, matrix);
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
n = sc.nextInt();
m = sc.nextInt();
a = new long[n][n];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
a[i][j] = sc.nextInt();
}
}
long[][] result = power(a, m);
System.out.println("Case #"+tc);
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result.length; j++) {
System.out.print(result[i][j] +" ");
}
System.out.println();
}
}
}
}
//////////////////// Merge Sort
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
public class Main {
static int a[];
static int T;
static void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[] = new int[n1];
int R[] = new int[n2];
// Copy data to temp arrays
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Merge the temp arrays
// Initial indices of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
static void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
public static void main(String[] args) throws FileNotFoundException {
// System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < a.length; i++) {
a[i] = sc.nextInt();
}
sort(a, 0, n-1);
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
System.out.println();
// System.out.println("Case #"+tc);
// System.out.println(maxprize);
}
}
}
///////////////// Minimal Big Sum
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
public static boolean isValidBigSum(int K, int A[], int bigSum) {
int blocks = 0;
int sum = 0;
for (int num: A) {
if (sum + num > bigSum) {
blocks++;
sum = num;
}
else
sum += num;
}
return blocks < K;
}
public static int minimalBigSum(int K, int[] A) {
int lower = Integer.MIN_VALUE;
int upper = 0;
for (int num : A) {
lower = Math.max(lower, num);
upper += num;
}
while (lower <= upper) {
int mid = (lower+upper)/2;
if (isValidBigSum(K, A, mid)) {
upper = mid -1;
}
else {
lower = mid +1;
}
}
return lower;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
// TODO Auto-generated method stub
for (int tc = 1; tc <= T; tc++) {
int K = sc.nextInt();
int N = sc.nextInt();
int A[] = new int[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextInt();
}
int res = minimalBigSum(K, A);
System.out.println("#"+tc +" "+res);
}
}
}
//////////////////// Nang cap may tinh
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int T,n, m, c,ans;
static int[] price;
static int[][] dis;
static int[] used;
static int num;
static int[] visited;
static int minA = Integer.MAX_VALUE;
public static void backtrack(int k) {
if(k == c){
if(ans < minA){
minA = ans;
}
return;
}
if(ans > minA) return;
ans += price[used[k] - 1];
backtrack(k + 1);
ans -= price[used[k] - 1];
for(int i = 0; i < m; i++){
for(int j = 2; j < 2 + dis[i][1]; j++){
if(dis[i][j] == used[k]){
if(visited[i] == 0){
visited[i] = 1;
ans += dis[i][0];
backtrack(k + 1);
ans -= dis[i][0];
visited[i] = 0;
}else{
backtrack(k + 1);
}
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
n = sc.nextInt();
price = new int[n];
for (int i = 0; i < n; i++) {
price[i] = sc.nextInt();
}
m = sc.nextInt();
dis = new int[35][35];
visited = new int[35];
for (int i = 0; i < m; i++) {
dis[i][0] = sc.nextInt();
dis[i][1] = sc.nextInt();
for (int j = 2; j < dis[i][1]+2; j++) {
dis[i][j] = sc.nextInt();
}
}
c = sc.nextInt();
used = new int[c];
for (int i = 0; i < c; i++) {
used[i] = sc.nextInt();
}
ans = 0;
minA = 10000000;
backtrack(0);
System.out.println("#" + tc + " " + minA);
}
}
}
///////////////////// Number
#include <iostream>
#define SIZE 30
using namespace std;
int data[SIZE], MAX[SIZE][SIZE],MIN[SIZE][SIZE];
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
int Easy(int i, int j) {
if (i > j) {
return 0;
}
if (MAX[i][j])
return MAX[i][j];
int t1 = data[i] + Easy(i + 1, j - 1);
int t2 = data[i] + Easy(i + 2, j);
int t3 = data[j] + Easy(i + 1, j - 1);
int t4 = data[j] + Easy(i, j - 2);
return MAX[i][j] = Max(Max(t1, t2), Max(t3, t4));
}
int Hard(int i,int j) {
if (i > j) {
return 0;
}
if (MIN[i][j])
return MIN[i][j];
int t1 = data[i] + Hard(i + 1, j - 1);
int t2 = data[i] + Hard(i + 2, j);
int t3 = data[j] + Hard(i + 1, j - 1);
int t4 = data[j] + Hard(i, j - 2);
return MIN[i][j] = Max(Min(t1, t2), Min(t3, t4));
}
int main() {
int T, K;
freopen("input.txt", "r", stdin);
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> K;
for (int i = 0; i <K; i++) {
cin >> data[i];
}
for (int i = 0;i <SIZE; i++) {
for (int j = 0;j <SIZE; j++) {
MAX[i][j]=0;
MIN[i][j]=0;
}
}
int Ea = Easy(0, K-1);
int Ha = Hard(0, K-1);
cout << "Case #" << tc << endl << Ea << " " << Ha << endl;
}
return 0;
}
////////////////// Nuoc bien
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
public class Main {
static int[][] a;
static int[][] visit;
static Node[] queue = new Node[10005];
static int start, end;
static int[] dx = {0,0, -1, 1};
static int[] dy = {-1,1,0,0};
static class Node {
int r, c;
public Node (int r, int c) {
this.r = r;
this.c = c;
}
}
private static Node pop() {
start++;
return queue[start];
}
private static void push(Node node) {
end++;
queue[end] = node;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int t = 1;
while (true) {
int row = sc.nextInt();
int col = sc.nextInt();
a = new int[row][col];
if (row == 0 && col == 0) {
break;
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
a[i][j] = sc.nextInt();
}
}
int feet = 1;
int lienthong = 0;
while (true) {
visit = new int[row][col];
//duyet hang thu 1
for (int i = 0; i < col; i++) {
if (a[0][i] <= feet && visit[0][i] == 0) {
start = end = -1;
push(new Node(0,i));
visit[0][i] = 1;
a[0][i]= 0;
while (start < end) {
Node node = pop();
for (int j = 0; j < 4; j++) {
int x = node.r + dx[j];
int y = node.c + dy[j];
if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
a[x][y] = 0;
push(new Node(x,y));
visit[x][y] = 1;
}
}
}
}
}
//duyet hang cuoi
for (int i = 0; i < col; i++) {
if (a[row-1][i] <= feet && visit[row-1][i] == 0) {
start = end = -1;
push(new Node(row-1,i));
visit[row-1][i] = 1;
a[row-1][i] = 0;
while (start < end) {
Node node = pop();
for (int j = 0; j < 4; j++) {
int x = node.r + dx[j];
int y = node.c + dy[j];
if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
a[x][y] = 0;
push(new Node(x,y));
visit[x][y] = 1;
}
}
}
}
}
//duyet cot dau
for (int i = 1; i < row - 1; i++) {
if (a[i][0] <= feet && visit[i][0] == 0) {
start = end = -1;
push(new Node(i,0));
visit[i][0] = 1;
a[i][0] = 0;
while (start < end) {
Node node = pop();
for (int j = 0; j < 4; j++) {
int x = node.r + dx[j];
int y = node.c + dy[j];
if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
a[x][y] = 0;
push(new Node(x,y));
visit[x][y] = 1;
}
}
}
}
}
//duyet cot cuoi
for (int i = 1; i < row - 1; i++) {
if (a[i][col-1] <= feet && visit[i][col-1] == 0) {
start = end = -1;
push(new Node(i,col-1));
visit[i][col-1] = 1;
a[i][col-1] = 0;
while (start < end) {
Node node = pop();
for (int j = 0; j < 4; j++) {
int x = node.r + dx[j];
int y = node.c + dy[j];
if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
a[x][y] = 0;
push(new Node(x,y));
visit[x][y] = 1;
}
}
}
}
}
//duyet toan bo ma tran dem thanhf phan lien thong
//neu khong co thanh phan lien thong ( toan bo ma tran la 0) ghi nhan ket qua
//Neu thanh phan lien thong > 1 -> dao bi chia cat
//Thanh phan lien thong = 1 lai tang feet len de xet tiep
visit = new int[row][col];
lienthong = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (a[i][j] != 0 && visit[i][j] == 0) {
lienthong++;
start = end = -1;
push(new Node(i,j));
visit[i][j] = 1;
while (start < end) {
Node node = pop();
for (int k = 0; k < 4; k++) {
int x = node.r + dx[k];
int y = node.c + dy[k];
if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] > 0 && visit[x][y] == 0) {
push(new Node(x,y));
visit[x][y] = 1;
}
}
}
}
}
}
if (lienthong == 0 || lienthong > 1) {
break;
}
feet++;
}
System.out.print("Case " + t + ": ");
if (lienthong == 0) {
System.out.println("Island never splits.");
} else {
System.out.println("Island splits when ocean rises "+ feet + " feet.");
}
t++;
}
}
}
///////////////// Painting
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int[][] matrix;
static int[] colors;
static int totalCases;
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 1; t <= T; t++) {
int n = sc.nextInt();
matrix = new int[n][n];
colors = new int[n];
totalCases = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
solve(0);
System.out.println("Case #" + t);
System.out.println(totalCases);
}
}
static void solve(int k) {
if (k == colors.length) {
totalCases++;
return;
}
for (int i = 1; i <= 4; i++) {
if (isValid(k, i)) {
colors[k] = i;
solve(k + 1);
colors[k] = 0;
}
}
}
static boolean isValid(int k, int color) {
for (int i = 0; i < colors.length; i++) {
if (colors[i] == color && matrix[k][i] == 1) {
return false;
}
}
return true;
}
}
///////////////// Pairing Parentheses
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
for (int tc = 1; tc <=10; tc++) {
int n = sc.nextInt();
String num = sc.next();
char s1 = '(';
char s2 = ')';
char s3 = '{';
char s4 = '}';
char s5 = '[';
char s6 = ']';
char s7 = '<';
char s8 = '>';
for (int j = 0; j < n; j++) {
int i = 0;
while(i<num.length()-1){
if (num.charAt(i) == s1 && s2 == num.charAt(i+1)) {
num = num.substring(0, i) + num.substring(i+2);
}else if (num.charAt(i) == s3 && s4 == num.charAt(i+1)) {
num = num.substring(0, i) + num.substring(i+2);
}else if (num.charAt(i) == s5 && s6 == num.charAt(i+1)) {
num = num.substring(0, i) + num.substring(i+2);
}else if (num.charAt(i) == s7 && s8 == num.charAt(i+1)) {
num = num.substring(0, i) + num.substring(i+2);
}
else
i++;
}
}
if (num.isEmpty()) {
System.out.println("#"+tc+" 1");
}
else
System.out.println("#"+tc+" 0");
}
}
}
/////////// Partition 1
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
static int a[];
static int T,N;
static void sort(){
int temp = a[0];
for (int i = 0; i < N-1; i++) {
for (int j = i+1; j < N; j++) {
if (a[i] < a[j]) {
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
a = new int[N];
int total = 0;
for (int i = 0; i < N; i++) {
a[i] = sc.nextInt();
total += a[i];
}
int time = 0;
while (N>1) {
sort();
// for (int i = 0; i < N; i++) {
// System.out.print(a[i]+" ");
// }
// System.out.println();
for (int i = 0; i < N; i++) {
a[N-2] = a[N-2]+a[N-1];
time = time + a[N-2];
N--;
break;
}
// System.out.println(time);
}
// time = time - a[N-1];
System.out.println("Case #"+tc);
System.out.println(time);
}
}
}
////////////// password
import java.util.Scanner;
public class Solution {
static int N;
static int[] Num;
public static void main(String args[]) throws Exception {
Scanner sc =new Scanner(System.in);
for (int tc = 1; tc <=10; tc++) {
int n = sc.nextInt();
String num = sc.next();
for (int j = 0; j < num.length(); j++) {
int i = 0;
while(i<num.length()-1){
if (num.charAt(i) == num.charAt(i+1)) {
num = num.substring(0, i) + num.substring(i+2);
}else
i++;
}
}
System.out.println("#"+tc+" "+num);
}
}
}
/////////////// Pha huy he thong dien
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
public class Main {
static int N;
static int arr[][];
static int answer;
static boolean visited[];
static class MyQueue {
int front, rear;
int arr[];
public MyQueue(int size) {
arr = new int[size];
rear = front = -1;
}
public void add(int item) {
rear++;
arr[rear] = item;
}
public int remove() {
return arr[++front];
}
public boolean isEmpty() {
return front == rear;
}
}
private static int[][] backUp() {
int tempArr[][] = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
tempArr[i][j] = arr[i][j];
return tempArr;
}
private static int demSoVung(int tempArr[][]) {
int soVung = 0;
visited = new boolean[N];
for (int i = 0; i < N; i++) {
if (!visited[i]) {
BFS(i, tempArr);
soVung++;
}
}
return soVung;
}
static void BFS(int start, int tempArr[][]) {
MyQueue q = new MyQueue(N);
visited[start] = true;
q.add(start);
while (!q.isEmpty()) {
int v = q.remove();
for (int i = 0; i < N; i++) {
if (tempArr[v][i] == 1 && !visited[i]) {
visited[i] = true;
q.add(i);
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T+2; tc++) {
if(sc.hasNextInt()){
N = sc.nextInt();
arr = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
arr[i][j] = sc.nextInt();
}
}
int tempArr[][] = backUp();
int max = 2;
answer = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
if (tempArr[i][j] == 1) {
tempArr[i][j] = 0;
tempArr[j][i] = 0;
}
}
if (demSoVung(tempArr) > max) {
max = demSoVung(tempArr);
answer = i + 1;
}
tempArr = backUp();
}
System.out.println(answer);
}
}
}
}
/////////////// picking up jewels
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
public class Main {
public static int max_res, res;
public static int a[][];
public static boolean visited[][];
public static int n;
static int rspin[] = {0,0,1,-1};
static int cspin[] = {1,-1,0,0};
static void check(int i, int j){
// System.out.println(i+" "+j+"-----");
if (a[i][j] == 2) {
res += 1;
}
visited[i][j] = true;
if (i == n-1 && j == n-1) {
max_res = max_res > res ? max_res : res;
// System.out.println(max_res+" "+res);
}
for (int k = 0; k < 4; k++) {
int newr = i + rspin[k];
int newc = j + cspin[k];
if (newr >= 0 && newr < n && newc >= 0 && newc < n && a[newr][newc] != 1 && visited[newr][newc] == false) {
check(newr, newc);
}
}
if (a[i][j] == 2) {
res -= 1;
}
visited[i][j] = false;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
int T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
n = sc.nextInt();
a = new int[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
//slve
max_res = res = 0;
check(0, 0);
System.out.println(max_res);
}
}
}
///////////// Point of balance 2
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static int T,N;
static double[] arrX;
static double[] mass;
static double [] res;
static double tmp;
public static double forceleft(double x, double mid){
double sum = 0;
for(int i = 0; i <= x; i++){
sum += mass[i] / ((mid - arrX[i]) * (mid - arrX[i]));
}
return sum;
}
public static double forceright(double y, double mid){
double sum = 0;
for(int i = N - 1; i >= y; i--){
sum += mass[i] / ((arrX[i] - mid) * (arrX[i] - mid));
}
return sum;
}
public static double cal(double x, double y){
if(x > y){
return x - y;
}else{
return y - x;
}
}
public static double binarySearch(double x, double y, int i){
tmp = 0;
while(x <= y){
double mid = (y + x) / 2;
if(cal(tmp, mid) <= 0.000000001) return mid;
double l = forceleft(i, mid);
double r = forceright(i + 1, mid);
if(l == r){
return mid;
}else{
if(l > r){
x = mid;
}else{
y = mid;
}
}
tmp = mid;
}
return tmp;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
for (int tc = 1; tc <=10; tc++) {
N = sc.nextInt();
arrX = new double[N];
mass = new double[N];
res = new double[N];
for (int i = 0; i < N; i++) {
int a = sc.nextInt();
arrX[i] = (double) a;
}
for (int i = 0; i < N; i++) {
int b = sc.nextInt();
mass[i] = (double) b;
}
double ans;
for(int i = 0; i < N - 1; i++){
ans = binarySearch(arrX[i], arrX[i + 1], i);
res[i] = ans;
}
System.out.print("#"+tc +" ");
for(int i = 0; i < N - 1; i++){
System.out.printf("%.10f ",res[i]);
}
System.out.println();
}
}
}
//////////////// Princess
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
static int arr[][];
static int T,n, cr, cc, nr, nc, xP, yP;
static boolean visited[][];
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[100000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rqueue = new Queue();
static Queue cqueue = new Queue();
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
n = sc.nextInt();
arr = new int[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
visited[i][j] = false;
if (arr[i][j] == 2) {
xP = i;
yP = j;
}
}
}
rqueue.reset();
cqueue.reset();
rqueue.enQueue(xP);
cqueue.enQueue(yP);
visited[xP][yP] = true;
while (!rqueue.isEmpty()) {
cr = rqueue.deQueue();
cc = cqueue.deQueue();
for(int i = 0; i < 4; i++){
nr = cr + dx[i];
nc = cc + dy[i];
if(nr >= 0 && nr < n && nc >= 0 && nc < n && arr[nr][nc] == 1 && visited[nr][nc] == false){
arr[nr][nc] = arr[cr][cc] + 1;
rqueue.enQueue(nr);
cqueue.enQueue(nc);
visited[nr][nc] = true;
}
}
}
int res;
if(arr[0][0] > 1 && arr[n-1][n-1] > 1){
res = arr[0][0] + arr[n-1][n-1] - 4;
System.out.println(res);
}else{
System.out.println("-1");
}
}
//
}
}
/////////////// Qua cau
import java.util.Scanner;
class Location {
public int r;
public int c;
public Location(int r, int c) {
this.r = r;
this.c = c;
}
}
public class Solution {
public static int[] dr = { -1, -1, -1 };
public static int[] dc = { -1, 0, 1 };
public static int[][] map = new int[30][5];
public static int N = 0;
public static Location[] lothung = new Location[100];
public static int sizeLo = 0;
public static int result = 0;
public static void backtracking(int r, int c, int sum) {
if (r == 0) {
result = result > sum ? result : sum;
return;
}
for (int i = 0; i < 3; i++) {
int newR = r + dr[i];
int newC = c + dc[i];
if (newR >= 0 && newR < N && newC >= 0 && newC < 5) {
if (map[newR][newC] == 0) {
backtracking(newR, newC, sum);
} else if (map[newR][newC] == 1) {
backtracking(newR, newC, sum + 1);
}
}
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
sizeLo = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 5; j++) {
map[i][j] = sc.nextInt();
if (map[i][j] == 2) {
lothung[sizeLo] = new Location(i, j);
sizeLo++;
}
}
}
result = -1;
for (int i = 0; i < sizeLo; i++) {
map[lothung[i].r][lothung[i].c] = 0;
backtracking(N, 2, 0);
map[lothung[i].r][lothung[i].c] = 2;
}
System.out.println("#" + tc + " " + result);
}
}
}
#include <iostream>
using namespace std;
int T, N, arr[25][5], cell[25][2], sizeOfCell, res;
bool visit[25][5];
int dx[3] = {-1, -1, -1};
int dy[3] = {-1, 0, 1};
void backtracking(int row, int col, int sum) {
if(row == 0) {
res = res > sum ? res : sum;
return;
}
for(int i = 0; i < 3; i++) {
int newX = row + dx[i];
int newY = col + dy[i];
if(newX >= 0 && newX < N && newY >= 0 && newY < 5 && !visit[newX][newY] && arr[newX][newY] < 2) {
visit[newX][newY] = true;
int tmp = 0;
if(arr[newX][newY] == 1) tmp = 1;
backtracking(newX, newY, sum + tmp);
visit[newX][newY] = false;
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
cin >>T;
for(int t = 1; t <= T; t++) {
cin >>N;
sizeOfCell = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < 5; j++) {
cin >>arr[i][j];
visit[i][j] = false;
if(arr[i][j] == 2) {
cell[sizeOfCell][0] = i;
cell[sizeOfCell][1] = j;
sizeOfCell++;
}
}
}
// solve:
// Danh dau vi tri o trong chen van:
res = -1;
for(int i = 0; i < sizeOfCell; i++) {
int index1 = cell[i][0], index2 = cell[i][1];
arr[index1][index2] = -1;
backtracking(N, 2, 0);
arr[index1][index2] = 2;
}
cout <<"#" <<t <<" " <<((res == -1) ? -1: res) <<endl;
}
return 0;
}
/////////////// Quan ma
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
static int T, N, M;
static int arr[][];
static int posX[];
static int posY[];
static int visited[][];
static int check[];
static int init[][];
int cnt;
static int map[][];
static int k;
static int ans, minA;
static int x, y;
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
static Queue rqueue = new Queue();
static Queue cqueue = new Queue();
public static void backtrack(int n, int tmp){
if(ans >= minA){
return;
}
if(tmp == k){
if(ans < minA)
minA = ans;
return;
}
for(int i = 1; i < k; i++){
if(map[n][i] != 0 && check[i] == 0 ){
ans += map[n][i];
check[i] = 1;
backtrack(i, tmp + 1);
ans -= map[n][i];
check[i] = 0;
}
}
}
static void BFS(int x, int y){
int a = posX[x];
int b = posY[x];
int c = posX[y];
int d = posY[y];
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
visited[i][j] = 0;
init[i][j] = arr[i][j];
}
}
rqueue.reset();
cqueue.reset();
init[a][b] = 0;
visited[a][b] = 1;
rqueue.enQueue(a);
cqueue.enQueue(b);
int flag;
while(rqueue.isEmpty() == false){
flag = 0;
int x1 = rqueue.deQueue();
int y1 = cqueue.deQueue();
for(int i = 0; i < 8; i++){
int row = x1 + dx[i];
int col = y1 + dy[i];
if(row >= 0 && row < N && col >= 0 && col < M && visited[row][col] == 0 && init[row][col] != 2){
if(row == c && col == d){
init[row][col] = init[x1][y1] + 1;
map[x][y] = init[row][col];
map[y][x] = init[row][col];
flag = 1;
break;
}else{
init[row][col] = init[x1][y1] + 1;
visited[row][col] = 1;
rqueue.enQueue(row);
cqueue.enQueue(col);
}
}
if(flag == 1){
break;
}
}
if(flag == 1){
break;
}
}
if(init[c][d] == -1 || init[c][d] == -3){
map[x][y] = 0;
map[y][x] = 0;
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt(); // number of test cases
for (int t = 1; t <= T; t++) {
N = scanner.nextInt(); // number of rows
M = scanner.nextInt(); // number of columns
arr = new int[N][M]; // room layout
visited = new int[N][M];
int count = 0;
// Read room layout
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
arr[i][j] = scanner.nextInt();
if (arr[i][j] == 3) {
x = i;
y = j;
arr[i][j] = -3;
}
if (arr[i][j] == 1) {
count++;
}
}
}
check = new int[count+1];
init = new int[N][M];
map = new int[count+1][count+1];
posX = new int[count+1];
posY = new int[count+1];
posX[0] = x;
posY[0] = y;
k = 1;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(arr[i][j] == 1){
arr[i][j] = -1;
posX[k] = i;
posY[k] = j;
k++;
}
}
}
for(int i = 0; i < k - 1; i++){
for(int j = i + 1; j < k; j++){
BFS(i, j);
}
}
for(int i = 0; i < k; i++){
check[i] = 0;
}
ans = 0;
minA = 1000000;
backtrack(0, 1);
System.out.println("Case #" + t);
if (minA == 1000000) {
System.out.println("-1");
}else
System.out.println(minA);
}
}
}
//////////////// Queue
public static class Queue{
int Data[];
int front, rear;
public Queue(){
Data = new int[1000];
this.front = this.rear = -1;
}
// check if the queue is full
public void reset() {
this.front = this.rear = -1;
}
// check if the queue is empty
public boolean isEmpty() {
if (this.front == this.rear)
return true;
else
return false;
}
// insert elements to the queue
public void enQueue(int value) {
Data[++rear] = value;
}
// delete element from the queue
public int deQueue() {
return Data[++front];
}
}
public static Queue rQueue = new Queue();
public static Queue cQueue = new Queue();
////////////// Quick Sort
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,
// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// To print sorted array
public static void printArr(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.length;
// Function call
quickSort(arr, 0, N - 1);
System.out.println("Sorted array:");
printArr(arr);
}
}
//////////// Route Find (tim duong di tu A den B)
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
public static boolean dfs(int node,int a[][]){
if (node == 99) {
return true;
}
for (int i = 0; i < 2; i++) {
int nexnode = a[node][i];
if (nexnode != 0 && dfs(nexnode, a)) {
return true;
}
}
return false;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// int T = sc.nextInt();
// TODO Auto-generated method stub
for (int tc = 1; tc <= 10; tc++) {
int K = sc.nextInt();
int N = sc.nextInt();
int a[][] = new int[100][2];
boolean visited[] = new boolean[100];
for (int i = 0; i < N; i++) {
int aa = sc.nextInt();
int bb = sc.nextInt();
a[aa][i%2] = bb;
}
boolean check = dfs(0, a);
System.out.print("#"+tc);
if (check) {
System.out.println(" 1");
}
else
System.out.println(" 0");
}
}
}
/////////// Score
import java.util.Scanner;
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
static int A[][];
static int T,N,S,K;
static int result;
public static int check(int ck, int total,int previous){
if (ck == K) {
if (total == S) {
result ++;
return 0;
}
}
else{
for (int t = 0; t < N; t++) {
if (A[t][ck] >= previous && total + A[t][ck] <= S) {
check(ck+1, total + A[t][ck], A[t][ck]);
}
}
return 0;
}
return 0;
}
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
S = sc.nextInt();
K = sc.nextInt();
N = sc.nextInt();
A = new int[N][K];
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
A[i][j] = sc.nextInt();
}
}
result = -1;
check(0, 0, 0);
System.out.println("Case " + tc);
if (result == -1) {
System.out.println("-1");
}
else
System.out.println(result+1);
}
}
}
////////////// Sinh hoan vi
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
public static void generate(int arr[],boolean[] used, int n, int index){
if (index == n) {
for (int num : arr) {
System.out.print(num+" ");
}
System.out.println();
return;
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
arr[index] = i;
used[i] = true;
generate(arr, used, n, index+1);
used[i] = false;
}
}
}
public static void main(String[] args) throws FileNotFoundException {
// System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
int T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
int n = sc.nextInt();
int[] arr = new int[n];
boolean[] used = new boolean[n+1];
for (int i = 0; i < n; i++) {
arr[i] = i+1;
}
generate(arr, used, n, 0);
}
}
}
//////////// Sinh to hop
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
public static void generate(int arr[], int start ,int n, int index, int k){
if (index == k) {
for (int num : arr) {
System.out.print(num+" ");
}
System.out.println();
return;
}
for (int i = start; i <= n; i++) {
arr[index] = i;
generate(arr, i+1, n, index+1, k);
}
}
public static void main(String[] args) throws FileNotFoundException {
// System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
int T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[k];
generate(arr, 1, n, 0, k);
}
}
}
////////////// Sky Force
import java.util.Scanner;
public class Solution {
static int t,n,re;
static int[][] a;
static int[][] visited;
static int[] dy = {-1, 0 , 1};
static boolean hasTrue;
static boolean hasBoom;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t =sc.nextInt();
for (int i = 0; i < t; i++) {
hasTrue = false;
hasBoom = true;
re = 0;
n = sc.nextInt();
a = new int[n][5];
visited = new int[n][5];
for (int j = 0; j < n; j++) {
for (int k = 0; k < 5; k++) {
a[j][k] =sc.nextInt();
}
}
fun(n-1,2,0);
System.out.println("Case #" + (i+1));
if(hasTrue) {
System.out.println(re);
}
else {
System.out.println(-1);
}
// boom(3);
// for (int j = 0; j < n; j++) {
// for (int k = 0; k < 5; k++) {
// System.out.print(a[j][k] + " ");
// }
// System.out.println();
// }
// unboom(3);
// for (int j = 0; j < n; j++) {
// for (int k = 0; k < 5; k++) {
// System.out.print(a[j][k] + " ");
// }
// System.out.println();
// }
}
}
public static void fun(int i, int j, int score) {
if(score <0) {
return;
}
if( i == -1) {
hasTrue = true;
if(re < score)
re = score;
}
else {
if(hasBoom) {
hasBoom = false;
boom(i);
fun(i, j,score);
unboom(i);
hasBoom = true;
}
//di chuyen
for (int k = 0; k < 3; k++) {
int y = dy[k] + j;
if(y >= 0 && y < 5) {
visited[i][y] = 1;
//keo map len
if(a[i][y] == 2) {
fun(i-1, y,score - 1);
}else if(a[i][y] == 1) {
//System.out.println("i" + i + " y" + y);
fun(i-1, y,score + 1);
}else {
fun(i-1, y,score);
}
}
}
}
}
static void boom(int i) {
int st = i-4 <= 0? 0: i - 4;
for (int j = st; j <= i; j++) {
for (int k = 0; k < 5; k++) {
if(a[j][k] == 2) {
a[j][k] = -1;
}
}
}
}
static void unboom(int i) {
int st = i-4 <= 0? 0: i - 4;
for (int j = st; j <= i; j++) {
for (int k = 0; k < 5; k++) {
if(a[j][k] == -1) {
a[j][k] = 2;
}
}
}
}
}
////////////// Sky map
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
static int arr[][];
static int T,n, res, max_res;
static boolean visited[][];
private static class Stack{
private int[] elements;
private int top;
public Stack(int size) {
elements = new int[size];
top = -1;
}
public void reset() {
top = -1;
}
public void push(int element) {
elements[++top] = element;
}
public int pop() {
return elements[top--];
}
public boolean isEmpty() {
return top == -1;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return elements[top];
}
public int getTop(){
return top;
}
}
static Stack stack = new Stack(1000);
public static void check(int x, int y){
visited[x][y] = true;
for(int i = 0; i < 4; i++){
int r = x + dx[i];
int c = y + dy[i];
if(r >= 0 && r < n && c >= 0 && c < n && arr[r][c] == 1 && visited[r][c] == false){
visited[r][c] = true;
stack.push(1);
check(r, c);
}
}
max_res = (max_res > stack.getTop()) ? max_res : stack.getTop();
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
n = sc.nextInt();
arr = new int[n][n];
visited = new boolean[n][n];
res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
visited[i][j] = false;
}
}
max_res = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 1 && visited[i][j] == false) {
stack.reset();
stack.push(1);
cnt++;
check(i, j);
}
}
}
System.out.println(cnt+" "+(max_res+1));
//
}
}
}
////////////// Stack
private static class Stack{
private int[] elements;
private int top;
public Stack(int size) {
elements = new int[size];
top = -1;
}
public void reset() {
top = -1;
}
public void push(int element) {
elements[++top] = element;
}
public int pop() {
return elements[top--];
}
public boolean isEmpty() {
return top == -1;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return elements[top];
}
public int getTop(){
return top;
}
}
/////////// Stock Exchange (co phieu)
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
public class Main {
static int arr[];
static int T;
static boolean check(int n){
boolean check = false;
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n; j++) {
if (arr[i] > arr[j]) {
check = true;
}
else{
check = false;
break;
}
}
if (check == false) {
break;
}
}
if (check == true) {
return true;
}
else
return false;
}
static int maxStock(int n){
int maxStock = 0;
int imax = 0;
for (int i = 0; i < n; i++) {
if (maxStock == arr[i]) {
imax = i;
}
else if (maxStock < arr[i]) {
maxStock = arr[i];
imax = i;
}
}
return imax;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
int n = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
if (check(n) == true) {
System.out.println("#"+tc+" 0");
}
else{
int max =0;
if (arr[n-1] < arr[n-2]) {
arr[n-1] = 0;
}
for (int j = 0; j < n; j++) {
int maxst = 0;
int s = maxStock(n);
if (s == j) {
arr[s] = 0;
}
int count = 0;
// System.out.println(arr[s]+" "+maxst);
for (int i = 0; i < s; i++) {
if (arr[i] != 0) {
maxst += arr[i];
arr[i] = 0;
count++;
}
}
// for (int i = 0; i < n; i++) {
// System.out.print(arr[i]+" ");
// }
// System.out.println();
// System.out.println(maxst);
// System.out.println("count: " +count);
if (count>0) {
max = max + arr[s]*count - maxst;
}
// System.out.println("max: "+max);
arr[s] = 0;
}
System.out.println("#"+tc+" "+max);
}
}
// System.out.println("Case #"+tc);
// System.out.println(maxprize);
}
}
/////// tan cong thanh tri
#include <iostream>
using namespace std;
int N;
int arr[101][101];
int gun[101];
int visit[101], check;
int ans;
void DFS(int curV, int strV, int preV, int min, int num1, int num2) {
visit[curV] = true;
for (int i = 0; i < N; i++) {
if (i != preV && arr[curV][i] == 1 && !check) {
int sumGun = gun[curV] + gun[i];
if (visit[i] && i == strV) {
if (min < sumGun) {
ans += min;
arr[num2][num1] = 0;
arr[num1][num2] = 0;
} else {
ans += sumGun;
arr[curV][i] = 0;
arr[i][curV] = 0;
}
check = true;
return;
}
if (!visit[i]) {
if (min < sumGun) {
DFS(i, strV, curV, min, num1, num2);
} else {
DFS(i, strV, curV, sumGun, curV, i);
}
}
}
}
}
int main() {
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
arr[i][j] = 0;
}
}
int v, w, cnt;
for (int i = 0; i < N; i++) {
cin >> v;
cin >> gun[v] >> cnt;
for (int j = 0; j < cnt; j++) {
cin >> w;
arr[v][w] = 1;
}
}
ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visit[j] = false;
}
check = false;
DFS(i, i, i, 1500000, i, i);
if (check) {
i--;
}
}
cout << "Case #" << tc << endl << ans << endl;
}
return 0;
}
////// Tat den
import java.util.Scanner;
public class Solution {
static int t,m,n,re;
static int[] hv;
static int[] a;
static int[][] light;
static int t,m,n,re;
static int[] hv;
static int[] a;
static int[][] light;
static void backtrack(int h, int k, int n){
for (int i = hv[h-1] + 1; i <= n - (k-h); i++){
hv[h] = i;
if (h == k){
for (int j = 1; j <= k; j++) {
turnOff(hv[j]);
}
int lights = getLightOff();
if(lights> re)
re = lights;
for (int j = 1; j <= k; j++) {
turnOff(hv[j]);
}
// printArray(hv, k);
}
else {
backtrack(h+1, k, n);
}
}
}
static int[] getLight(int khoa){
int cnt = -1;
int stt = 0;
while(stt <= m){
cnt ++;
stt = khoa + cnt * (khoa + 1);
}
int[] arr = new int[cnt];
for (int i = 0; i < arr.length; i++) {
arr[i] = khoa + i * (khoa + 1);
}
return arr;
}
static void turnOff(int khoa){
for (int i = 0; i < light[khoa-1].length; i++) {
a[light[khoa-1][i] - 1] = 1 - a[light[khoa-1][i] - 1];
}
}
static int getLightOff(){
int re = 0;
for (int i = 0; i < m; i++) {
if(a[i] == 0)
re ++;
}
return re;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t =sc.nextInt();
for (int i = 0; i < t; i++) {
m = sc.nextInt();
n = sc.nextInt();
hv = new int[n + 1];
a = new int[m];
for (int j = 0; j < m; j++) {
a[j] = sc.nextInt();
}
re = getLightOff();
light = new int[n][];
for (int j = 0; j < n; j++) {
light[j] = getLight(j +1);
}
// turnOff(1);
dequy(1, 3, n);
hv = new int[n + 1];
dequy(1, 2, n);
hv = new int[n + 1];
dequy(1, 1, n);
System.out.println("#" + (i+1) + " " + re);
}
}
}
//////// The frog
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
static int T, N;
static int arr[][];
static int radius[][];
static int X[];
static int Y[];
static int R[];
static int key[];
static int visited[];
public static int cal1(int i, int j){
int res;
res = (X[i] - X[j])*(X[i] - X[j]) + (Y[i] - Y[j])*(Y[i]-Y[j]);
return res;
}
public static int cal2(int i, int j){
int res;
res = R[i] + R[j];
return res;
}
public static int minValue(int a, int b){
if(a < b)
return a;
return b;
}
public static void Dijkstra(int s){
for(int i = 0; i < N; i++){
key[i] = arr[s][i];
}
for(int cnt = 0; cnt < N - 1; cnt++){
visited[s] = 1;
int res = 1000000000;
int index = 0;
for(int i = 0; i < N; i++){
if(key[i] < res && visited[i] == 0){
res = key[i];
index = i;
}
}
for(int i = 0; i < N; i++){
if(arr[index][i] != 0)
key[i] = minValue(key[i],key[index] + arr[index][i]);
}
s = index;
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
arr = new int[201][201];
radius = new int[201][201];
X = new int[201];
Y = new int[201];
R = new int[201];
key = new int[201];
visited = new int[201];
for (int i = 0; i < N; i++) {
X[i] = sc.nextInt();
Y[i] = sc.nextInt();
R[i] = sc.nextInt();
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
arr[i][j] = cal1(i, j);
radius[i][j] = cal2(i, j);
if(arr[i][j] <= (radius[i][j] + 40) * (radius[i][j] + 40) && i != j){
arr[i][j] = 1;
}else
if(arr[i][j] > (radius[i][j] + 40) * (radius[i][j] + 40) && arr[i][j] <= (radius[i][j] + 90) * (radius[i][j] + 90)){
arr[i][j] = 200;
}else if(i == j){
arr[i][j] = 0;
}
else{
arr[i][j] = 1000000000;
}
}
}
for(int i = 0; i < N; i++){
visited[i] = 0;
key[i] = 1000000000;
}
int ans1 = 0;
int ans2 = 0;
int check = 0;
Dijkstra(0);
ans1 = key[N - 1]/ 200;
ans2 = key[N - 1] % 200;
if(key[N - 1] >= 1000000000){
System.out.println(-1);
}
else {
System.out.println(ans1+" "+ans2);
}
}
}
}
/////////// The settlers of Canta
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import javax.naming.spi.DirStateFactory.Result;
public class Main {
static int A[][];
static int T,N,M;
static int x,y;
static int edgeS[],edgeE[];
static int cMax;
public static int backTrack(int idx, int cnt){
if(cnt > cMax)
cMax = cnt;
for(int i = 0; i < M; i++){
if(edgeS[i] == idx){
int t1, t2;
t1 = edgeS[i];
t2 = edgeE[i];
edgeS[i] = -1;
edgeE[i] = -1;
backTrack(t2, cnt + 1);
edgeS[i] = t1;
edgeE[i] = t2;
}
else if(edgeE[i] == idx){
int t1, t2;
t1 = edgeS[i];
t2 = edgeE[i];
edgeS[i] = -1;
edgeE[i] = -1;
backTrack(t1, cnt + 1);
edgeS[i] = t1;
edgeE[i] = t2;
}
}
return 0;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
N = sc.nextInt();
M = sc.nextInt();
edgeS = new int[M];
edgeE = new int[M];
for (int i = 0; i < M; i++) {
edgeS[i] = sc.nextInt();
edgeE[i] = sc.nextInt();
}
cMax = 0;
for(int i = 0; i < N; i++){
backTrack(i, 0);
}
// System.out.println("Case #" + tc);
System.out.println(cMax);
}
}
}
/////////////// Tuan trang mat
#include <iostream>
using namespace std;
const int MAXN = 1000;
const int MAXK = 15;
const long long INF = 1e18;
long long dist[MAXN][MAXN], dp[1 << MAXK][MAXK];
int s[MAXK];
void floydWarshall(int n) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
long long findMinCost(int n, int m, int k) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = (i == j ? 0 : INF);
for (int i = 0; i < m; i++) {
int u, v;
long long c;
cin >> u >> v >> c;
dist[u-1][v-1] = c;
}
floydWarshall(n);
for (int i = 0; i < (1 << k); i++)
for (int j = 0; j < k; j++)
dp[i][j] = INF;
for (int i = 0; i < k; i++)
dp[1 << i][i] = dist[0][s[i]];
for (int mask = 0; mask < (1 << k); mask++) {
for (int i = 0; i < k; i++) {
if (mask & (1 << i)) {
for (int j = 0; j < k; j++) {
if (!(mask & (1 << j))) {
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],
dp[mask][i] + dist[s[i]][s[j]]);
}
}
}
}
}
long long result = INF;
for (int i = 0; i < k; i++)
result = min(result, dp[(1 << k) - 1][i] + dist[s[i]][0]);
return (result >= INF ? -1 : result);
}
int main() {
int T;
//freopen("input.txt","r",stdin);
cin >> T;
for (int tc = 0; tc < T; tc++)
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < k; i++) {
cin >> s[i];
s[i]--;
}
cout << "Case #" << tc+1 << " \n" << findMinCost(n, m, k) << endl;
}
return 0;
}
////////////////// Turn Over Game
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt(); // s� lượng test case
for (int i = 1; i <= t; i++) {
char[][] table = new char[4][4];
// nháºp bảng
for (int j = 0; j < 4; j++) {
String row = scanner.next();
table[j] = row.toCharArray();
}
int minOperations = findMinOperations(table);
System.out.println("Case #"+i);
if (minOperations == -1) {
System.out.println("impossible");
} else {
System.out.println(minOperations);
}
}
scanner.close();
}
private static int findMinOperations(char[][] table) {
int minOperations = Integer.MAX_VALUE;
// thỠtất cả các phép biến ��i có th�
for (int mask = 0; mask < (1 << 16); mask++) {
char[][] copyTable = copyTable(table);
int operations = 0;
// áp dụng phép biến ��i và o bảng
for (int i = 0; i < 16; i++) {
if ((mask & (1 << i)) != 0) {
int row = i / 4;
int col = i % 4;
flipColor(copyTable, row, col);
operations++;
}
}
// ki�m tra xem tất cả các viên �á có cùng mà u hay không
boolean allWhite = true;
boolean allBlack = true;
for (int row = 0; row < 4; row++) {
for (int col = 0; col < 4; col++) {
if (copyTable[row][col] == 'b') {
allWhite = false;
} else {
allBlack = false;
}
}
}
// cáºp nháºt sá»� lượng phép biến Ä�á»�i tá»�i thiá»�u
if (allWhite || allBlack) {
minOperations = Math.min(minOperations, operations);
}
}
if (minOperations == Integer.MAX_VALUE) {
return -1; // không th� thay ��i �ược
}
return minOperations;
}
private static void flipColor(char[][] table, int row, int col) {
if (table[row][col] == 'b') {
table[row][col] = 'w';
}
else {
table[row][col] = 'b';
}
for (int[] dir : DIRECTIONS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow >= 0 && newRow < 4 && newCol >= 0 && newCol < 4) {
if (table[newRow][newCol] == 'b') {
table[newRow][newCol] = 'w';
}
else {
table[newRow][newCol] = 'b';
}
}
}
}
private static char[][] copyTable(char[][] table) {
char[][] copy = new char[4][4];
for (int i = 0; i < 4; i++) {
System.arraycopy(table[i], 0, copy[i], 0, 4);
}
return copy;
}
}
////////////////// Uniform Distribution in Square
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
static int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
static int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
static boolean duyet(int r, int c, int n, int map[][]) {
//0
if ((r+dx[0]) > 0 && (r+dx[0]) < n && (c+dy[0]) > 0 && (c+dy[0]) < n) {
if (map[r][c] == map[dx[0]+r][dy[0]+c]) {
if (map[r+dx[1]][(c+dy[1])] == map[r][c] || map[r+dx[7]][(c+dy[7])] == map[r][c]) {
return true;
}
else
return false;
}
}else
//2
if ((r+dx[2]) > 0 && (r+dx[2]) < n && (c+dy[2]) > 0 && (c+dy[2]) < n) {
if (map[r][c] == map[dx[2]+r][dy[2]+c]) {
if (map[r+dx[1]][(c+dy[1])] == map[r][c] || map[r+dx[3]][(c+dy[3])] == map[r][c]) {
return true;
}
else
return false;
}
}else
//4
if ((r+dx[4]) > 0 && (r+dx[4]) < n && (c+dy[4]) > 0 && (c+dy[4]) < n) {
if (map[r][c] == map[dx[4]+r][dy[4]+c]) {
if (map[r+dx[5]][(c+dy[5])] == map[r][c] || map[r+dx[3]][(c+dy[3])] == map[r][c]) {
return true;
}
else
return false;
}
}
//6
else if((r+dx[6]) > 0 && (r+dx[6]) < n && (c+dy[6]) > 0 && (c+dy[6]) < n) {
if (map[r][c] == map[dx[6]+r][dy[6]+c]) {
if (map[r+dx[5]][(c+dy[5])] == map[r][c] || map[r+dx[7]][(c+dy[7])] == map[r][c]) {
return true;
}
else
return false;
}
}
return true;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("input1.txt"));
Scanner sc = new Scanner(System.in);
// TODO Auto-generated method stub
int T = sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
int n = sc.nextInt();
int map[][] = new int[n][n];
int a[][] = new int [n-1][n*2];
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n*2; j++) {
a[i][j] = sc.nextInt();
}
}
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n*2; j+=2) {
// System.out.println(a[i][j]+" "+a[i][j+1]);
map[a[i][j]-1][a[i][j+1]-1] = i+1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(map[i][j] == 0){
map[i][j] = n;
}
}
}
// for (int i = 0; i < n-1; i++) {
// for (int j = 0; j < n*2; j++) {
// System.out.print(a[i][j]+" ");
// }
// System.out.println();
// }
// System.out.println("-------------");
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// System.out.print(map[i][j]+" ");
// }
// System.out.println();
// }
// System.out.println("-------------");
boolean isUniform = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
isUniform = duyet(i, j, n, map);
if (isUniform == false) {
break;
}
else
continue;
}
if (isUniform == false) {
break;
}
}
if (isUniform) {
System.out.println("Case #"+tc);
System.out.println("good");
}
else{
System.out.println("Case #"+tc);
System.out.println("wrong");
}
}
}
}
///////////// Visit departments
import java.util.Scanner;
public class Solution {
public static float[][] Time = new float[101][101];
public static float[][] matrix = new float[101][101];
public static int N = 0;
public static int E = 0;
public static int K = 0;
public static int T = 0;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
for (int tc = 1; tc <= 10; tc++) {
N = sc.nextInt();
E = sc.nextInt();
K = sc.nextInt();
T = sc.nextInt();
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
matrix[i][j] = 0f;
}
}
for (int i = 0; i < E; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
matrix[start][end] = sc.nextFloat();
}
// for (int i = 0; i <= N; i++) {
// for (int j = 0; j <= N; j++) {
// System.out.print(matrix[i][j] + " ");
// }
// System.out.println();
// }
// System.out.println();
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= T/10; j++) {
Time[i][j] = 0f;
}
}
Time[1][0] = 1f;
// for (int i = 1; i <= N; i++) {
// for (int j = 0; j <= T/10; j++) {
// System.out.print(Time[i][j] + " ");
// }
// System.out.println();
// }
// System.out.println();
for (int t = 1; t <= T/10; t++) {
for (int i = 1; i <= N; i++) {
if (Time[i][t - 1] != 0) {
for (int j = 1; j <= N; j++) {
if (matrix[i][j] != 0) {
Time[j][t] += Time[i][t - 1] * matrix[i][j];
}
}
}
}
}
// for (int i = 1; i <= N; i++) {
// for (int j = 0; j <= T/10; j++) {
// System.out.print(Time[i][j] + " ");
// }
// System.out.println();
// }
int timeJ = T/10;
int timeK = (T - K)/10;
float maxJ = 0f;
float maxK = 0f;
int indexJ = 0;
int indexK = 0;
for (int i = 1; i <= N; i++) {
if (maxJ < Time[i][timeJ]) {
maxJ = Time[i][timeJ];
indexJ = i;
}
if (maxK < Time[i][timeK]) {
maxK = Time[i][timeK];
indexK = i;
}
}
System.out.print("#" + tc + " " + indexJ + " ");
System.out.printf("%.6f ", maxJ);
System.out.print(indexK + " ");
System.out.printf("%.6f ", maxK);
System.out.println();
}
}
}
Editor is loading...
Leave a Comment