# HoangLong2

user_9175993
plain_text
19 days ago
43 kB
26
Indexable
Never
```//HoangLong2
//Ban Bong Bay
import java.util.Scanner;

public class Solution {
static int[] map = new int[501];
static int N, score, maxScore;

public static void main(String[] args) throws Exception {
//System.setIn(new FileInputStream("w2_thus/banbongbay/input.txt"));
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();

for (int i = 0; i < N; i++) {
map[i] = sc.nextInt();
}

score = 0;
maxScore = 0;
backtrack(N, 0);

System.out.println("Case #" + tc);
System.out.println(maxScore);
}
sc.close();

}

private static void backtrack(int N, int score) {
int max = -1, curI = 0;
// dkkt
if (N == 0) {
maxScore = maxScore > score ? maxScore : score;
return;
}

if (N == 2) {
int temp = map[0];
if (map[0] < map[1]) {
temp = map[1];
}
backtrack(N - 2, score + 2 * temp);
}

if (N == 3) {
int temp = map[0] * map[2];
if (temp < map[1]) {
backtrack(N - 3, score + 3 * map[1]);
}
}

for (int i = 1; i < N - 1; i++) {
int temp = map[i - 1] * map[i + 1];
int save = map[i];

for (int j = i; j < N - 1; j++) {
map[j] = map[j + 1];
}

backtrack(N - 1, score + temp);

for (int j = N - 2; j > i; j--) {
map[j] = map[j - 1];
}
map[i] = save;
}
}
}
//Ho den
public class Test_1 {
static int T, numberWhole;
static int pointX[], pointY[], value[][], min;
static boolean visited[][];

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

public static void backTrack(int r, int c, int sumTime){
if(sumTime > min) return;

if(min > sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1])){
min = sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1]);
return;
}

for(int i = 1; i <= numberWhole; i++){
visited[value[i][0]][value[i][1]] = true;
visited[value[i][2]][value[i][3]] = true;

if(!visited[value[i][0]][value[i][1]]){
backTrack(value[i][2], value[i][3],
sumTime + value[i][4] + calculatePoint(r, value[i][0], c, value[i][1]));
}

if(!visited[value[i][2]][value[i][3]]){
backTrack(value[i][0], value[i][1],
sumTime + value[i][4] + calculatePoint(r, value[i][2], c, value[i][3]));
}

visited[value[i][0]][value[i][1]] = false;
visited[value[i][2]][value[i][3]] = false;

}
}

public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Test_1"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
numberWhole = scanner.nextInt();
pointX = new int[numberWhole+2];
pointY = new int[numberWhole+2];
pointX[0] = scanner.nextInt();
pointY[0] = scanner.nextInt();
pointX[numberWhole+1] = scanner.nextInt();
pointY[numberWhole+1] = scanner.nextInt();

value = new int[numberWhole+1][5];

for(int i = 1; i <= numberWhole; i++){
value[i][0] = scanner.nextInt();
value[i][1] = scanner.nextInt();
value[i][2] = scanner.nextInt();
value[i][3] = scanner.nextInt();
value[i][4] = scanner.nextInt();
}

visited = new boolean[1001][1001];
min = calculatePoint(pointX[0], pointX[numberWhole+1],
pointY[0], pointY[numberWhole+1]);

visited[pointX[0]][pointY[0]] = true;
backTrack( pointX[0], pointY[0], 0);
System.out.println("#" + tc + " " + min);

}
}

}
//Hugo ve nha
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoVeNha {
static int N;
static int gate[][];
static int res;
static int armyAtGate[], expAtGate[];

static void BT(int k, int cost){
if(k == N){
res = res < cost ? res : cost;
return;
}
if(cost > res)
return;

//Pass
BT(k+1, cost + gate[k][1]);

//Hire
armyAtGate[k] += gate[k][0];
BT(k+1, cost + gate[k][1]*2);
armyAtGate[k] -= gate[k][0];

//Combat
int total = 0;
int tmp_army[] = new int[21];
int tmp_exp[] = new int[21];
for(int i = 0; i < k; i++){
tmp_army[i] = armyAtGate[i];
tmp_exp[i] = expAtGate[i];

if(armyAtGate[i] > 0 && expAtGate[i] < 3){
total += armyAtGate[i];
}
}

int enermy = gate[k][0];
if(total < enermy)
return;

for(int i = 0; i < k; i++){
if(armyAtGate[i] <= 0 || expAtGate[i] >= 3)
continue;
int tmp_enermy = enermy;
enermy -= armyAtGate[i];
armyAtGate[i] -= tmp_enermy;
if(enermy <= 0)
break;
}

for(int i = 0; i < k; i++){
if(armyAtGate[i] > 0 || expAtGate[i] < 3)
expAtGate[i] += 1;
}

BT(k+1, cost);

for(int i = 0; i < k; i++){
armyAtGate[i] = tmp_army[i];
expAtGate[i] = tmp_exp[i];
}
}

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input_HugoVeNha.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
for(int t = 1; t <= T; t++){
N = sc.nextInt();
gate = new int[21][2];
for(int i = 0; i < N; i++){
gate[i][0] = sc.nextInt();
gate[i][1] = sc.nextInt();
}

//Solve
res = 999999;
armyAtGate = new int[21];
expAtGate = new int[21];
BT(0, 0);

System.out.println("#" + t + " " + res);
}
}
}
//Hugo thi chay
public class Solution {
static int m, d;
static int []gio, phut, nangLuong, time;
static int timeMin;

public static void backtrack(int k, int energy, int tg, int km){
if(tg > timeMin){
return;
}
if(energy <= 0){
return;
}
if(k >= 5){
return;
}
if(km <= 0){
if(tg < timeMin){
timeMin = tg;
}
return;
}

for(int j=0; j<2; j++){
if(j == 1){
backtrack(k+1, energy-nangLuong[k], tg + time[k], km-1);
backtrack(k, energy-nangLuong[k], tg + time[k], km-1);
}
else{
backtrack(k+1, energy, tg, km);
}
}
}

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("src/hugo_thi_chay/input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scanner = new Scanner(System.in);
int TC = scanner.nextInt();
for(int t=0; t<TC; t++){
m = scanner.nextInt();
d = scanner.nextInt();
gio = new int[5];
phut = new int[5];
nangLuong = new int[5];
time = new int[5];
for(int i=0; i<5; i++){
gio[i] = scanner.nextInt();
phut[i] = scanner.nextInt();
nangLuong[i] = scanner.nextInt();
}
for(int i=0; i<5; i++){
time[i] = gio[i] * 60 + phut[i];
}

timeMin = Integer.MAX_VALUE;
backtrack(0, m, 0, d);
System.out.println("Case #" + (t+1));
if(timeMin == Integer.MAX_VALUE){
System.out.println(-1);
}
else{
int resGio = timeMin / 60;
int resPhut = timeMin % 60;
System.out.println(resGio + " " + resPhut);
}

}
}
}
//Hugo giao hang
public class hugo_giao_hang {
static int hx, hy, sx, sy, n, Ans;
static int [][] arr, map;
static int [] visit;

static int distance(int i, int j) {
int a = arr[i][0] - arr[j][0];
int b = arr[i][1] - arr[j][1];
if (a < 0) a = 0 - a;
if (b < 0) b = 0 - b;
return a+b;
}

static void createMatrix() {
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
int x = distance(i, j);
map[i][j] = x;
}
}
}

static void Try(int x, int sum_distance, int count) {
if (count == n) {
sum_distance += map[x][n+1];
if (sum_distance < Ans) Ans = sum_distance;
return;
}
if (Ans < sum_distance) return;
for (int i = 1; i <= n; i++) {
if (visit[i] == 0) {
visit[i] = 1;
Try(i, sum_distance + map[x][i], count+1);
visit[i] = 0;
}
}
}

public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("D://Trainee//SRV_training//src//Hugo_Giao_Hang//giao_hang.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
sx = sc.nextInt();
sy = sc.nextInt();
hx = sc.nextInt();
hy = sc.nextInt();
n = sc.nextInt();
arr = new int [n+2][2];
for(int i = 1; i < n+1; i++) {
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
arr[0][0] = sx;
arr[0][1] = sy;
arr[n+1][0] = hx;
arr[n+1][1] = hy;
map = new int [n+2][n+2];
createMatrix();
Ans = 1000000000;
visit = new int [n+2];
visit[0] = 1;
Try(0, 0, 0);

System.out.println("Case #" + test_case + " " + Ans);
}
}
}
//hugo xep lich
public class xep_quang_cao {
static int N, res, start, end;
static int[][] guestTime;
static int[][] score = new int[3][55];
static int[] L = new int[3];
static int[] P = new int[3];

public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("w4_fri/xep_quang_cao/input.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
for (int i = 0; i < 3; i++) {
L[i] = sc.nextInt();
}
for (int i = 0; i < 3; i++) {
P[i] = sc.nextInt();
}
guestTime = new int[N][2];

for (int i = 0; i < N; i++) {
guestTime[i][0] = sc.nextInt();
guestTime[i][1] = sc.nextInt() + guestTime[i][0];
}
start = guestTime[0][0];
end = guestTime[0][1];
for (int i = 1; i < N; i++) {
if (start > guestTime[i][0]) {
start = guestTime[i][0];
}
if (end < guestTime[i][1]) {
end = guestTime[i][1];
}
}
res = -1;

backtrack(0);

System.out.println("Case #" + tc);
System.out.println(res);
}
}

private static boolean checkVisit(int start, int end) {
for (int i = start; i < end; i++) {
return false;
}
return true;
}

private static void visit(int start, int end, int visit) {
for (int i = start; i < end; i++) {
}
}

private static void backtrack(int k) {
if (k == 3) {
int count = sum();
res = count > res ? count : res;
return;
}
for (int i = 1; i <= 50; i++) {
if (checkVisit(i, i + L[k])) {
visit(i, i + L[k], 1);

// Neu ads nam trong thoi gian cua guest thi tinh diem
for (int j = 0; j < N; j++) {
if (i >= guestTime[j][0] && i + L[k] <= guestTime[j][1])
score[k][j] = P[k];
}

backtrack(k + 1);

visit(i, i + L[k], 0);

for (int j = 0; j < N; j++) {
if (i >= guestTime[j][0] && i + L[k] <= guestTime[j][1])
score[k][j] = 0;
}
}

}
}

private static int sum() {
int count = 0;
for (int i = 0; i < N; i++) {
int max = score[0][i];
for (int j = 1; j < 3; j++)
if (max < score[j][i])
max = score[j][i];
count += max;
}
return count;
}
}
//Hugo ban dau
#include<iostream>
using namespace std;
int N, M;
int P; // giới hạn bơm
// mảng 8 loại đường ống
int DuongOng[8][4]={
0,0,0,0,
1,1,1,1,
1,0,1,0,
0,1,0,1,
1,1,0,0,
0,1,1,0,
0,0,1,1,
1,0,0,1 };

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int visit[51][51]; // mảng thăm
int cntN[51][51]; // mảng lan truyền
int map[51][51]; // mang đường ống
int Qx[10000];
int Qy[10000];
int rear, front;
int cnt; //đếm số đường ống

bool check(int x, int y){
if(x >= 0 && x < N && y >= 0 && y < M)return true;
return false;
}
void BFS(int x_mb, int y_mb){
front = rear = 0;
Qx[rear] = x_mb;
Qy[rear++] = y_mb;
visit[x_mb][y_mb] = 1;
cntN[x_mb][y_mb] = 1;
while (front < rear){
int x = Qx[front];
int y = Qy[front++];
for (int i = 0; i < 4; i++){
int nx = x + dx[i]; // vị trí sắp đi đến
int ny = y + dy[i];
if(check(nx, ny)) // check vị trí sắp đi đến
{
if(map[nx][ny] != 0 && visit[nx][ny] == 0 && DuongOng[map[x][y]][i] == 1 && DuongOng[map[nx][ny]][(i+2)%4] == 1)
{ // nếu vị trí sắp tới khác 0, chưa thăm, đầu của 2 loại ống phù hợp nhau
cntN[nx][ny] = cntN[x][y] + 1; // lan truyền giới hạn bơm
if(cntN[nx][ny] > P)return;
cnt++;
Qx[rear] = nx;
Qy[rear++] = ny;
visit[nx][ny] = 1;
}
}
}
}
}
void reset(){
for (int i = 0; i <= N; i++){
for (int j = 0; j <= M; j++){
visit[i][j] = 0;
cntN[i][j] = 0;
}
}
}

int main(){
int T;
int x_mb,y_mb;
freopen("input.txt", "r", stdin);
cin>>T;
for (int tc = 1; tc <= T; tc++)
{
cnt = 1;
cin>>N>>M>>x_mb>>y_mb>>P;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin>>map[i][j];
}
}
reset();
BFS(x_mb,y_mb);
cout<<"Case #"<<tc<<endl;
cout<<cnt<<endl;
}
return 0;
}
//HUgo quan ly tau
#include <iostream>

using namespace std;

int N; // Số lượng người trong dãy
int people[1001], door[4], kc[4][1001], check[5], visit[1001]; // Mảng lưu thông tin về người, cửa, khoảng cách, kiểm tra và viếng thăm
int Max; // Biến lưu trữ kết quả tối ưu

// Hàm in mảng khoảng cách
void print(int kc[]) {
for (int i = 1; i <= N; i++) {
cout << kc[i] << " ";
}
cout << endl;
}

int abs(int x){
return x > 0 ? x : -x;
}

// Hàm backtrack để thực hiện quay lui
void backtrack(int indext, int sum) {
// Nếu đã duyệt hết 4 cửa
if (indext == 4) {
// Lưu kết quả tối ưu
Max = min(Max, sum);
return;
}
// Duyệt qua từng cửa
for (int s = 1; s <= 3; s++) {
// Nếu chưa kiểm tra cửa này
if (check[s] == 0) {
// Duyệt qua 2 trường hợp: mở cửa hoặc không mở
for (int k = 0; k < 2; k++) {
int dor = door[s]; // Cửa hiện tại
int guse = people[dor]; // Số người ở cửa đó
int cout = 0; // Biến đếm số lần di chuyển
int value = 0; // Biến lưu tổng khoảng cách
// Trường hợp mở cửa
if (k == 0) {
check[s] = 1;
while (guse > 0) {
int l = dor - cout; // Cửa bên trái
int r = dor + cout; // Cửa bên phải
// Nếu cửa bên trái hợp lệ và chưa được viếng thăm
if (l >= 1 && visit[l] == 0) {
visit[l] = dor;
value = value + cout + 1; // Cập nhật tổng khoảng cách
guse--; // Giảm số người cần di chuyển
}
// Nếu cửa bên phải hợp lệ và chưa được viếng thăm
else if (r <= N && visit[r] == 0) {
visit[r] = dor;
value = value + cout + 1; // Cập nhật tổng khoảng cách
guse--; // Giảm số người cần di chuyển
}
// Nếu cửa đã được viếng thăm hoặc vượt quá phạm vi
else if ((r <= N && visit[r] != 0) || (l >= 1 && visit[l] != 0)) {
cout++; // Tăng biến đếm
}
}
// Gọi đệ quy cho cửa tiếp theo
backtrack(indext + 1, sum + value);
check[s] = 0; // Đánh dấu cửa đã được kiểm tra
// Đặt lại các cửa đã được viếng thăm
for (int i = 1; i <= N; i++) {
if (visit[i] == dor)
visit[i] = 0;
}
}
// Trường hợp không mở cửa
else {
check[s] = 1;
while (guse > 0) {
int l = dor - cout; // Cửa bên trái
int r = dor + cout; // Cửa bên phải
if (r <= N && visit[r] == 0) { // Nếu cửa bên phải hợp lệ và chưa được viếng thăm
visit[r] = dor;
value = value + cout + 1;
guse--;
}
else if (l >= 1 && visit[l] == 0) { // Nếu cửa bên trái hợp lệ và chưa được viếng thăm
visit[l] = dor;
value = value + cout + 1;
guse--;
} else {
cout++;
}
}
// Gọi đệ quy cho cửa tiếp theo
backtrack(indext + 1, sum + value);
check[s] = 0; // Đánh dấu cửa đã được kiểm tra
// Đặt lại các cửa đã được viếng thăm
for (int i = 1; i <= N; i++) {
if (visit[i] == dor)
visit[i] = 0;
}
}
}
}
}
}

int main() {
//freopen("HugoQuanLy.txt", "r", stdin);
int T;
cin >> T; // Nhập số lượng bộ test
for (int t = 1; t <= T; t++) {
cin >> N; // Nhập số lượng người trong dãy
// Nhập thông tin về cửa và số người ở mỗi cửa
for (int i = 1; i <= 3; i++) {
int x;
cin >> x;
door[i] = x;
cin >> people[x];
}
// Tính toán khoảng cách từ mỗi cửa đến từng người
for (int i = 1; i <= 3; i++) {
int k = door[i];
for (int j = 1; j <= N; j++) {
kc[i][j] = abs(k - j) + 1;
}
}
Max = 10000; // Khởi tạo kết quả tối ưu
backtrack(1, 0); // Gọi hàm backtrack để tìm kết quả tối ưu
// In kết quả
cout << "Case #" << t << endl;
cout << Max << endl;
}

return 0;
}
//Thong tri khu vuc
#include<iostream>
using namespace std;
// code 100/100
int map[105][105];
int mapCopy[105][105];
int visit[105][105];
int Que[10000][2];
int n, ans, T;
int TS[6]; // mảng lưu tần số xuất hiện của các số
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1,0, 1,0 };
void reset() {
for (int i = 0; i < 6; i++)  TS[i] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) visit[i][j] = 0;
}
}
void dfs(int x, int y, int oVal, int nVal) {           // Tô màu cho cửa hàng
for (int h = 0; h < 4; h++) {
int nx = x + dx[h];
int ny = y + dy[h];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (!visit[nx][ny] && mapCopy[nx][ny] == oVal) {
visit[nx][ny] = 1;
mapCopy[nx][ny] = nVal;
dfs(nx, ny, oVal, nVal);
}
}
}
void bfs(int x, int y) {
reset();
visit[x][y] = 1;
int front = 0, rear = 0;
Que[rear][0] = x; // push vị trí đầu vào Queue
Que[rear++][1] = y;
while (front < rear) {
int r = Que[front][0]; // vị trí đang đứng
int c = Que[front++][1];
for (int h = 0; h < 4; h++) {
int nx = r + dx[h]; // vị trí sắp đến
int ny = c + dy[h];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // check vị trí sắp đến
if (!visit[nx][ny]) { // nếu vị trí sắp tới chưa được thăm
if ((map[r][c] == 0) || (map[nx][ny] == map[r][c])) {
TS[map[nx][ny]] ++;                    // Tăng tần số xuất hiện cho số đó
visit[nx][ny] = 1; // đánh dấu
Que[rear][0] = nx; // push số đó vào Queue
Que[rear++][1] = ny;
}
}
}
}
int maxTS = TS[1], color = 1;
for (int i = 2; i <= 5; i++)
if (TS[i] >= maxTS) {              // Chọn ra số có tần số xuất hiện nhiều nhât
color = i;
maxTS = TS[i];
}
mapCopy[x][y] = color;
dfs(x, y, 0, color);
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mapCopy[i][j] == 0) {
bfs(i, j);
}
}
}
reset();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visit[i][j]) {                      // Tìm số vùng
ans++;
visit[i][j] = 1;
dfs(i, j, mapCopy[i][j], mapCopy[i][j]);
}
}
}
}
int main() {
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++) {
cin >> map[i][j];
mapCopy[i][j] = map[i][j];
}
}
ans = 0; solve();
cout << "Case #" << tc << endl << ans << endl;
}
return 0;
}
//Cleaning robot
#include<iostream>

using namespace std;

int M[101][101];
int visited[101][101];
int A[2][100];
int idx;
int ke[101][101];
int S[2][1000000];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int top;
int bot;
int luu[11];
int used[11];
int minn,kq;

bool checkused()
{
for(int i=0;i<idx;i++)
{
if(used[i]==0) return true;
}
return false;
}

void tinhtoan(int x)
{
if(kq>minn) return;
if(!checkused())
{
if(kq<minn) minn=kq;
return;
}
for(int i=0;i<idx;i++)
{
if(used[i]==0)
{
kq+=ke[x][i];
used[i]=1;
tinhtoan(i);
used[i]=0;
kq-=ke[x][i];
}
}
}

int main()
{
//freopen("input.txt","r",stdin);
int t;cin>>t;

for(int tc=1;tc<=t;tc++)
{
idx=1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>M[i][j];
if(M[i][j]==3)
{
A[0][0]=i;
A[1][0]=j;
}
else if(M[i][j]==1)
{
A[0][idx]=i;
A[1][idx]=j;
idx++;
}
}
}
// xu ly
for(int i=0;i<101;i++)
for(int j=0;j<101;j++) ke[i][j]=0;
//
int dem=0;
bool firstcheck=true;
for(int i=0;i<idx;i++)
{
for(int a=0;a<101;a++)
for(int b=0;b<101;b++) visited[a][b]=0;
//khai bao queue
top=-1,bot=-1;
//
top++;
S[0][top]=A[0][i];
S[1][top]=A[1][i];
visited[A[0][i]][A[1][i]]=1;
//
while(top!=bot)
{
bot++;
int x=S[0][bot];
int y=S[1][bot];
//
for(int k=0;k<4;k++)
{
int xnew=x+dx[k];
int ynew=y+dy[k];
if(xnew >=0 && xnew <n && ynew >= 0 && ynew<m)
{
if(visited[xnew][ynew]==0 && M[xnew][ynew]!=2)
{
top++;
S[0][top]=xnew;
S[1][top]=ynew;
visited[xnew][ynew]=visited[x][y]+1;
}
}
}
}
//dua vao ma tran ke
for(int a=0;a<idx;a++)
{
ke[i][a]=visited[A[0][a]][A[1][a]]-1;
if(ke[i][a]==-1) firstcheck=false;
}
if(firstcheck) dem++;
}
if(dem<idx)
{
cout<<"Case #"<<tc<<endl<<-1<<endl;
continue;
}
minn=9999;kq=0;
for(int k=0;k<11;k++) used[k]=0;
//
tinhtoan(0);
//
cout<<"Case #"<<tc<<endl;
cout<<minn<<endl;
}
return 0;
}
//Ho den
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Test_1 {
static int T, numberWhole;
static int pointX[], pointY[], value[][], min;
static boolean visited[][];

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

public static void backTrack(int r, int c, int sumTime){
if(sumTime > min) return;

if(min > sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1])){
min = sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1]);
return;
}

for(int i = 1; i <= numberWhole; i++){
visited[value[i][0]][value[i][1]] = true;
visited[value[i][2]][value[i][3]] = true;

if(!visited[value[i][0]][value[i][1]]){
backTrack(value[i][2], value[i][3],
sumTime + value[i][4] + calculatePoint(r, value[i][0], c, value[i][1]));
}

if(!visited[value[i][2]][value[i][3]]){
backTrack(value[i][0], value[i][1],
sumTime + value[i][4] + calculatePoint(r, value[i][2], c, value[i][3]));
}

visited[value[i][0]][value[i][1]] = false;
visited[value[i][2]][value[i][3]] = false;

}
}

public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Test_1"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
numberWhole = scanner.nextInt();
pointX = new int[numberWhole+2];
pointY = new int[numberWhole+2];
pointX[0] = scanner.nextInt();
pointY[0] = scanner.nextInt();
pointX[numberWhole+1] = scanner.nextInt();
pointY[numberWhole+1] = scanner.nextInt();

value = new int[numberWhole+1][5];

for(int i = 1; i <= numberWhole; i++){
value[i][0] = scanner.nextInt();
value[i][1] = scanner.nextInt();
value[i][2] = scanner.nextInt();
value[i][3] = scanner.nextInt();
value[i][4] = scanner.nextInt();
}

visited = new boolean[1001][1001];
min = calculatePoint(pointX[0], pointX[numberWhole+1],
pointY[0], pointY[numberWhole+1]);

visited[pointX[0]][pointY[0]] = true;
backTrack( pointX[0], pointY[0], 0);
System.out.println("#" + tc + " " + min);

}
}

}
//Cuting a piece
import java.util.Scanner;

public class PaperCutting {

// Hàm đệ quy để đếm số lượng giấy trắng và xanh
static int[] countColoredPieces(int[][] paper, int x, int y, int size) {
if (isUniform(paper, x, y, size)) {
if (paper[x][y] == 0) {
return new int[]{1, 0}; // {white, blue}
} else {
return new int[]{0, 1}; // {white, blue}
}
} else {
int newSize = size / 2;
int[] count1 = countColoredPieces(paper, x, y, newSize);
int[] count2 = countColoredPieces(paper, x, y + newSize, newSize);
int[] count3 = countColoredPieces(paper, x + newSize, y, newSize);
int[] count4 = countColoredPieces(paper, x + newSize, y + newSize, newSize);

return new int[]{
count1[0] + count2[0] + count3[0] + count4[0],
count1[1] + count2[1] + count3[1] + count4[1]
};
}
}

// Hàm kiểm tra nếu tất cả các phần của giấy có cùng màu
static boolean isUniform(int[][] paper, int x, int y, int size) {
int color = paper[x][y];
for (int i = x; i < x + size; i++) {
for (int j = y; j < y + size; j++) {
if (paper[i][j] != color) {
return false;
}
}
}
return true;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();

for (int t = 1; t <= T; t++) {
int N = sc.nextInt();
int[][] paper = new int[N][N];

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
paper[i][j] = sc.nextInt();
}
}

int[] result = countColoredPieces(paper, 0, 0, N);
System.out.println("Case #" + t);
System.out.println(result[0] + " " + result[1]);
}
sc.close();
}
}
//Skyforce
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;
#define SIZE 15

int map[SIZE][SIZE];
int N;
int best;

void resetData() {
int i, j;
best = -1;
for (i = 0; i < SIZE; ++i) {
for (j = 0; j < 5; ++j) {
map[i][j] = 0;
}
}
}

void move(int row, int col, int coin, int ignoreEnemy, bool have_bomb) {
if (col < 0 || col > 4) return;

if (row < 0) {
if (best < coin) best = coin;
return;
}

//process current cell
if (map[row][col] == 1) {
++coin;
}
else if (map[row][col] == 2 && ignoreEnemy <= 0) {
if (coin > 0) --coin;
else return;
}

//scroll down bombed area
--ignoreEnemy;

//move up
move(row - 1, col, coin, ignoreEnemy, have_bomb);

//use bomb and move up
if (have_bomb) move(row - 1, col, coin, 5, false);

//move top-left
move(row - 1, col - 1, coin, ignoreEnemy, have_bomb);

//use bomb and move top-left
if (have_bomb) move(row - 1, col - 1, coin, 5, false);

//move top-right
move(row - 1, col + 1, coin, ignoreEnemy, have_bomb);

//use bomb and move top-right
if (have_bomb) move(row - 1, col + 1, coin, 5, false);
}

int main() {
int T, testcase;
cin>>T;
for (testcase = 1; testcase <= T; ++testcase) {
cin>>N;
resetData();
int i, j, k;
for (i = 0; i < N; ++i) {
for (j = 0; j < 5; ++j) {
cin>>map[i][j];
}
}

move(N, 2, 0, 0, true);
cout<<"Case #"<<testcase<<endl;
cout<<best<<endl;
}
return 0;
}
//Hugo di tau

#include <iostream>

using namespace std;

// Hàm để tính tổng khoảng cách di chuyển của hành khách từ một cửa
int calculateDistance(int N, int startPos, int numPassengers, bool seats[]) {
int totalDistance = 0;
for (int i = 0; i < numPassengers; ++i) {
int distance = 0;
while (true) {
// Kiểm tra vị trí ngồi tại startPos
if (startPos + distance < N && !seats[startPos + distance]) {
totalDistance += distance + 1;
seats[startPos + distance] = true;
break;
}
if (startPos - distance >= 0 && !seats[startPos - distance]) {
totalDistance += distance + 1;
seats[startPos - distance] = true;
break;
}
distance++;
}
}
}

// Hàm để tìm tất cả các hoán vị của mảng
bool nextPermutation(int arr[], int size) {
int i = size - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) {
i--;
}
if (i < 0) return false;
int j = size - 1;
while (arr[j] <= arr[i]) {
j--;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
for (int k = i + 1, l = size - 1; k < l; k++, l--) {
temp = arr[k];
arr[k] = arr[l];
arr[l] = temp;
}
return true;
}

int main() {
freopen("inp.txt", "r", stdin);
int T;
cin >> T;

for (int caseNum = 1; caseNum <= T; ++caseNum) {
int N;
cin >> N;

int positions[3], passengers[3];
for (int i = 0; i < 3; ++i) {
cin >> positions[i] >> passengers[i];
positions[i]--; // Để vị trí bắt đầu từ 0
}

int minDistance = 999999; // Giá trị lớn ban đầu
int order[3] = {0, 1, 2};

// Duyệt tất cả các thứ tự mở cửa
do {
bool seats[60] = {false}; // Mảng trạng thái ghế trống

int currentDistance = 0;
for (int i = 0; i < 3; ++i) {
currentDistance += calculateDistance(N, positions[order[i]], passengers[order[i]], seats);
}

if (currentDistance < minDistance) {
minDistance = currentDistance;
}
} while (nextPermutation(order, 3));

cout << "Case #" << caseNum << "\n" << minDistance << "\n";
}

return 0;
}
//mario climb
#include <iostream>

using namespace std;
int M, N;
int xS, yS, xE, yE;
int front, rear;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int A[55][55];
int visit[55][55];
int ans;

struct Node{
int r,c;
};

Node queue[100000];

void enQueue(int x, int y){
Node node; node.r = x; node.c = y;
rear++;
queue[rear] = node;
}

Node deQueue(){
front++;
return queue[front];
}

void resetVisit(){
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
visit[i][j] = 0;
}
}
}

int check(int k){
resetVisit();
front = rear = -1;
enQueue(xS,yS);
visit[xS][yS] = 1;

while (front!=rear)
{
Node mid = deQueue();
if(mid.r == xE && mid.c == yE){
return 1;
}

for (int i = 2; i <= 3; i++)
{
for (int j = 1; j <= k; j++)
{
int tx = mid.r + dx[i] * j;
int ty = mid.c + dy[i];
if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3))
{
enQueue(tx,ty);
visit[tx][ty] = 1;
}
}
}

for (int i = 0; i < 2; i++)
{
int tx = mid.r + dx[i];
int ty = mid.c + dy[i];
if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3))
{
enQueue(tx,ty);
visit[tx][ty] = 1;
}
}
}

return 0;

}

int fun(int s, int e){
int mid = s + (e - s)/2;
if (check(mid-1) == 0 && check(mid) == 1)
{
return mid;
}

if(check(mid) == 1){
return fun(s,mid);
}else
{
return fun(mid+1,e);
}
}

int main(){
int tc, T;
//freopen("input.txt", "r", stdin);
cin>> T;

for (tc = 1; tc <= T; tc++)
{
cin >> M >> N;
ans = 0;

for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
cin>> A[i][j];
if(A[i][j] == 2){
xS = i;
yS = j;
}
if (A[i][j] == 3)
{
xE = i;
yE = j;
}
}
}

ans = fun(1,50);
cout<< "Case #" << tc <<endl;
cout<< ans << endl;

}

return 0;
}
//HUgo chi ong nau
#include<iostream>
using namespace std;

int T, M, N;
int arr[20][20], visited[20][20];
// -1 0, 0 1, 1 1, 1 0, 1 -1, 0 -1
// -1 0, -1 1, 0 1, 1 0, 0 -1, -1 -1;
int dxc[6] = {-1, 0, 1, 1, 1, 0};
int dyc[6] = {0, 1, 1, 0, -1, -1};

int dxl[6] = {-1, -1, 0, 1, 0, -1};
int dyl[6] = {0, 1, 1, 0, -1, -1};

bool isValid(int x, int y){
return x >= 1 && x <= N && y > 0 && y <= M;
}

void bt(int x, int y, int sum, int count){
if(count == 4){
}
return;
}
for(int i = 0; i < 6; i++){
if(y % 2 == 0){
int nx = x + dxc[i];
int ny = y + dyc[i];
if(isValid(nx, ny) && visited[nx][ny] == 0 ){
visited[nx][ny] = 1;

bt(nx, ny, sum+ arr[nx][ny], count+1);
bt(x,y,sum+arr[nx][ny],count+1);
visited[nx][ny] = 0;
}

}
else{
int nx = x + dxl[i];
int ny = y + dyl[i];
if(isValid(nx, ny) && visited[nx][ny] == 0){
visited[nx][ny] = 1;

bt(nx, ny, sum+ arr[nx][ny], count+1);
bt(x,y,sum+arr[nx][ny],count+1);
visited[nx][ny] = 0;
}
}
}
}

void reset(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
visited[i][j] = 0;
}
}
}

int main(){
//freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
cin >> M >> N;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin >> arr[i][j];
}
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
visited[i][j] = 1;
int sum = arr[i][j];
bt(i, j, sum, 1);
reset();
}
}
cout << "Case #" <<tc << endl;

}
return 0;
}
//Visit department
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
static int N, E, K , T;
static int len = 201;
static double[][] arr = new double[len][len];
static double[][] timeXacSuat = new double[len][len];

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {

}
Scanner sc = new Scanner(System.in);
for (int tcid = 1; tcid <= 15; tcid++) {
N = sc.nextInt();	//so phong ban
E = sc.nextInt();	//so mui ten
K = sc.nextInt();	//time kang
T = sc.nextInt();	//time = minutes
reset();
for (int i = 0; i < E; i++) {
int dinh1 = sc.nextInt();
int dinh2 = sc.nextInt();
arr[dinh1][dinh2] = sc.nextDouble();

}

//node
timeXacSuat[1][0] = 1;
for(int t = 1; t <= T/10; t++){
for(int i = 1; i <= N; i++){
if(timeXacSuat[i][t-1] != 0){
for(int j = 1; j <= N; j++){
if(arr[i][j] != 0){
timeXacSuat[j][t] += timeXacSuat[i][t-1]*arr[i][j];
}
}
}
}
}
//Jang start tai 0, Kang tai K
//10p di chuyen 1 lan
int jangTime = T/10, kangTime = (T-K)/10;
int jangD = 0, kangD = 0;
double jangXS = 0, kangXS = 0;
for(int i = 1; i <= N; i++){
if(timeXacSuat[i][jangTime] > jangXS){
jangXS = (double) timeXacSuat[i][jangTime];
jangD = i;
}
if(timeXacSuat[i][kangTime] > kangXS){
kangXS = (double) timeXacSuat[i][kangTime];
kangD = i;
}
}

System.out.print("#" + tcid + " ");
System.out.printf("%d %.6f %d %.6f\n", jangD, jangXS, kangD, kangXS);
}
sc.close();
}

private static void reset(){
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
arr[i][j] = 0;
timeXacSuat[i][j] = 0;
}
}
}
}
//Cover dominos
#include <iostream>

using namespace std;

#define N 7
#define M 8

int T, results, nx, ny, index, tt;
int matrix[50][50];
int visit[10][10];
int dt[2][2] = {{0,1},{1,0}};
int state[50][50];
int Q[100][2];

void BT(int x, int cnt, int y){
if (x == N && cnt == 28) {
results++;
return;
}
if (x == N) return;

if (state[x][y] == 0){
tt = 1;
for (int k = 0; k < 2; k++){
nx = x + dt[k][0];
ny = y + dt[k][1];
if (nx >= 0 && nx < N && ny >= 0 && ny < M && visit[matrix[nx][ny]][matrix[x][y]] == 0 && state[nx][ny] == 0){
tt = 0;
state[x][y] = cnt+1;
state[nx][ny] = cnt+1;
visit[matrix[nx][ny]][matrix[x][y]] = 1;
visit[matrix[x][y]][matrix[nx][ny]] = 1;
Q[index][0] = nx; Q[index][1] = ny; index++;
if (ny < M-1) BT(x,cnt+1,y+1);
else BT(x+1,cnt+1,0);
index--;
state[x][y] = 0;
state[Q[index][0]][Q[index][1]] = 0;
visit[matrix[Q[index][0]][Q[index][1]]][matrix[x][y]] = 0;
visit[matrix[x][y]][matrix[Q[index][0]][Q[index][1]]] = 0;
}
}
if (tt == 1) return;
}
else if (y < M - 1) BT(x,cnt,y+1);
else BT(x+1,cnt,0);

}

int main(){
freopen("input.txt","r",stdin);
cin >> T;
for (int t = 0; t < T; t++){
results = 0;
index = 0;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
cin >> matrix[i][j];
state[i][j] = 0;
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
visit[i][j] = 0;
}
}
BT(0, 0, 0);
cout << "#" << t + 1 << " " << results << endl;
}
return 0;
}
//Connect Processor
#include<iostream>

// code 100/100
// Backtrack (trả lại visit)

using namespace std;
int tc,n,map[12][12], visited[12][12];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; // trên, phải, xuống, trái
int chip[2][12], minn=987654,cnt=0,dai=0;

bool checkMap(int x, int y){
return (x<n && y<n && x>=0 && y>=0);
}

bool checkHuong (int x, int y, int hgx, int hgy){
int tempx = x+hgx;
int tempy = y+hgy;
while(checkMap(tempx,tempy)){
if(visited[tempx][tempy]==1){
return false;
}
tempx += hgx;
tempy += hgy;
}
return true;
}
void visit(int x, int y, int hgx, int hgy, int val){
int tempx = x+hgx;
int tempy = y+hgy;
dai=0;
while(checkMap(tempx,tempy) && map[tempx][tempy]==0){
dai++;
visited[tempx][tempy]+=val; // đánh dấu ô đã đi qua
tempx += hgx;
tempy += hgy;
}
}
void BT(int xx,int sum){ // chip, sum
if(sum>minn) return;
if(xx==cnt){
if(sum<minn) minn=sum;
return;
}
int x=chip[0][xx];
int y=chip[1][xx];
if(x==-1 && y==-1){ // chip(-1,-1) là ko thể nối nguồn
BT(xx+1,sum);
}
else{
for(int i=0;i<4;i++){ // đi 4 hướng
if(checkHuong(x,y,dx[i],dy[i]) ){
visit(x,y,dx[i],dy[i],1);
BT(xx+1,sum+dai);
visit(x,y,dx[i],dy[i],-1); // trả lại visit
}
}
return;
}
}
int main(){

cin>>tc;
for(int t=1;t<=tc;t++){
cin>>n;
minn=987654;
cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
visited[i][j]=0;
cin>>map[i][j];
if(map[i][j]==1){
if(i==0 || i==n-1 || j==0 ||j==n-1){}
else { // chỉ lưu các chip trong bo
chip[0][cnt]=i;
chip[1][cnt]=j;
cnt++;
}
visited[i][j]=1;
}
}
}
for(int i=0;i<cnt;i++){ // check tất cả các chip theo 4 hướng
bool ch[4];
for(int j=0;j<4;j++){ // check 4 hướng cửa chip
ch[j]=checkHuong(chip[0][i],chip[1][i],dx[j],dy[j]);
}
if(!ch[0] && !ch[1] && !ch[2] && !ch[3] ){ // chip ko đi được hướng nào cả
chip[0][i]=-1;
chip[1][i]=-1;
}
}
BT(0,0);
if(minn==987654) cout<<"#"<<t<< " "<<0<<endl;
else {
cout<<"#"<<t<<" "<<minn<<endl;
}
}

return 0;
}```