pku1923.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define ONLINE

#ifndef ONLINE
#include <time.h>
#endif

int N, M;
int found;

void DFS(int max, int ans, int left)
{
	int i;
	if (found)
	{
		return;
	}
	if (left == 0 && ans == M)
	{
		found = 1;
		return;
	}
	if (ans > M || ans + left * (left - 1) / 2 < M)
		return;
	for (i = max; i > 0; i--)
	{
		DFS(i, ans + i * (left - i), left - i);
	}
}

int main()
{

#ifndef ONLINE
	freopen("PKU1923.in", "r", stdin);
	clock_t start = clock();
#endif
	int t = 1;
	while (EOF != scanf("%d %d", &N, &M) && (M + N))
	{
		found = 0;
		DFS(N, 0, N);
		if (found)
			printf("Case %d: %d lines with exactly %d crossings can cut the plane into %d pieces at most.\n", t++, N, M, N + M + 1);
		else
			printf("Case %d: %d lines cannot make exactly %d crossings.\n", t++, N, M);
	}
#ifndef ONLINE
	printf("TIME:%dms\n", clock() - start);
#endif
	return 0;
}