【bzoj1224】[HNOI2002]彩票

2015.04.15 09:25 Wed | 21次阅读 | 旧日oi | 固定链接 | 源码

Description

某地发行一套彩票。彩票上写有1到M这M个自然数。彩民可以在这M个数中任意选取N个不同的数打圈。每个彩民只能买一张彩票,不同的彩民的彩票上的选择不同。每次抽奖将抽出两个自然数X和Y。如果某人拿到的彩票上,所选N个自然数的倒数和,恰好等于X/Y,则他将获得一个纪念品。已知抽奖结果X和Y。现在的问题是,必须准备多少纪念品,才能保证支付所有获奖者的奖品。

Input

输入文件有且仅有一行,就是用空格分开的四个整数N,M,X,Y。输出文件有且仅有一行,即所需准备的纪念品数量。 1≤X, Y≤100,1≤N≤10,1≤M≤50。输入数据保证输出结果不超过10^5。

Output

2 4 3 4

Sample Input

1

Sample Output

题解

爆搜

我的程序

#include<cstdio>
#define eps 1e-10
int n,m,ans;
double sum[51],x,y;
void dfs(int now,int ret,double num)
{
    if(now>m+1-ret) return;
    if(sum[now+ret-1]-sum[now-1]<num-eps) return;
    if(sum[m]-sum[m-ret]>num+eps) return;
    if(ret==0)
    {
        ans++;
        return;
    }
    dfs(now+1,ret-1,num-1.0/now);
    dfs(now+1,ret,num);
}
int main()
{
    for(int i=1;i<=50;i++) sum[i]=sum[i-1]+1.0/i;
    scanf("%d%d%lf%lf",&n,&m,&x,&y);
    dfs(1,n,x/y);
    printf("%d\n",ans);
    return 0;
}```