I2P(I)2023_Hu_Mid2

Climbing Stairs part 1

#include <stdio.h>

int dp[45];

int main(void) {

    //freopen("13540.txt", "r", stdin);
    
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i < 45; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    int T;
    scanf("%d", &T);
    while(T--) {
        int h;
        scanf("%d", &h);
        printf("%d\n", dp[h]);
    }
    
    return 0;
}

Climbing Stairs part 2

#include <stdio.h>

int min(int a, int b){
    return a < b ? a : b;
}

int main(){
    int t, c;
    scanf("%d %d", &t, &c);
    int cost[c];
    for(int i=0; i<c; i++){
        scanf("%d", &cost[i]);
    }

    int dp[c+2];
    dp[0] = 0;
    dp[1] = 0;
    for(int i=2; i<c+2; i++){
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    }

    while(t--){
        int x;
        scanf("%d", &x);
        printf("%d\n", dp[x]);
    }
}

Chess Puzzle part 1

#include <stdio.h>

int n, m;
long long ans;

int queen[10];
int rook[10];

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

int valid(int row, int col, char type) {
	for (int i = 0; i < row; i++) {
		if (queen[i] == col) return 0;
		if (rook[i] == col) return 0;
	}

	for (int i = 0; i < row; i++) {
		if (queen[i] != -1) {
			if (abs(i - row) == abs(queen[i] - col)) return 0;
		}

		if (type == 'q') {
			if (queen[i] != -1) {
				if ((abs(i - row)) == abs(queen[i] - col)) return 0;
			} else {
				if ((abs(i - row)) == abs(rook[i] - col)) return 0;
			}
		}
	}

	return 1;
}

void place(int row, int q, int r) {
	if (q < 0 || r < 0) return;
	if (row == n+m) {
		ans++;
		return;
	}

	for (int i = 0; i < n+m; i++) {
		if (valid(row, i, 'q')) {		// place queen at [row][i].
			queen[row] = i;
			rook[row] = -1;
			place(row+1, q-1, r);
		}

		if (valid(row, i, 'r')) {		// place rook at [row][i].
			queen[row] = -1;
			rook[row] = i;
			place(row+1, q, r-1);
		}
	}
}

int main() {
	int t;
	scanf("%d", &t);
	
	while (t--) {
		scanf("%d %d", &n, &m);
		ans = 0;

		place(0, n, m);

		printf("%lld\n", ans);
	}
}

Chess Puzzle part 2

#include <stdio.h>

int n, m, K;
long long ans, sum;

int map[10][10];
int queen[10];
int rook[10];

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

int valid(int row, int col, char type) {
	for (int i = 0; i < row; i++) {
		if (queen[i] == col) return 0;
		if (rook[i] == col) return 0;
	}

	for (int i = 0; i < row; i++) {
		if (queen[i] != -1) {
			if (abs(i - row) == abs(queen[i] - col)) return 0;
		}

		if (type == 'q') {
			if (queen[i] != -1) {
				if ((abs(i - row)) == abs(queen[i] - col)) return 0;
			} else {
				if ((abs(i - row)) == abs(rook[i] - col)) return 0;
			}
		}
	}

	return 1;
}

void place(int row, int q, int r) {
	if (q < 0 || r < 0) return;
	if (row == n+m) {	
		if (sum <= K)
			ans++;
			
		return;
	}

	for (int i = 0; i < n+m; i++) {
		if (valid(row, i, 'q')) {		// place queen at [row][i].
			queen[row] = i;
			rook[row] = -1;
			
			sum += map[row][i];
			place(row+1, q-1, r);
			sum -= map[row][i];
		}

		if (valid(row, i, 'r')) {		// place rook at [row][i].
			queen[row] = -1;
			rook[row] = i;
			
			sum += map[row][i];
			place(row+1, q, r-1);
			sum -= map[row][i];
		}
	}
}

int main() {
	int t;
	scanf("%d", &t);
	
	while (t--) {
		scanf("%d %d %d", &n, &m, &K);
		ans = 0;
		
		for (int i = 0; i < n + m; i++) {
			for (int k = 0; k < n + m; k++) {
				scanf("%d", &map[i][k]);
			}
		}

		place(0, n, m);

		printf("%lld\n", ans);
	}
}

Chess Puzzle part 3

#include <stdio.h>

int n, m;
long long ans;

int knight[10];
int rook[10];

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

int valid(int row, int col, char type) {
	for (int i = 0; i < row; i++) {
		if (rook[i] == col) return 0;
		if (knight[i] == col) return 0;
	}

	if (row - 2 >= 0) {
		if (col - 1 >= 0 && knight[row-2] == col - 1) return 0;
		if (col + 1 < n+m && knight[row-2] == col + 1) return 0;
		
		if (type == 'k') {
			if (col - 1 >= 0 && rook[row-2] == col - 1) return 0;
			if (col + 1 < n+m && rook[row-2] == col + 1) return 0;
		}
	}
	
	if (row - 1 >= 0) {
		if (col - 2 >= 0 && knight[row-1] == col - 2) return 0;
		if (col + 2 < n+m && knight[row-1] == col + 2) return 0;
		
		if (type == 'k') {
			if (col - 2 >= 0 && rook[row-1] == col - 2) return 0;
			if (col + 2 < n+m && rook[row-1] == col + 2) return 0;
		}
	}

	return 1;
}

void place(int row, int q, int r) {
	if (q < 0 || r < 0) return;
	if (row == n+m) {
		ans++;
		return;
	}

	for (int i = 0; i < n+m; i++) {
		if (valid(row, i, 'k')) {		// place knight at [row][i].
			knight[row] = i;
			rook[row] = -1;
			place(row+1, q-1, r);
		}

		if (valid(row, i, 'r')) {		// place rook at [row][i].
			knight[row] = -1;
			rook[row] = i;
			place(row+1, q, r-1);
		}
	}
}

int main() {
	int t;
	scanf("%d", &t);
	
	while (t--) {
		scanf("%d %d", &n, &m);
		ans = 0;

		place(0, n, m);

		printf("%lld\n", ans);
	}
}