fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. #define inf 1000000000
  4. struct node
  5. {
  6.     double cost;
  7.     double area;
  8. };
  9. struct coupon
  10. {
  11.     double arr[16];
  12. };
  13. struct coupon arr1[32768];
  14. struct node dp[32768][17];
  15. int main(void)
  16. {
  17.     int i,j,k,l,n,m,p,r;
  18.     double a,b,c,d,q;
  19.     while(1)
  20.     {
  21.         scanf("%d",&n);
  22.         if(n==0)
  23.             break;
  24.         double pa[n][2];
  25.         int power[16];
  26.         power[0]=1;
  27.         for(i=1;i<=15;i++)
  28.             power[i]=power[i-1]*2;
  29.             k=power[n];
  30.         for(i=0;i<=k-1;i++)
  31.         {
  32.             for(j=1;j<=n;j++)
  33.                 arr1[i].arr[j]=1;
  34.         }
  35.         for(i=0;i<=n-1;i++)
  36.         {
  37.             scanf("%d%d",&p,&r);
  38.             pa[i][0]=p;
  39.             pa[i][1]=r;
  40.             scanf("%d",&j);
  41.             for(l=0;l<=j-1;l++)
  42.             {
  43.                 scanf("%d%d",&p,&r);
  44.                 q=r;
  45.                 q=q/100;
  46.                 q=1-q;
  47.                 m=power[i];
  48.                 arr1[m].arr[p]*=q;
  49.             }
  50.         }
  51.         for(i=1;i<=k-1;i++)
  52.         {
  53.             j=log(i)/log(2);
  54.             //cout<<j<<endl;
  55.             j=power[j];
  56.             l=i-j;
  57.             for(m=1;m<=n;m++)
  58.                 arr1[i].arr[m]=arr1[j].arr[m]*arr1[l].arr[m];
  59.         }
  60.         for(i=1;i<=n+1;i++)
  61.         {
  62.             dp[0][i].cost=0;
  63.             dp[0][i].area=0;
  64.         }
  65.         for(i=1;i<=k-1;i++)
  66.         {
  67.             d=inf;
  68.             a=inf;
  69.             b=1;
  70.             for(j=1;j<=n;j++)
  71.             {
  72.                 l=power[j-1];
  73.                 if((i|l)==i)
  74.                 {
  75.                     m=i-l;
  76.                     dp[i][j].cost=dp[m][n+1].cost+(pa[j-1][0]*arr1[m].arr[j]);
  77.                     dp[i][j].area=dp[m][n+1].area+pa[j-1][1];
  78.                     c=dp[i][j].cost/dp[i][j].area;
  79.                     if(c<d)
  80.                     {
  81.                         d=c;
  82.                         a=dp[i][j].cost;
  83.                         b=dp[i][j].area;
  84.                     }
  85.                 }
  86.                 else
  87.                 {
  88.                     dp[i][j].cost=inf;
  89.                     dp[i][j].area=1;
  90.                 }
  91.             }
  92.             dp[i][n+1].cost=a;
  93.             dp[i][n+1].area=b;
  94.         }
  95.         a=inf;
  96.         for(i=1;i<=k-1;i++)
  97.         {
  98.             b=dp[i][n+1].cost/dp[i][n+1].area;
  99.             if(b<a)
  100.                 a=b;
  101.         }
  102.         printf("%0.4lf\n",a);
  103.     }
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0s 15096KB
comments (?)
stdin
copy 
1
80 30 0
2
200 100 1 2 50
200 100 0
5
100 100 2 3 50 2 50
100 100 1 4 50
100 100 1 2 40
600 600 1 5 10
1000 10 1 1 50
0
stdout
copy 
2.6667
1.5000
0.5333
https://ideone.com/KwQC2f
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!