Untitled

avatar
user_9038197
plain_text
a year ago
7.9 kB
13
Indexable
// array game
#include <iostream>
using namespace std;
#define MAX 20005
int T, N, matrix[MAX], dem, ans;
long long sum;

void init(){
	for(int i = 0; i < MAX; i++){
		matrix[i] = 0;
	}
	dem = 0;
	ans = 0;
	sum = 0;
}

void solve(int start, int end, long long sumT){
	if(sumT % 2 == 1) return;

	sumT = sumT/2;
	long long s = 0;
	for(int i = start; i < end; i++){
		s += matrix[i];
		if(s > sumT) return;
		if(s == sumT){
			dem ++;
			if(dem > ans) ans = dem;
			solve(start, i + 1, s);
			solve(i + 1, end, s);
			dem --;
			break;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; t++){
		init();
		cin >> N;
		for(int i = 0; i < N; i++){
			cin >> matrix[i];
			sum += matrix[i];
		}
		if(sum == 0){
			cout << N- 1 << endl;
		}else{
			solve(0, N, sum);
			cout << ans << endl;
		}
	}

	return 0;
}


// di chuyen bo
#include <iostream>
using namespace std;
#define MAX 20
int T, M, N, matrix[MAX], binary[MAX], ans;


void init(){
	for(int i = 0; i < MAX; i++){
		matrix[i]  = 0;
		binary[i] = 0;
	}
	ans = 0;
}

void solve(int index,int sum){
	if(sum <= M){
		if(ans < sum){
			ans = sum;
		}
	}
	if(index == N){
		return;
	}
	
	for(int i = 0; i <= 1; i++){
		binary[index] = i;
		// chon
		if(binary[index] == 1){
			solve(index + 1, sum + matrix[index]);
		}
		// khong chon
		else{
			solve(index + 1, sum);
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; t++){
		init();
		cin >> M >> N;
		for(int i = 0; i < N; i++){
			cin >> matrix[i];
		}
		solve(0, 0);
		cout << "#" << t << " " << ans << endl;
	}

	return 0;
}


// hugo thi chay
#include <iostream>
using namespace std;
#define MAX 705
#define MAX_Q 100000
#define INF 999999999
int T, N, matrix[MAX][MAX], visited[MAX][MAX], ans, Min_n, Max_x, cnt;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
struct Pos
{
	int x;
	int y;
};

Pos queue[MAX_Q];
int front, rear;

void initQueue(){
	front = rear = -1;
}

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

Pos dequeue(){
	front++;
	return queue[front];
}

void init(){
	for(int i = 1; i <= MAX; i++){
		for(int j = 1; j <= MAX; j++){
			matrix[i][j] = 0;
			visited[i][j] = 0;
		}
	}
	ans = INF;
	Min_n = INF;
	Max_x = 0;
	cnt = 0;
}

void searchMinMax(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			if(Min_n > matrix[i][j]){
				Min_n = matrix[i][j];
			}
			if(Max_x < matrix[i][j]){
				Max_x = matrix[i][j];
			}
		}
	}
}

bool isPath(int start, int end){
	if(matrix[1][1] >= start && matrix[1][1] <= end){
		initQueue();
		enqueue(1, 1);
		cnt ++;
		visited[1][1] = cnt;
		while(rear != front){
			Pos p = dequeue();
			for(int k = 0; k < 4; k++){
				int xx = p.x + dx[k];
				int yy = p.y + dy[k];
				if(xx >= 1 && xx <= N && yy >= 1 && yy <= N && visited[xx][yy] < cnt && matrix[xx][yy] >= start && matrix[xx][yy] <= end){
					if(xx == N && yy == N){
						return true;
					}
					visited[xx][yy] = cnt;
					enqueue(xx ,yy);
				}
			}
		}
	}
	return false;
}

int solve(int left, int right){
	while(left < right){
		int mid = (left + right)/2;
		int flag = 0;
		for(int i = Min_n; i <= Max_x - mid; i++){
			if(isPath(i, i + mid)){
				flag = 1;
				right = mid;
				break;
			}
		}
		if(flag == 0){
			left = mid + 1;
		}
	}
	return left;
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; t++){
		init();
		cin >> N;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				cin >> matrix[i][j];
			}
		}
		searchMinMax();

		cout << "Case #" << t << " " << solve(0, Max_x - Min_n) << endl;;
	}

	return 0;
}


// nang cap may tinh
#include <iostream>
using namespace std;
int T, N, M, L, ans, linh_Kien[25], visitedGoi[55], visitedLK[25], binary[25], LK_Cho[25];

struct Goi
{
	int gia;
	int linhkien[25];
};

Goi goi[55];

void init(){
	for(int i = 1; i <= 55; i++){
		goi[i].gia = 0;
		for(int j = 1; j <= 25; j++){
			goi[i].linhkien[j] = 0;
		}
	}
	for(int i = 1; i <= 25; i++){
		linh_Kien[i] = 0;
		visitedLK[i] = 0;
		binary[i] = 0;
		LK_Cho[i] = 0;
	}
	for(int i = 1; i <= 55; i++){
		visitedGoi[i] = 0;
	}
	ans = 999999999;
}

void solve(int index, int sum){
	if(index > M){
		int temp = sum;
		for(int i = 1; i <= L; i++){
			if(visitedLK[linh_Kien[i]] == 1){
				temp += LK_Cho[linh_Kien[i]];
			}
		}
		if(ans > temp){
			ans = temp;
		}
		return;
	}
	if(sum > ans){
		return;
	}
	for(int i = 0; i <= 1; i++){
		binary[index] = i;
		if(binary[index] == 1){
			for(int j = 1; j <= L; j++){
				if(goi[index].linhkien[linh_Kien[j]] == 1){
					visitedLK[linh_Kien[j]] --;
				}
			}
			solve(index + 1, sum + goi[index].gia);
			for(int j = 1; j <= L; j++){
				if(goi[index].linhkien[linh_Kien[j]] == 1){
					visitedLK[linh_Kien[j]] ++;
				}
			}
		}else{
			solve(index + 1, sum);
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; t++){
		int s, a;
		init();
		cin >> N;
		for(int i = 1; i <= N; i++){
			cin >> LK_Cho[i];
		}
		cin >> M;
		for(int i = 1; i <= M; i++){
			cin >> goi[i].gia;
			cin >> s;
			for(int j = 1; j <= s; j++){
				cin >> a;
				goi[i].linhkien[a] = 1;
			}
		}
		cin >> L;
		for(int i = 1; i <= L; i++){
			cin >> linh_Kien[i];
			visitedLK[linh_Kien[i]] = 1;
		}
		if(M == 0){
			int temp = 0;
			for(int i = 1; i <= L; i++){
				if(visitedLK[linh_Kien[i]] == 1){
					temp += LK_Cho[linh_Kien[i]];
				}
			}
			cout << "#" << t << " " << temp << endl;
		}else{
			solve(1,0);
			cout << "#" << t << " " << ans << endl;
		}
		
	}

	return 0;
}


// qua cau
#include <iostream>
using namespace std;
#define MAX 15
int T, N, matrix[MAX][5], ans;
int dx[3] = {-1, -1, -1};
int dy[3] = {-1, 0, 1};
void init(){
	for(int i = 0; i < MAX; i++){
		for(int j = 0; j < 5; j++){
			matrix[i][j] = 0;
		}
	}
	ans = -1;
}

void solve(int x, int y, int sum, int van){
	if(x == 0){
		if(ans < sum){
			ans = sum;
		}
		return;
	}
	for(int k = 0; k < 3; k++){
		int xx = x + dx[k];
		int yy = y + dy[k];
		if(xx >= 0 && xx < N && yy >= 0 && yy < 5){
			if(matrix[xx][yy] < 2){
				solve(xx, yy, sum + matrix[xx][yy], van);
			}else{
				if(van == 1){
					solve(xx, yy, sum, 0);
				}
			}
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; t++){
		init();
		cin >> N;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < 5; j++){
				cin >> matrix[i][j];
			}
		}
		solve(N, 2, 0, 1);
		cout << "#" << t << " " << ans << endl;
	}
	return 0;
}

// turn over game
#include <iostream>
using namespace std;
#define INF 9999999
int T, matrix[5][5], visited[5][5], ans, white, black, dem;
int dx[5] = {0, 0, -1, 0, 1};
int dy[5] = {0, -1, 0, 1, 0};
void init(){
	for(int i = 1; i <= 5; i++){
		for(int j = 1; j <= 5; j++){
			matrix[i][j] = 0;
			visited[i][j] = 0;
		}
	}
	ans = INF;
	white = 0;
	black = 0;
}

void latco(int x, int y){
	for(int i = 0; i < 5; i++){
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(xx >= 0 && xx < 4 && yy >= 0 && yy < 4){
			if(matrix[xx][yy] == 1){
				matrix[xx][yy] = 0;
				black ++;
				white --;
			}else{
				matrix[xx][yy] = 1;
				black --;
				white ++;
			}
		}
	}
}

void solve(int index, int dem){
	if(white == 16 || black == 16){
		if(ans > dem){
			ans = dem;
		}
		return;
	}
	if(index == 16){
		return;
	}else{
		int r = index/4;
		int c = index%4;
		visited[r][c] = 1;
		latco(r, c);
		solve(index + 1, dem + 1);
		visited[r][c] = 0;
		latco(r, c);
		solve(index + 1, dem);
	}
	

}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; t++){
		init();
		for(int i = 0; i < 4; i++){
			for(int j = 0; j < 4; j++){
				char a;
				cin >> a;
				if(a == 'b'){
					 matrix[i][j] = 0;
					 black ++;
				}else{
					 matrix[i][j] = 1;
					 white ++;
				}

			}
		}
		solve(0, 0);
		cout << "Case #" << t << endl;
		if(ans == INF){
			cout << "impossible" << endl;
		}else{
			cout << ans << endl;
		}
	}

	return 0;
}
Editor is loading...
Leave a Comment