2024.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2024 on 2005-10-03 at 15:04:52 */ 
#include <stdio.h>
#include <string.h> 
#define  R_MAX  10
#define  C_MAX  2000

long fact[R_MAX+1];

int main()
{
	int m, n, test;
	int i, j;
	double c[R_MAX+1][C_MAX+1];
	
	fact[0] = 1;
	for(i = 1; i <= R_MAX; i++) {
		fact[i] = fact[i-1] * 2;
	}
	memset(c, 0, sizeof(c));
	for(i = 1; i <= R_MAX; i++) {
		for(j = 1; j <= C_MAX; j++) {
			if(i == 1) {
				c[i][j] = j;
			} else if(j < fact[i-1]) {
				c[i][j] = 0;
			} else if(j == fact[i-1]) {
				c[i][j] = 1;
			} else {
				c[i][j] += c[i][j-1];
				c[i][j] += c[i-1][j/2];
			}
		}
	}
	scanf("%d", &test);
	for(i = 1; i <= test; i++) {
		scanf("%d %d", &n, &m);
		printf("Case %d: ", i);
		printf("n = %d, m = %d, # lists = %.0lf\n", n, m, c[n][m]);
	}
	
	return 0;
}