Coupons

uva10288:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1229

题意：有一种盒子，盒子一面会随机放一种卡片，现在要集齐n种卡片，问要买多少个盒子。

题解：假如说n==2，那么第一次买，肯定可以得到一种新的卡片，第二次买得到新的卡片的概率是1/2，也就是说你那买2包才能得到新的卡片，所以期望值是1+2==3；如果n==3的话，第一次概率是1，第二次是2/3,也就是说第二次要买3/2包才能得到一种新的卡片，第三次是1/3，所以要买3包，所以总的期望是1+3/2+3;一次类推，可以得到期望：n/1+n/2+n/3+.....+n/n.还有题目中的输出格式，用log(a)/log(10)+1就可以得到a的位数。还有uva用的是lld，不是I64d

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<set>

 #include<cmath>

 using namespace std;

 long long n,temp,a,b,ans;

 long long gcd(long long a, long long b){

     if(b==)

         return a;

     return gcd(b,a%b);

 }

 int main(){

    while(~scanf("%lld",&n)){

        a=;b=;ans=;

        for(int i=;i<=n;i++){

            a=a*i+b;

            b=b*i;

            temp=gcd(a,b);

            a/=temp;

            b/=temp;

        }

        a*=n;

        temp=gcd(a,b);

        a/=temp;

        b/=temp;

        ans=a/b;

         a=a%b;

         temp=gcd(a,b);

         a/=temp;

         b/=temp;

         int m,t;

          int s=(int)(log(b)/log()+);

         m=t=(int)(log(ans)/log()+);

         if(a==)

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

         else{

             while(t--)printf(" ");

             printf("%lld\n",a);

             printf("%lld ",ans);

             while(s--)printf("-");

             printf("\n");

             while(m--)printf(" ");

             printf("%lld\n",b);

         }

    }

 }

巴特西

Coupons

最新文章

热门文章