Untitled
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