obs
Attempted by: 97
/
Accuracy: 84%
/
PROBLEM
EDITORIAL
MY SUBMISSIONS
ANALYTICS
Tuco Salamanca has N distributors in New Mexico. He has to distribute methamphetamine in N districts. Each distributor has some probability of getting killed in each district. Given the probability of each distributor not getting killed in each district, Tuco has to assign districts to distributors (one distributor can take only one district) such that the probability of no one getting killed is maximized. Find this value for him.
Input:
First line contain N, the number of districts and distributors. Each of next N lines will contain N integers each. The j'th integer on i'th line is the probability that distributor number i will not get killed if assigned to district number i.
Output:
Print the probability (correct to 6 decimal digits).
Constraints:
1 ≤ N ≤ 20
0 ≤ Each probability ≤ 100
Notes:
1. Print output correct to 6 digits after decimal point, otherwise it leads to wrong answer.
2. The probability of no one getting killed is equal to the product of the probabilities of individual distributors not getting killed.
Input:
First line contain N, the number of districts and distributors. Each of next N lines will contain N integers each. The j'th integer on i'th line is the probability that distributor number i will not get killed if assigned to district number i.
Output:
Print the probability (correct to 6 decimal digits).
Constraints:
1 ≤ N ≤ 20
0 ≤ Each probability ≤ 100
Notes:
1. Print output correct to 6 digits after decimal point, otherwise it leads to wrong answer.
2. The probability of no one getting killed is equal to the product of the probabilities of individual distributors not getting killed.
SAMPLE INPUT
3 25 60 100 13 0 50 12 70 90
SAMPLE OUTPUT
9.100000
Explanation
Distributor 1 is assigned the 3rd district. Distributor 2 is assigned the 1st district. Distributor 3 is assigned the 2nd district. The probability in this case is, 10.130.7=9.1/100
Time Limit:
We need to see few aspects of this question. First of all dp[pos][bitmask] will give us time out because of the huge complexity. And the important observation is here since we need to assign all of them hence we do so by counting the number of on bits in the number. This will give us the number of the individual that is to be assigned. After doing this we can simply assign the person to their job and calculate the dp recursively. This question was similar to assignment spoj.
The code....
#include<bits/stdc++.h>using namespace std;
double a[22][22];double dp[(1<<20)+10];int mx;int n;double solve(int bm){ if(bm==mx) return 1.00; if(dp[bm]!=-1.00) return dp[bm]; double ret=0.00; int per=0; for(int i=0;i<=19;i++) { if(bm>>i &1) per++; } // cout<<"bm per"<<bm<<" "<<per<<endl; for(int i=0;i<n;i++) { if((bm>>i &1)==0) ret=max(ret,(a[per][i])/100.00*solve(bm|1<<i)); } dp[bm]=ret; return ret;}int main(){// int n; cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cin>>a[i][j]; } mx=(1<<n)-1; for(int i=0;i<(1<<20)+3;i++) { dp[i]=-1.00; } double res=solve(0); res=res*(double)100; printf("%.6lf",res); return 0;}
We need to see few aspects of this question. First of all dp[pos][bitmask] will give us time out because of the huge complexity. And the important observation is here since we need to assign all of them hence we do so by counting the number of on bits in the number. This will give us the number of the individual that is to be assigned. After doing this we can simply assign the person to their job and calculate the dp recursively. This question was similar to assignment spoj.
The code....
#include<bits/stdc++.h>using namespace std;
double a[22][22];double dp[(1<<20)+10];int mx;int n;double solve(int bm){ if(bm==mx) return 1.00; if(dp[bm]!=-1.00) return dp[bm]; double ret=0.00; int per=0; for(int i=0;i<=19;i++) { if(bm>>i &1) per++; } // cout<<"bm per"<<bm<<" "<<per<<endl; for(int i=0;i<n;i++) { if((bm>>i &1)==0) ret=max(ret,(a[per][i])/100.00*solve(bm|1<<i)); } dp[bm]=ret; return ret;}int main(){// int n; cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cin>>a[i][j]; } mx=(1<<n)-1; for(int i=0;i<(1<<20)+3;i++) { dp[i]=-1.00; } double res=solve(0); res=res*(double)100; printf("%.6lf",res); return 0;}
No comments:
Post a Comment