HDU4979-A simple math problem.

A simple math problem.

                                                                    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

                                                                                              Total Submission(s): 435    Accepted Submission(s): 150

Problem Description Dragon loves lottery, he will try his luck every week. One day, the lottery company brings out a new form of lottery called accumulated lottery. In a normal lottery, you pick 7 numbers from N numbers. You will get reward according to how many numbers you match. If you match all 7 numbers, you will get the top prize for 1 billion dollars!!! Unlike normal lottery, an M-accumulated lottery allows you to pick M numbers from N numbers. If M is big enough, this may significantly increase your possibility to win. (Of course it cost more…) 

Some people buy multiple accumulated lotteries to guarantee a higher possibility to get the top prize. Despite of this, it’s still not worthy to guarantee a top prize.Knowing this, Dragon changes his target to second tier prize.  To get a second tier prize, you need to contain all of the R numbers with M numbers picked.Given N, M and R, Dragon wants to know how many M-accumulated lotteries he needs to buy, so that he can guarantee that he can get at least the second tier prize.  

Input The first line of input contains only one integer T, the number of test cases.

For each case, there’s a single line contains N, M and R(1<=R<=M<=N<=8).  

Output Each output should occupy one line. Each line should start with "Case #i: ", with i implying the case number. For each case, just output the result with no other leading or tailing spaces.  

Sample Input

3
2 1 1
2 2 1
2 2 2
        

Sample Output

Case #1: 2
Case #2: 1
Case #3: 1
        

Author BJTU  

Source 2014 Multi-University Training Contest 10  

題意：有n個号碼，每張彩票是n中選M個号碼的一個組合，中獎号碼是n中選r個号碼的一個組合，如果買的一張彩票m個号碼完整覆寫r即中獎。給出n,m,r，問至少買多少彩票可以保證中獎

解題思路：這題需要舞蹈鍊重複覆寫打表才能通過，打表整整花了20分鐘左右

#include <iostream>      
#include <cstdio>      
#include <cstring>      
#include <string>      
#include <algorithm>      
#include <cctype>      
#include <map>      
#include <cmath>      
#include <set>      
#include <stack>      
#include <queue>      
#include <vector>      
#include <bitset>      
#include <functional>      

using namespace std;

#define LL long long      
const int INF = 0x3f3f3f3f;
const int maxn = 300005;

/*
int n, m, R, x, y, tot1, tot2;
vector<int>g[10];

struct DLX
{
	int L[maxn], R[maxn], U[maxn], D[maxn];
	int row[maxn], col[maxn], sum[maxn], ans[maxn];
	int n, m, num, cnt;
	int vis[maxn];
	void add(int k, int l, int r, int u, int d, int x, int y)
	{
		L[k] = l;   R[k] = r;   U[k] = u;
		D[k] = d;   row[k] = x;  col[k] = y;
	}
	void reset(int n, int m)
	{
		num = 0x7FFFFFFF;
		this->n = n;   this->m = m;
		for (int i = 0; i <= m; i++)
		{
			add(i, i - 1, i + 1, i, i, 0, i);
			sum[i] = 0;
		}
		L[0] = m, R[m] = 0, cnt = m + 1;
	}
	void insert(int x, int y)
	{
		int temp = cnt - 1;
		if (row[temp] != x)
		{
			add(cnt, cnt, cnt, U[y], y, x, y);
			U[D[cnt]] = cnt; D[U[cnt]] = cnt;
		}
		else
		{
			add(cnt, temp, R[temp], U[y], y, x, y);
			R[L[cnt]] = cnt; L[R[cnt]] = cnt;
			U[D[cnt]] = cnt; D[U[cnt]] = cnt;
		}
		sum[y]++, cnt++;
	}
	void Remove(int k)
	{
		for (int i = D[k]; i != k; i = D[i])
		{
			L[R[i]] = L[i];
			R[L[i]] = R[i];
		}
	}
	void Resume(int k)
	{
		for (int i = U[k]; i != k; i = U[i]) L[R[i]] = R[L[i]] = i;
	}
	int A()
	{
		int dis = 0;
		for (int i = R[0]; i != 0; i = R[i]) vis[i] = 0;
		for (int i = R[0]; i != 0; i = R[i])
			if (!vis[i])
			{
				dis++, vis[i] = 1;
				for (int j = D[i]; j != i; j = D[j])
					for (int k = R[j]; k != j; k = R[k])
						vis[col[k]] = 1;
			}
		return dis;
	}
	void Dfs(int k)
	{
		if (!R[0]) { num = min(num, k); return ; }
		else if (k + A() < num)
		{
			int now = R[0];
			for (int i = R[0]; i != 0; i = R[i])
				if (sum[now] > sum[i]) now = i;
			for (int i = D[now]; i != now; i = D[i])
			{
				ans[k] = row[i];
				Remove(i);
				for (int j = R[i]; j != i; j = R[j]) Remove(j);
				Dfs(k + 1);
				for (int j = L[i]; j != i; j = L[j]) Resume(j);
				Resume(i);
			}
		}
	}
}dlx;

int main()
{
	freopen("output.txt", "w", stdout);
	for (int n = 1; n <= 8; n++)
	{
		for (int k = 1; k <= n; k++) g[k].clear();
		for (int k = 1; k < (1 << n); k++)
		{
			int sum = 0;
			for (int p = 0; p < n; p++)
				if (k&(1 << p)) sum++;
			g[sum].push_back(k);
		}
		for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
		for (int m = 1; m <= n; m++)
		{
			for (int R = 1; R <= m; R++)
			{
				tot1 = g[R].size(), tot2 = g[m].size();
				dlx.reset(tot2, tot1);
				for (int i = 0; i < tot2; i++)
					for (int j = 0; j < tot1; j++)
						if ((g[m][i] | g[R][j]) == g[m][i])
							dlx.insert(i + 1, j + 1);
				dlx.Dfs(0);
				printf("%d ", dlx.num);
			}
			printf("\n");
		}
		printf("\n\n");
	}
	return 0;
}*/

int ans[10][10][10]=
{
	{
		{1}
	},
	{
		{2},
		{1, 1}
	},
	{
		{3},
		{2,3},
		{1, 1, 1}
	},
	{
		{4},
		{2, 6},
		{2, 3, 4},
		{1, 1, 1, 1}
	},
	{
		{5},
		{3, 10},
		{2, 4, 10},
		{2, 3, 4, 5},
		{1, 1, 1, 1, 1}
	},
	{
		{6},
		{3, 15},
		{2, 6, 20},
		{2, 3, 6, 15},
		{2, 3, 4, 5, 6},
		{1, 1, 1, 1, 1, 1}
	},
	{
		{7},
		{4, 21},
		{3, 7, 35},
		{2, 5, 12, 35},
		{2, 3, 5, 9, 21},
		{2, 3, 4, 5, 6, 7},
		{1, 1, 1, 1, 1, 1, 1}
	},
	{
		{8},
		{4, 28},
		{3, 11, 56},
		{2, 6, 14, 70},
		{2, 4, 8, 20, 56},
		{2, 3, 4, 7, 12, 28},
		{2, 3, 4, 5, 6, 7, 8},
		{1, 1, 1, 1, 1, 1, 1, 1}
	}
};

int n, m, R;

int main()
{
	int t, cas = 0;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d%d", &n, &m, &R);
		printf("Case #%d: %d\n", ++cas, ans[n - 1][m - 1][R - 1]);
	}
	return 0;
}